Hello! Today we will conduct a coding test lecture using C#. The topic for today is selection sort, which is one of the basics of algorithms. Selection sort is a simple and intuitive sorting algorithm. In this lecture, we will explain the concept of selection sort, how the algorithm works, how to implement it, and how to apply selection sort to actual problems with examples.
1. What is Selection Sort?
Selection sort sorts by finding the smallest (or largest) value from a given list and swapping that value with the first position in the list. Next, it finds the smallest value from the remaining list and swaps it with the second position. This process continues until all elements are sorted, which is the principle of selection sort.
2. How the Algorithm Works
Let’s take a look at the step-by-step operation of selection sort. Let’s assume the given list is [64, 25, 12, 22, 11].
- Step 1: Find the smallest value in the entire list. Since 11 is the smallest, we swap 11 with 64. (Current list: [11, 25, 12, 22, 64])
- Step 2: Find the smallest value in the remaining list. Since 12 is the smallest, we swap 12 with 25. (Current list: [11, 12, 25, 22, 64])
- Step 3: Since 22 is the smallest in the remaining list, we swap 22 with 25. (Current list: [11, 12, 22, 25, 64])
- Step 4: Finally, we swap 25 with 25. (Current list: [11, 12, 22, 25, 64])
In this way, the list is sorted. The sorting process has a time complexity of O(n^2) in the worst and average cases.
3. Implementing Selection Sort in C#
Next, let’s implement selection sort in C#. The code below is a C# program that sorts an array using the selection sort algorithm.
using System;
class SelectionSort
{
static void Main(string[] args)
{
int[] array = { 64, 25, 12, 22, 11 };
Console.WriteLine("Array before sorting:");
PrintArray(array);
SelectionSort(array);
Console.WriteLine("Array after sorting:");
PrintArray(array);
}
static void SelectionSort(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
// Swap the minimum value with the value at the current position
if (minIndex != i)
{
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
static void PrintArray(int[] arr)
{
foreach (int num in arr)
{
Console.Write(num + " ");
}
Console.WriteLine();
}
}
4. Code Explanation
Let’s briefly explain the code. The SelectionSort class contains the Main method. This method is the entry point of the program, where a predefined array is declared and the array before and after sorting is printed.
The SelectionSort method contains the core logic of the selection sort algorithm. This method traverses the given array, finds the index of the minimum value at each position, and swaps that value with the value at the current position. The PrintArray method performs the function of printing all the elements of the array.
5. Advantages and Disadvantages of Selection Sort
Advantages
- It is simple and intuitive to implement.
- It uses little memory. Since it does not use much additional memory, it has a space complexity of O(1).
Disadvantages
- It has a high time complexity (O(n^2) in the worst case), making it unsuitable for large datasets.
- It is not stable in sorting. If there are duplicate values, the relative order is not guaranteed.
6. Example Problems Where Selection Sort Can Be Used
Let’s give an example of a situation where selection sort can be used in coding tests. For instance, after sorting the students’ scores in ascending order, a program can be implemented to assign grades based on the scores. The problem is as follows:
Problem: Given an array of students’ scores, sort the scores in ascending order using the selection sort algorithm.
Input
10, 3, 76, 34, 2, 45, 65, 23, 90
Output
2, 3, 10, 23, 34, 45, 65, 76, 90
This problem can be solved using selection sort, and the implementation of the code can be based on the previous selection sort code.
7. Conclusion
Through this lecture, we learned about selection sort. Selection sort is a simple but easy-to-understand sorting algorithm, which greatly helps in understanding the fundamental principles of algorithm operation. Additionally, by directly implementing it using C#, we could experience the working process of the algorithm. We explored how selection sort can be applied in various algorithmic problems, and I encourage you to apply it to various problems!
In the next lecture, we will cover another sorting algorithm, insertion sort. Thank you!