Un fel de agitator
| Un fel de agitator | |
|---|---|
| Clasă | Algoritm de sortare |
| Structură de date | Matrice |
| Cel mai rău caz din punct de vedere temporal | О (n²) |
| Optim | Nu |
În informatică, sortarea Shaker , cunoscută și sub numele de sortare bidirecțională cu bulă , sortare cocktail , sortare cocktail shaker , sortare Ripple , sortare Happy hour sau sortare Shuttle este un algoritm de sortare a datelor dezvoltat de Sun Microsystems . Sortarea agitatorului este în esență o variantă a sortării cu bule : diferă de acesta din urmă pentru indicele ciclului cel mai intern care, în loc să ruleze de la început până la sfârșit, își inversează direcția la fiecare ciclu. În timp ce menține aceeași complexitate , adică O (n²) , sortarea agitatorului reduce probabilitatea ca sortarea să aibă un cost corespunzător celui mai rău caz .
Notă: Pentru a înțelege următoarele, este necesar să înțelegeți funcționarea generală a sortării cu bule .
Pseudo cod
Cea mai simplă formă a agitatorului de sortare derulează întreaga listă la fiecare pas (cazul sortării descendente este prezentat mai jos):
procedure shakerSort (A : lista articolelor care trebuie sortate) definit ca:
do
schimbat: = false
pentru fiecare i în 0 până la lungimea (A) - 2 faceți:
dacă A [i]> A [i + 1] atunci // verificați dacă cele 2 elemente sunt în ordine greșită
swap (A [i], A [i + 1]) // swap cele 2 elemente
schimbat: = true
incheie daca
sfârșit pentru
dacă se schimbă = fals atunci
// dacă nu se efectuează schimburi, bucla cea mai exterioară poate fi ieșită
rupe bucla do-while
incheie daca
schimbat: = false
pentru fiecare i în lungime (A) - 2 până la 0 faceți:
dacă A [i]> A [i + 1] atunci
swap (A [i], A [i + 1])
schimbat: = true
incheie daca
sfârșit pentru
în timp ce se schimbă // dacă nu au fost efectuate swap-uri, atunci lista este sortată
încheierea procedurii
Primul pas spre dreapta va muta cel mai mare element în poziția corectă la sfârșitul listei, în timp ce următorul pas spre stânga va muta cel mai mic element în poziția corectă din partea de sus a listei. A doua trecere completă se va muta de- al doilea cel mai mare și al doilea cel mai mic element în poziția corectă, și așa mai departe: după „“ trece mai întâi „elementele“ a și ultimul „elementele“ ale listei vor fi poziționate corect, și nu va trebui să le verificați de două ori. Numărul de operații poate fi redus prin scurtarea părții din listă care este sortată la fiecare pas.
procedure cocktailSort (A : lista articolelor de sortat) definit ca: // „începe” și „sfârșit” marchează primul și ultimul index de verificat începe: = -1 final: = lungime (A) - 2 do schimbat: = false // incrementează `începe`, deoarece elementele dinaintea„ începe` sunt sortate corect începe: = începe + 1 pentru fiecare i în a începe să se încheie face: dacă A [i]> A [i + 1] atunci swap (A [i], A [i + 1]) schimbat: = true incheie daca sfârșit pentru dacă se schimbă = fals atunci rupe bucla do-while incheie daca schimbat: = false // decrementează `end` deoarece elementele de după„ end` sunt sortate corect sfârșit: = sfârșit - 1 pentru fiecare i în cele din urmă pentru a începe faceți: dacă A [i]> A [i + 1] atunci swap (A [i], A [i + 1]) schimbat: = true incheie daca sfârșit pentru în timp ce era schimbat încheierea procedurii
Explicaţie
Sortarea cu bule are o asimetrie intrinsecă: valorile matricei sunt mutate rapid într-o direcție (și exact în cea în care scanarea matricei continuă în timpul unei iterații) și încet în cealaltă direcție. De exemplu, dacă matricea este scanată înainte și numerele sunt aranjate în ordine crescătoare, numerele mari vor avansa rapid, numerele mici se vor mișca înapoi încet. Putem clarifica mai bine acest concept cu acest exemplu. Luați în considerare această mică matrice:
15 4 10 11 2
În timpul primei iterații, 15 este mutat în mod repetat (vezi sortarea cu bule ), cu următorul rezultat final:
4 10 11 2 15
Prin urmare, se poate vedea că în arcul unei singure iterații, „15” (numărul maxim care era în prima poziție) a traversat întreaga matrice. „2”, care se afla într-o situație simetrică (număr minim în ultima poziție), a făcut în schimb doar un pas către locația sa finală.
În general, un număr destinat poziției N și plasat inițial în poziția M , unde N < M , va necesita iterații M - N pentru a ajunge la celula de destinație. Dacă, pe de altă parte, M < N , deplasarea acestuia va fi în medie mai rapidă. Cazul particular în care numărul destinat primei poziții a matricei este în ultima corespunde unei situații de „cel mai rău caz” al bubbleortului, în care toate iterațiile N -1 ale algoritmului vor fi necesare pentru a obține matricea ordonată .
Shakersort
Denumirea de tip shaker (sortarea „un shaker”, care se referă la instrumentul pentru prepararea cocktailurilor ) sugerează destul de clar modul în care sortul shaker modifică sortarea cu bule. În loc să derulați întotdeauna matricea în aceeași direcție (favorizând astfel deplasările valorilor în acea direcție), sortarea shaker alternează pur și simplu o scanare înainte și una înapoi.
Toate optimizările și variantele prevăzute pentru sortarea cu bule sunt aplicabile, cu adaptările necesare, și la sortarea shaker.
Alte proiecte
-
Wikibooks conține implementări de tip Shaker
