Selection Sort Algorithm
Selection Sort algorithm is used to arrange a list of elements in a particular order (Ascending
or Descending). In selection sort, the first element in the list is selected and it is compared
repeatedly with all the remaining elements in the list. If any element is smaller than the
selected element (for Ascending order), then both are swapped so that first position is filled
with the smallest element in the sorted order. Next, we select the element at a second position
in the list and it is compared with all the remaining elements in the list. If any element is
smaller than the selected element, then both are swapped. This procedure is repeated until the
entire list is sorted.
//Selection sort logic
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
Complexity of the Selection Sort Algorithm
To sort an unsorted list with 'n' number of elements, we need to make ((n-1)+(n-2)+(n-
3)+......+1) = (n (n-1))/2 number of comparisions in the worst case. If the list is already sorted
then it requires 'n' number of comparisions.
Worst Case : O(n2)
Best Case : O (n2)
Average Case : O (n2)