Sortare selecție

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 februarie 2019; verificările necesită 33 de modificări .
Sortare selecție
scop Algoritm de sortare
Structură de date matrice
cel mai rău moment O( n 2 )
Cel mai bun timp O( n 2 )
Timp mediu O( n 2 )
Costul memoriei O(1)
 Fișiere media la Wikimedia Commons

Sortarea selecției este un algoritm de sortare . Poate fi fie stabil, fie instabil. Pe o matrice de n elemente, are un timp de rulare în cel mai rău caz, mediu și cel mai bun caz de Θ ( n 2 ), presupunând că comparațiile sunt făcute în timp constant.

Algoritm fără alocare suplimentară de memorie

Etapele algoritmului:

  1. găsiți numărul valorii minime din lista curentă
  2. schimbăm această valoare cu valoarea primei poziții nesortate (schimbul nu este necesar dacă elementul minim este deja la această poziție)
  3. acum sortăm coada listei, excluzând elementele deja sortate din considerare

Un exemplu de implementare instabilă :

C++

template < typename type_arr > void selectie_sort ( tip_arr * arr , dimensiune int ) { pentru ( int i = 0 ; i < dimensiune - 1 ; i ++ ) { int min_index = i ; pentru ( int j = i + 1 ; j < dimensiune ; j ++ ) { dacă ( arr [ j ] < arr [ min_index ]) { min_index = j ; } } dacă ( min_index != i ) { swap ( arr [ i ], arr [ min_index ]); } } }

C#

public static IList < T > Selecție < T >( IList < T > listă ) unde T : IComparable < T > { pentru ( int i = 0 ; i < listă . Număr - 1 ; ++ i ) { int min = i ; pentru ( int j = i + 1 ; j < listă . Număr ; ++ j ) { if ( lista [ j ]. CompareTo ( lista [ min ]) < 0 ) { min = j ; } } vardummy = lista [ i ] ; list [ i ] = list [ min ]; list [ min ] = dummy ; } lista de returnare ; }

PL/SQL

tip sort_choice_list este tabel cu index întreg de binary_integer ; -------------------------------------------------- -- funcția SORT_CHOICE returnează sort_choice_list ESTE list sort_choise_list ; l_min pls_integer ; l_dummy pls_integer ; ÎNCEPE pentru n în 1 .. 100 bucle listă ( n ): = dbms_random . aleatoriu ; --inițializarea matricei cu numere aleatorii buclă de capăt ; pentru eu in lista . primul .. lista . ultima buclă l_min : = i ; pentru j în ( i + 1 ).. listă . ultima buclă daca ( lista ( j ) < lista ( l_min )) atunci l_min : = j ; termina daca ; buclă de capăt ; l_dummy : = lista ( i ); list ( i ): = list ( l_min ); listă ( l_min ) : = l_dummy ; buclă de capăt ; lista de returnare ; final SORT_CHOICE ;

Java

public static < T se extinde Comparabil <? super T >> void sort ( T [] matrice ) { pentru ( int i = 0 ; i < matrice . lungime - 1 ; ++ i ) { int minPos = i ; pentru ( int j = i + 1 ; j < matrice . lungime ; ++ j ) { if ( matrice [ j ] . compareTo ( matrice [ minPos ] ) < 0 ) { minPos = j ; } } T saveValue = matrice [ minPos ] ; matrice [ minPos ] = matrice [ i ] ; matrice [ i ] = saveValue ; } }

rubin

def selectie_sort ( matrice ) pentru min în 0 .. matrice . numără - 2 minim = min pentru j în ( min + 1 ) .. matrice . numără - 1 if matrice [ j ] < matrice [ minim ] cel puțin = j Sfârşit Sfârşit temp = matrice [ min ] matrice [ min ] = matrice [ minim ] matrice [ minim ] = temp Sfârşit Sfârşit

Rapid

func selectionSort < Element >( _ array : inout Array < Element >) unde Element : Comparabil { pentru min în 0. .< matrice . numără - 1 { pentru j în min ..< matrice . numără { if matrice [ j ] < matrice [ min ] { let temp = matrice [ min ] matrice [ min ] = matrice [ j ] matrice [ j ] = temp } } } }

PascalABC.NET

ÎNCEPE var a := ArrRandom ; a . Println ; pentru var i := 0 la a . High do Schimbați ( a [ i ] , a [ i + a [ i : ] . IndexMin ]) ; a . Println ; Sfârşit

Piton

def select_sort ( A ): pentru i în interval ( len ( A ) - 1 ): pentru k în interval ( i + 1 , len ( A )): dacă A [ k ] < A [ i ]: A [ k ], A [ i ] = A [ i ], A [ k ]

merge

func selectieSort ( nums [] int ) { n := len ( nums ) pentru i := 0 ; i < n ; i ++ { min := i pentru j := i + 1 ; j < n ; j ++ { dacă nums [ j ] < nums [ min ] { min = j } } nums [ i ], nums [ min ] = nums [ min ], nums [ i ] } }

Să arătăm de ce această implementare este instabilă.
Luați în considerare următoarea matrice de elemente, fiecare cu două câmpuri. Sortarea se face pe primul câmp.
Matrice înainte de sortare:
{ (2, a), (2, b), (1, a) }
Deja după prima iterație a buclei exterioare, vom avea o secvență sortată:
{ (1, a), (2, b), (2, a) }
Acum rețineți că poziția relativă a elementelor (2, a) și (2, b) sa schimbat. Astfel, implementarea considerată este instabilă.


Deoarece se face un singur schimb după fiecare trecere prin bucla interioară, numărul total de schimburi este N-1, care este de N/2 ori mai mic decât în ​​sortarea cu bule .
Numărul de treceri prin bucla interioară este N-1 chiar dacă sortați o matrice sortată parțial sau complet.

Cel mai rău caz:
numărul de comparații din corpul buclei este (N-1)*N/2.
Numărul de comparații în anteturile buclei (N-1)*N/2.
Numărul de comparații înainte de operațiunea de schimb N-1.
Numărul total de comparații este N 2 −1.
Numărul de schimburi N-1.

Cel mai bun caz:


Timpul de sortare a 10.000 de numere întregi scurte pe același sistem hardware și software prin sortare de selecție a fost ≈40 sec, iar sortarea cu bule chiar mai îmbunătățită a fost ≈30 sec.

Heapsort îmbunătățește foarte mult algoritmul de bază prin utilizarea unei structuri de date heap pentru a accelera găsirea și eliminarea elementului minim.

Există, de asemenea, o variantă bidirecțională de sortare a selecției, în care atât valorile minime, cât și cele maxime sunt găsite și stabilite la fiecare trecere.

Literatură

  • Levitin A. V. Capitolul 3. Metoda forței brute: Sortarea selecției // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 143-144. — 576 p. — ISBN 978-5-8459-0987-9
  • Robert Sedgwick. Partea a III-a. Capitolul 6. Metode elementare de sortare: 6.2 Selection Sort // Algoritmi în C++ = Algoritmi în C++. - M . : „Williams” , 2011. - S. 246-247. - ISBN 978-5-8459-1650-1 .
  • Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .

Vezi și

Link -uri

 Algoritmi de sortare
Teorie Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern
schimb valutar
Alegere
inserții
fuziune
Fara comparatii
hibrid
Alte
nepractic