Selection sort to prosty algorytm sortowania. Ten algorytm sortowania jest algorytmem opartym na porównaniu na miejscu, w którym lista jest podzielona na dwie części, posortowaną część na lewym końcu i nieposortowaną część na prawym końcu. Początkowo posortowana część jest pusta, a nieposortowana część jest całą listą.
najmniejszy element jest wybierany z nieposortowanej tablicy i zamieniany z najbardziej wysuniętym na lewo elementem, a ten element staje się częścią posortowanej tablicy. Ten proces kontynuuje przesuwanie nieposortowanej granicy tablicy o jeden element w prawo.
algorytm ten nie jest odpowiedni dla dużych zbiorów danych, ponieważ jego średnia i najgorsza złożoność to Ο(N2), gdzie n jest liczbą elementów.
Jak Działa Sortowanie Wyboru?
rozważ poniższą tablicę jako przykład.
dla pierwszej pozycji posortowanej listy, cała lista jest skanowana sekwencyjnie. Na pierwszej pozycji, gdzie 14 jest obecnie przechowywane, przeszukujemy całą listę i stwierdzamy, że 10 jest najniższą wartością.
więc zamieniamy 14 na 10. Po jednej iteracji 10, która jest minimalną wartością na liście, pojawia się na pierwszej pozycji posortowanej listy.
dla drugiej pozycji, gdzie znajduje się 33, rozpoczynamy skanowanie reszty listy w sposób liniowy.
znajdujemy, że 14 jest drugą najniższą wartością na liście i powinna pojawić się na drugim miejscu. Wymieniamy te wartości.
po dwóch iteracjach dwie najmniejsze wartości są umieszczane na początku w sposób posortowany.
ten sam proces zostanie zastosowany do reszty elementów w tablicy.
Poniżej znajduje się obrazkowe przedstawienie całego procesu sortowania −
teraz poznajmy niektóre aspekty programowania selection sort.
algorytm
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
Pseudokod
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 < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
aby dowiedzieć się więcej o implementacji sortowania wyboru w języku programowania C, Kliknij tutaj.