Selection sort
|
|
Selection 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
- sort the remainder of the list (excluding the first value)
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. It is generally out performed 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 (x[min] > x[j]) {
min = j;
}
}
temp = x[i];
x[i] = x[min];
x[min] = 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 (numbers[scan] < numbers[min])
min = scan;
// Swap the values
temp = numbers[min];
numbers[min] = numbers[index];
numbers[index] = 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(array[index] < array[min]) 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 = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
de:Selectionsort
fr:Tri par slection lt:Išrinkimo rūšiavimo algoritmas ja:選択ソート pl:Sortowanie przez wybieranie pt:Selection sort