| • Science | • People | • Locations | • Timeline |
If you had to invent a sort algorithm on your own, you'd probably write an algorithm similar to selection sort because it is probably the more intuitive and immediate to invent.
An evolution of selection sort remembers the index of the minimum element that it finds in each pass. At the end of each pass it makes one exchange. This is more efficient because it reduces the total number of swaps, which cannot be bigger than the number n of elements to sort.
The naïve algorithm, iterating through a list of n unsorted items, has a worst-case, average-case, and best-case run-time of Θ(n2), assuming that comparisons can be done in constant time. Thus it is outperformed on almost-sorted lists by insertion sort.
Heapsort greatly improves the basic algorithm by using a heap data structure to speed up finding and removing the lowest datum.Implementation in C:
for(i=0 ; iImplementation in Basic:
For i = 1 To n - 1 For j = i + 1 To n If x(i) > x(j) Then temp = x(i) x(i) = x(j) x(j) = temp End If Next j Next iImplementation in C:
void selection_sort (int arr[], int n){ int i, j, min, min_i; for (i = 0; i < n-1; i++){ min = arr[i]; min_i = i; for (j = i+1; j < n; j++){ if (arr[j] < min){ min = arr[j]; min_i = j; } } arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; } }Implementation in Java:
public static void selectionSort (int[] numbers) { int min, temp; for (int index = 0; index < numbers.length-1; index++) { min = index; for (int scan = index+1; scan < numbers.length; scan++) if (numbers[scan] < numbers[min]) min = scan; // Swap the values temp = numbers[min]; numbers[min] = numbers[index]; numbers[index] = temp; } }