Selection Sort in Data Structure

The most fundamental sorting algorithm is selection sort. This algorithm will start by finding the smallest element in the array and swapping it with the element in the first position, then moving on to the second smallest element and swapping it with the one in the second place, and so on until the entire array has been sorted. Selection sort is named for the fact that it constantly selects the next-smallest element and swaps it into the correct position.

Working of Selection Sort

Selection sort (sorting a given array in ascending order) involves the following steps:

1. We search the array for the smallest element and replace it with the element in the first position, starting with the first element.

2. From index 1 to the last index, we search for the smallest element in the sub array.

3. The second smallest element is used to replace the element at the second position in the original array, or the first position in the sub array.

4. This process is repeated until the array has been sorted fully.

With the help of the following example, we can better understand how the selection sort algorithm works. Consider the following array with the following elements: 41, 11, 36, 16, 21, 3, 11, 8.

The entire sorted list is scanned progressively for the initial position. We search the entire list and find that 3 is the lowest number at the first slot where 41 is currently stored.

As a result, we replace 41 with 3. After one iteration, the number 3, which happens to be the list’s minimum value, appears at the top of the sorted list.

We begin reading the rest of the list in a linear fashion for the second position, where 11 resides.

We discover that 8 is the second lowest value on the list and therefore it should be placed second. These values are swapped.

After two iterations, the two least values are sorted and placed at the beginning.

The rest of the items in the array are treated in the same way. The following is a diagram of the full sorting procedure.

Selection Sort Algorithm

Step 1: For i = 1 to n-1, do the following.

Step 2: Set min = arr[i].

Step 3: Set position = i.

Step 4: Repeat steps 1-3 for j = i+1 to n-1:

if (min > arr[j])

                Set min = arr[j]

             Set position = j

            [end of if]

        [end of loop]

Step 5: swap a[i] with arr[position]

        [end of loop]

Step 6: END

Complexity of Selection Sort

The time complexity of the selection sort is determined by the comparison and swap operations. In the selection sort algorithm, however, a swap operation is far more efficient than other sorting algorithms. The following are the total number of comparisons:  (n-1) + (n-2) + (n-3)+ ……..+ 1
= n(n-1)/2
~ {n}^{2}

1. Best Case: The data is already sorted within the array in this situation. As a result, there will be no exchanges, but the comparison will take place at every point. So, best case time complexity will be Ω({n}^{2}).

2. Average Case: The elements are not arranged in ascending or descending order. The array’s values are distributed at random. Here, the average case time complexity will be Θ({n}^{2}).

3. Worst Case: In the worst-case scenario, the array is in declining or non-increasing order. It will have the maximum number of swaps as well as comparisons. Here, the time complexity will be O({n}^{2}).

The selection sort algorithm has space complexity O(1).

Selection Sort’s Applications

The following are some of the applications of the selection sort technique:

• This method is suitable for smaller datasets.

• When the cost of swapping isn’t a factor, this function is used.

• It won’t work with content from the internet. For each iteration, it must have all of the array elements.

• When the cost of writing in flash memory is a factor, this is the best option.