Selection Sort – Sorting in C++ – 2
February 15, 2011 Leave a comment
Selection sort works as follows: we select the max element in the array and place it at the last position. In the next iteration, we select the 2nd largest element of the array, and place it at the 2nd last position. Continue doing so until the array is sorted.
void sel_sort (int A [ ], int n)
int max, max_index;
for (int i = 0; i < n-1; i++)
max = A;
max_index = 0;
for (int j = 1; j < n-i; j++)
if ( A[j] > max)
max = A[j];
max_index = j;
//now swap A[n-i] and A[max_index].
temp = A[n-i];
A[n-i] = A[max_index];
A[max_index] = temp;
Running time : for all cases – O(n^2).