Kijelölés rendezése

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. február 22-én felülvizsgált verziótól ; az ellenőrzések 33 szerkesztést igényelnek .
Kijelölés rendezése
célja Rendezési algoritmus
Adatstruktúra sor
legrosszabb idő O( n 2 )
Legjobb idő O( n 2 )
Átlagos idő O( n 2 )
A memória költsége O(1)
 Médiafájlok a Wikimedia Commons oldalon

A kijelölés rendezése egy rendezési algoritmus . Lehet stabil vagy instabil. Egy n elemű tömbön a legrosszabb eset, az átlagos és a legjobb eset futásideje Θ ( n 2 ), feltételezve, hogy az összehasonlításokat állandó időben végezzük.

Algoritmus további memóriafoglalás nélkül

Az algoritmus lépései:

  1. keresse meg a minimális érték számát az aktuális listában
  2. ezt az értéket felcseréljük az első rendezetlen pozíció értékével (a csere nem szükséges, ha a minimális elem már ezen a pozíción van)
  3. most a lista végét rendezzük, kizárva a már rendezett elemeket a figyelembevételből

Példa egy instabil megvalósításra:

C++

sablon < typename type_arr > void selection_sort ( type_arr * arr , int size ) { for ( int i = 0 ; i < méret - 1 ; i ++ ) { int min_index = i ; for ( int j = i + 1 ; j < méret ; j ++ ) { if ( arr [ j ] < arr [ min_index ]) { min_index = j ; } } if ( min_index != i ) { csere ( arr [ i ], arr [ min_index ]); } } }

C#

nyilvános statikus ILista < T > Kijelölés < T > ( ILista < T > lista ) ahol T : IComparable < T > { for ( int i = 0 ; i < lista . Szám - 1 ; ++ i ) { int min = i ; for ( int j = i + 1 ; j < lista . Szám ; ++ j ) { if ( lista [ j ]. Összehasonlítás ( lista [ min ]) < 0 ) { min = j ; } } vardummy = lista [ i ] ; lista [ i ] = lista [ min ]; lista [ min ] = dummy ; } visszatérési lista ; }

PL/SQL

type sort_choice_list a bináris_egész szám szerinti egész index táblázata ; -------------------------------------------------- -- függvény SORT_CHOICE visszaadja a sort_choice_list IS list sort_choise_list ; l_min pls_integer ; l_dummy pls_integer ; kezdődik n - re 1 .. 100 hurok lista ( n ): = dbms_random . véletlenszerű ; --tömb inicializálása véletlen számokkal end - loop ; nekem a listán . _ első .. lista . utolsó hurok l_min : = i ; for j in ( i + 1 ).. lista . utolsó hurok if ( lista ( j ) < list ( l_min )) akkor l_min : = j ; vége if ; end - loop ; l_dummy : = lista ( i ); lista ( i ): = lista ( l_min ); lista ( l_min ) : = l_dummy ; end - loop ; visszatérési lista ; vége SORT_CHOICE ;

Jáva

nyilvános statikus < T kiterjeszti Összehasonlítható <? szuper T >> void rendezés ( T [ ] tömb ) { for ( int i = 0 ; i < tömb . hossza - 1 ; ++ i ) { int minPos = i ; for ( int j = i + 1 ; j < tömb . hossza ; ++ j ) { if ( array [ j ] . ÖsszehasonlítTo ( array [ minPos ] ) < 0 ) { minPos = j ; } } T saveValue = tömb [ minPos ] ; tömb [ minPos ] = tömb [ i ] ; tömb [ i ] = saveValue ; } }

rubin

def selection_sort ( tömb ) min 0 .. tömbben . _ _ szám - 2 minimum = min for j in ( min + 1 ) .. tömb . szám - 1 if tömb [ j ] < tömb [ legkevesebb ] legalább = j vége vége temp = tömb [ perc ] tömb [ min ] = tömb [ legkevesebb ] array [ legkevesebb ] = temp vége vége

Gyors

func selectionSort < Element >( _ array : inout Array < Element >) where Element : Comparable { min 0 - ban . .< tömb . szám - 1 { j esetén min .. < tömb . count { if array [ j ] < array [ min ] { legyen temp = tömb [ min ] tömb [ min ] = tömb [ j ] tömb [ j ] = temp } } } }

PascalABC.NET

kezdődik var a := ArrRandom ; a . Println ; a var i := 0 -tól a -ig . Magas do Csere ( a [ i ] , a [ i + a [ i : ] . IndexMin ]) ; a . Println ; vége

Piton

def select_sort ( A ): i tartományban ( len ( A ) - 1 ) : _ k tartományban ( i + 1 , len ( A ) ) : ha A [ k ] < A [ i ]: A [ k ], A [ i ] = A [ i ], A [ k ]

megy

func selectionSort ( számok [ ] int ) { n := len ( számok ) for i := 0 ; i < n ; én ++ { min := i j esetén := i + 1 ; j < n ; j ++ { if számok [ j ] < számok [ min ] { min = j } } számok [ i ], számok [ min ] = számok [ perc ], számok [ i ] } }

Mutassuk meg, miért instabil ez a megvalósítás.
Tekintsük a következő elemtömböt, amelyek mindegyike két mezővel rendelkezik. A rendezés az első mezőben megy.
Tömb rendezés előtt:
{ (2, a), (2, b), (1, a) }
Már a külső ciklus első iterációja után lesz egy rendezett sorozatunk:
{ (1, a), (2, b), (2, a) }
Most vegyük észre, hogy a (2, a) és (2, b) elemek egymáshoz viszonyított helyzete megváltozott. Így a vizsgált megvalósítás instabil.


Mivel a belső hurkon minden egyes áthaladás után csak egy csere történik, a cserék teljes száma N-1, ami N/2-szer kevesebb, mint a buborékos rendezésnél .
A belső hurkon való áthaladások száma még akkor is N-1, ha egy részben vagy teljesen rendezett tömböt rendezünk.

Legrosszabb eset:
A huroktörzsben az összehasonlítások száma (N-1)*N/2.
Összehasonlítások száma hurokfejlécekben (N-1)*N/2.
A csereművelet előtti összehasonlítások száma N-1.
Az összehasonlítások száma összesen N 2 −1.
Cserék száma N-1.

Legjobb eset:


A 10 000 rövid egész szám rendezési ideje ugyanazon a hardver- és szoftverrendszeren kiválasztási rendezés szerint ≈40 másodperc volt, és a még továbbfejlesztett buborékrendezés ≈30 másodperc volt.

A Heapsort nagymértékben javítja az alapul szolgáló algoritmust azáltal, hogy halom adatstruktúrát használ a minimális elem megtalálásának és eltávolításának felgyorsítására.

A kiválasztási rendezésnek létezik egy kétirányú változata is, amelyben a minimális és a maximális értékek is megtalálhatók és be vannak állítva minden egyes lépésnél.

Irodalom

  • Levitin A. V. 3. fejezet: Brute force method: Selection sort // Algorithms. Bevezetés a fejlesztésbe és elemzésbe - M . : Williams , 2006. - S. 143-144. — 576 p. — ISBN 978-5-8459-0987-9
  • Robert Sedgwick. rész III. 6. fejezet Elemi rendezési módszerek: 6.2 Kijelölés rendezés // Algoritmusok C++ nyelven = Algorithms in 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 / Szerk. I. V. Krasikova. - 2. kiadás - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .

Lásd még

Linkek

 Rendezési algoritmusok
Elmélet Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső
Csere
Választás
Betétek
egyesülés
Nincs összehasonlítás
hibrid
Egyéb
nem praktikus