Sorting: Selection Sort
Selection sort is probably one of the simplest sorting algorithms. In this technique, we will iterate through the list, identify the smallest element and put it at the first place in an array ( 0th index, since an array starts with the index zero). Once the first index (the 0th index of an array) is done, we will move on to the 2nd place in an array. We again iterate through the array from the second index and find the next smallest number. The reason we start with 2nd place is because the first place (0th index) in the array is already occupied with the smallest element of the list. We keep doing the above iterations until all the spots in the array are occupied by the correct elements.
To understand selection sort further, we provide an example below that shows the first iteration of selection sort. We take an array and go through the first iteration. In this iteration, we focus on the first index of the array and compare it with all the other elements (starting from second index). If we find an element that is smaller, then we do the swap with the first element. At the end of first iteration, the smallest element in the list (84) is positioned at the 1st place (0th index of the array).
Figure: Selection Sort: First Iteration
For the sake of simplicity we did not show the remaining iterations.
Implementation
Let us now look at an implementation. Our implementation uses an in place approach. In place sorting algorithm is the one where the extra space needed to a sort the list is (usually small) constant. In other words the extra/temporary space needed to sort a list remains same irrespective of the size of a given list. Here, we will see an in place version of the selection sort.
#include <stdio.h>
void print_array (int input_array[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ",input_array[i]);
}
}
void selection_sort (int input_array[], int size) {
int i,j,temp,k;
for (i = 0; i < size-1; i++) {
for (j = i+1; j < size; j++) {
if (input_array[i] > input_array[j]) {
temp = input_array[i];
input_array[i] = input_array[j];
input_array[j] = temp;
}
}
printf (" \n\tAfter Iteration %d \n\t", i+1);
print_array(input_array,size);
}
}
int main (int argc, char *argv[]) {
int i;
/* Initialize the array */
int input_array[] = {280,84,680,237,101,880};
int len = sizeof(input_array)/sizeof(input_array[0]);
printf("Before sorting :");
print_array(input_array,len);
selection_sort(input_array,len);
printf("\nAfter sorting :");
print_array(input_array,len);
printf(" \n");
return 0;
}
In the above code, the selection_sort function is the heart of the program. In this function the outer loop forms each iteration of selection sort. For each iteration we run an inner loop (represented by j).
In terms of time-complexity, the selection_sort() does N iterations and in each iteration, it compares all the N elements. Therefore, the time complexity of this algorithm is O(N^2). Selection sort has the same complexity, whether it is worst-case or best-case or average.
Let us go ahead and compile the above example. Here is the output:
$ gcc selection_sort.c -o selection_sort $ ./selection_sort Before sorting :280 84 680 237 101 880 After Iteration 1 84 280 680 237 101 880 After Iteration 2 84 101 680 280 237 880 After Iteration 3 84 101 237 680 280 880 After Iteration 4 84 101 237 280 680 880 After Iteration 5 84 101 237 280 680 880 After sorting :84 101 237 280 680 880