|
Selection SortSelection sort is a sort algorithm that works as follows: - find the minimum value in the list
- swap it with the value in the first position
- find the minimum value amongst the remaining values
- swap it with the value in the second position
- repeat until the list is sorted
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 most intuitive and immediate to invent. This 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. Selection sort is not a stable sort. Heapsort greatly improves the basic algorithm by using a heap data structure to speed up finding and removing the lowest datum. Implementations of Selection Sort Implementation in C: for (i = 0; i < n-1; i++) { min = i; for (j = i+1; j < n; j++) { if (xmin > xj) { min = j; } } temp = xi; xi = xmin; xmin = temp; } Implementation in Basic: For i = 1 To n - 1 min = i For j = i + 1 To n If x(min) > x(j) Then min = j End If Next j temp = x(i) x(i) = x(min) x(min) = temp Next i Implementation in Java (iterative): 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 (numbersscan < numbersmin) min = scan; // Swap the values temp = numbersmin; numbersmin = numbersindex; numbersindex = temp; } } Implementation in Java (recursive): // Selection sort for an array of ints public static int findMin(int[] array, int index) { int min = index - 1; if(index < array.length - 1) min = findMin(array, index + 1); if(arrayindex < arraymin) min = index; return min; } public static void selectionSort(int[] array) { for(int left = 0; left < array.length - 1; left++) { swap(array, left, findMin(array, left)); } } public static void swap(int[] array, int index1, int index2) {//swap the two values int temp = arrayindex1; arrayindex1 = arrayindex2; arrayindex2 = temp; }
|