Selection Sort
An Introduction with Examples |
Prof. David Bernstein |
Computer Science Department |
bernstdh@jmu.edu |
8 | 4 | 7 | 3 | 3 | 9 |
3 | 4 | 7 | 3 | 8 | 9 |
3 | 4 | 3 | 7 | 8 | 9 |
3 | 3 | 4 | 7 | 8 | 9 |
3 | 3 | 4 | 7 | 8 | 9 |
/** * Sort an array of integers using a selection sort * * Side Effects: The array is sorted "in place" * * @param a The array of integers * @param length The number of elements in the array */ void sort(int a[], int length) { int bottom, i, indexOfMax, temp; for (bottom = length - 1; bottom >= 1; bottom--) { indexOfMax = 0; for (i = 1; i <= bottom; i++) { if (a[i] > a[indexOfMax]) indexOfMax = i; } temp = a[bottom]; a[bottom] = a[indexOfMax]; a[indexOfMax] = temp; } }
\( T(n) = (n-1) + (n-2) + \cdots 2 + 1 = n \cdot (n-1)/2 \)
So: \( T(n) = O(n^2) \)