sorting
Selectie
Zoeken…
Opmerkingen
In de informatica is een selectiesoort een sorteeralgoritme, met name een interne sorteersoort. Het heeft O (n 2 ) tijdcomplexiteit, waardoor het in grote lijsten inefficiënt is en over het algemeen slechter presteert dan de vergelijkbare invoegsoort. Selectie sorteren staat bekend om zijn eenvoud, en het heeft prestatievoordelen ten opzichte van meer gecompliceerde algoritmen in bepaalde situaties, met name wanneer het hulpgeheugen beperkt is.
De onderstaande afbeelding laat zien hoe de selectie sorteren werkt-
Onderstaande pseudo-code helpt bij het maken van een programma (in elke taal) of het begrijpen van selectiesoorten.
procedure selection sort
list : array of items
n : size of list
for i = 1 to n - 1
/* set current element as minimum*/
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure
Voordelen:
- het is te eenvoudig om te begrijpen
- het presteert goed op een kleine lijst
- er is geen extra tijdelijke opslag vereist dan nodig is om de oorspronkelijke lijst te bewaren
Afbeeldingsreferentie: RMIT University
Selectie sorteren (Python)
Animatie om te laten zien hoe selectie sorteren werkt
In het onderstaande voorbeeld wordt de sortering van de selectie in Python weergegeven
def sort_selection(my_list):
for pos_upper in xrange( len(my_list)-1, 0, -1):
max_pos = 0
for i in xrange(1, pos_upper + 1):
if(my_list[i] > my_list[max_pos]):
max_pos = i
print "resetting max_pos = " + str(max_pos)
my_list[pos_upper], my_list[max_pos] = my_list[max_pos], my_list[pos_upper]
print "pos_upper: " + str(pos_upper) + " max_pos: " + str(max_pos) + " my_list: " + str(my_list)
return my_list
if __name__ == "__main__":
my_list = [54,26,93,17,77,31,44,55,20]
print "my_list: " + str(my_list)
print sort_selection(my_list)
Uitgang van het programma:
my_list: [54, 26, 93, 17, 77, 31, 44, 55, 20]
resetting max_pos = 2
pos_upper: 8 max_pos: 2 my_list: [54, 26, 20, 17, 77, 31, 44, 55, 93]
resetting max_pos = 4
pos_upper: 7 max_pos: 4 my_list: [54, 26, 20, 17, 55, 31, 44, 77, 93]
resetting max_pos = 4
pos_upper: 6 max_pos: 4 my_list: [54, 26, 20, 17, 44, 31, 55, 77, 93]
pos_upper: 5 max_pos: 0 my_list: [31, 26, 20, 17, 44, 54, 55, 77, 93]
resetting max_pos = 4
pos_upper: 4 max_pos: 4 my_list: [31, 26, 20, 17, 44, 54, 55, 77, 93]
pos_upper: 3 max_pos: 0 my_list: [17, 26, 20, 31, 44, 54, 55, 77, 93]
resetting max_pos = 1
pos_upper: 2 max_pos: 1 my_list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
resetting max_pos = 1
pos_upper: 1 max_pos: 1 my_list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
Afbeeldingsreferentie: Pirate Learner
Selectie sorteren (Java)
Animatie om te laten zien hoe selectie sorteren werkt
Onderstaand voorbeeld toont de selectie in oplopende volgorde:
public class MySelectionSort {
public static int[] doSelectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return arr;
}
Ik heb een voorbeeld van de methode main() geschreven om de uitvoer van de selectiesoort te tonen:
public static void main(String a[]){
int[] arr1 = {10,34,2,56,7,67,88,42};
int[] arr2 = doSelectionSort(arr1);
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}
Uitgang van het programma:
2, 7, 10, 34, 42, 56, 67, 88
Onderstaand voorbeeld toont de selectie in aflopende volgorde:
public static void doDescendingSelectionSort ( int [ ] num )
{
int i, j, first, temp;
for ( i = num.length - 1; i > 0; i - - )
{
first = 0; //initialize to subscript of first element
for(j = 1; j <= i; j ++) //locate smallest element between positions 1 and i.
{
if( num[ j ] < num[ first ] )
first = j;
}
temp = num[ first ]; //swap smallest found with element in position i.
num[ first ] = num[ i ];
num[ i ] = temp;
}
}
Afbeeldingsreferentie: Wikipedia