sorting
Urval
Sök…
Anmärkningar
Inom datavetenskap är en urvalssortering en sorteringsalgoritm, speciellt en jämförelsesortering på plats. Den har O (n 2 ) tidskomplexitet, vilket gör den ineffektiv på stora listor och fungerar generellt sämre än den liknande insättningssorten. Urvalssortering är känd för sin enkelhet och har prestandafördelar jämfört med mer komplicerade algoritmer i vissa situationer, särskilt där hjälpminnet är begränsat.
Bilden nedan visar hur urvalssorten fungerar-
Nedan hjälper pseudokoden till att skapa ett program (på vilket språk som helst) eller förstå sorteringsval.
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
Fördelar:
- det är för enkelt att förstå
- det fungerar bra på en liten lista
- ingen extra tillfällig lagring krävs utöver vad som krävs för att hålla originallistan
Bildreferens: RMIT University
Urvalssortering (Python)
Animering för att visa hur urvalssortering fungerar
Exemplet nedan visar sortens sortering i 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)
Utgång av programmet:
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]
Bildreferens: Pirate Learner
Urvalssortering (Java)
Animering för att visa hur urvalssortering fungerar
Nedanstående exempel visar urvalssortering i stigande ordning:
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;
}
Jag har skrivit ett exempel på main() för att visa utgången från urvalssorten:
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(", ");
}
}
}
Utgång av programmet:
2, 7, 10, 34, 42, 56, 67, 88
Nedanstående exempel visar valssortering i fallande ordning:
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;
}
}
Bildreferens: Wikipedia