sorting
Auswahl
Suche…
Bemerkungen
In der Informatik ist eine Auswahlsortierung ein Sortieralgorithmus, insbesondere eine Direktvergleichssortierung. Es hat eine O (n 2 ) -Zeitkomplexität, was es bei großen Listen ineffizient macht und im Allgemeinen schlechter abschneidet als die ähnliche Sortierreihenfolge. Die Auswahl der Auswahl ist für ihre Einfachheit bekannt und hat in bestimmten Situationen, insbesondere wenn der Hilfsspeicher begrenzt ist, Leistungsvorteile gegenüber komplizierteren Algorithmen.
Das Bild unten zeigt, wie die Auswahlsortierung funktioniert.
Der folgende Pseudo-Code hilft beim Erstellen eines Programms (in einer beliebigen Sprache) oder beim Verständnis der Auswahl.
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
Vorteile:
- Es ist zu einfach zu verstehen
- es funktioniert gut auf einer kleinen Liste
- Es ist kein zusätzlicher temporärer Speicher erforderlich, der für die Aufbewahrung der ursprünglichen Liste erforderlich ist
Bildreferenz: RMIT University
Auswahl sortieren (Python)
Animation, um zu zeigen, wie die Auswahlsortierung funktioniert
Das folgende Beispiel zeigt die Sortierung der Auswahl in Python
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)
Ausgabe des Programms:
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]
Bildreferenz: Piratenschüler
Auswahl sortieren (Java)
Animation, um zu zeigen, wie die Auswahlsortierung funktioniert
Das folgende Beispiel zeigt die Auswahl in aufsteigender Reihenfolge:
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;
}
Ich habe eine Beispielmethode main() , um die Ausgabe der Auswahlsorte anzuzeigen:
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(", ");
}
}
}
Ausgabe des Programms:
2, 7, 10, 34, 42, 56, 67, 88
Das folgende Beispiel zeigt die Auswahl der Sortierung in absteigender Reihenfolge:
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;
}
}
Bildreferenz: Wikipedia