Sortiraj po direktnom uključivanju, baš kao sortiraj po metodi jednostavan izbor, obično se koristi za nizove koji ne sadrže duple elemente.
Sortiranje ovom metodom se izvodi uzastopno korak po korak. On k-tom koraku, smatra se da je dio niza koji sadrži prvi k– 1 element, već naručen, tj.
Dalje, morate uzeti k-ti element i odaberite mjesto za njega u sortiranom dijelu niza tako da nakon njegovog umetanja red ne bude narušen, odnosno potrebno je pronaći takvo da . Zatim morate umetnuti element a(k) na pronađenu lokaciju.
Sa svakim korakom, sortirani dio niza se povećava. Da biste izvršili kompletno sortiranje, morate pokrenuti n– 1 korak.
Ostaje odgovoriti na pitanje kako tražiti odgovarajuće mjesto za element X. Uradimo sledeće: pogledaćemo elemente koji se nalaze sa leve strane X(odnosno one koje su već naručene), krećući se prema početku niza. Stavke je potrebno pogledati a(j), j promjene od k– l do 1. Takvo pretraživanje će se završiti kada se ispuni jedan od sljedećih uslova:
Pronađen element koji ukazuje na potrebu umetanja X između i a(j).
Dosegnut je lijevi kraj uređenog dijela niza, pa umetnite X na prvom mjestu.
Dok se ne ispuni jedan od ovih uslova, pomeraćemo posmatrane elemente za 1 poziciju udesno, usled čega će se osloboditi prostor u sortiranom delu ispod X.
Tehnika sortiranja je ilustrovana u tabeli 2:
Tabela 2 – Primjer sortiranja korištenjem direktnog uključivanja
Inicijalno uređena sekvenca se sastoji od 1. elementa 9. Element A( 2) =5 je prvi od neuređenog niza i 5< 9, поэтому ставится на его место, а 9 сдвигается вправо. Теперь упорядоченная последовательность состоит из двух элементов 5, 9. Элемент A( 3) =15 neuređenog niza je veći od svih elemenata uređenog niza, pa ostaje na svom mjestu i u sljedećem koraku uređeni niz se sastoji od 5, 9, 15, a element koji se razmatra je 6. Proces se nastavlja sve dok sekvenca postaje uređena.
shaker sort
Metoda mjehurića omogućava tri jednostavna poboljšanja. Prvo, ako u nekom koraku nije izvršena razmjena, tada se algoritam može prekinuti. Drugo, možete zapamtiti najmanju vrijednost indeksa niza, za koju su permutacije izvršene u trenutnom koraku. Očigledno je da je gornji dio niza do elementa s ovim indeksom već sortiran, a u sljedećem koraku možete prestati s upoređivanjem vrijednosti susjednih elemenata kada se postigne takva vrijednost indeksa. Treće, metoda mjehurića radi nejednako za "lake" i "teške" vrijednosti. Laka vrijednost dolazi na pravo mjesto u jednom koraku, a teška se spušta prema pravom mjestu za jednu poziciju na svakom koraku.
Metoda ShakerSort zasniva se na ovim zapažanjima. Kada se primeni, smer uzastopnog pretraživanja se menja u svakom sledećem koraku. Kao rezultat toga, u jednom koraku sljedeći najlakši element "ispliva", a u sljedećem koraku sljedeći najteži element "potopi". Primjer sortiranja shakerom prikazan je u tabeli 3.
Tabela 3 - Primjer sortiranja shakerom
Sortiranje niza pomoću inkluzija sa smanjenjem udaljenosti (Shell metoda)
D. Shell je predložio poboljšanje sortiranja korištenjem direktnog uključivanja.
Ideja metode: svi elementi niza su podijeljeni u grupe na način da svaka grupa uključuje elemente razmaknute jedan od drugog određenim brojem pozicija L. Elementi svake grupe su sortirani. Nakon toga, svi elementi se ponovo kombinuju i sortiraju u grupe, dok se razmak između elemenata smanjuje. Proces se završava nakon što se izvrši redoslijed elemenata s razmakom između njih 1.
Primjer sortiranja po Shell metodi prikazan je u tabeli 4.
Tabela 4 - Primjer sortiranja po Shell metodi
Prvo, razmotrite opciju kada je početna vrijednost L jednaka je polovini broja elemenata u nizu, a svaka naredna vrijednost je upola manja od prethodne. Imajte na umu da se razmjenjuju elementi koji su razdvojeni veličinom koraka. Ako pri upoređivanju 2 elementa ne dođe do zamjene, tada se mjesta upoređenih elemenata pomiču udesno za jednu poziciju. Ako je došlo do razmjene, tada se odgovarajući upoređeni elementi pomjeraju za L.
Podijeljeno sortiranje (brzo sortiranje)
Metodu particionog sortiranja predložio je Charles Hoare. Ova metoda je razvoj jednostavne metode razmjene i toliko je efikasna da je postala poznata kao metoda brzog sortiranja - "Quicksort".
Osnovna ideja algoritma je to nasumično odabran je neki element niza x, nakon čega se niz skenira slijeva dok se ne naiđe na element a(i) takav da a(i) > x a zatim se niz pretražuje s desne strane sve dok se ne naiđe na element a(i) takav da a(i)< x. Ova dva elementa se zamjenjuju, a proces gledanja, poređenja i razmjene se nastavlja sve dok ne dođemo do elementa x. Kao rezultat toga, niz će biti podijeljen na dva dijela - lijevi, u kojem će vrijednosti ključa biti manje od x, a desni sa ključnim vrijednostima većim od x. Proces se zatim nastavlja rekurzivno za lijevi i desni dio niza sve dok svaki dio ne sadrži tačno jedan element. Rekurzija se može zamijeniti iteracijama ako se sjećate odgovarajućih indeksa niza.
Proces sortiranja niza brzim metodom prikazan je u tabeli 5.
Tabela 5 - Primjer brzog sortiranja
Sortiranje je raspored podataka u memoriji na pravilan način prema odabranom parametru. Regularnost se smatra povećanjem (smanjenjem) vrijednosti parametra od početka do kraja niza podataka.
Prilikom obrade podataka važno je poznavati informacijsko polje podataka i njihov smještaj u mašini.
Razlikujte unutrašnje i eksterno sortiranje:
Interno sortiranje - sortiranje ram memorija;
Eksterno sortiranje - sortiranje u eksternoj memoriji.
Ako zapisi koji se sortiraju zauzimaju veliku količinu memorije, njihovo premještanje je skupo. Kako bi se oni smanjili vrši se sortiranje tabela ključnih adresa, odnosno rade permutaciju pokazivača, a sam niz se ne pomiče. Ovo - metoda sortiranja adresne tablice.
Prilikom sortiranja mogu se pojaviti isti ključevi. U ovom slučaju, poželjno je nakon sortiranja iste ključeve rasporediti istim redoslijedom kao u izvorni fajl. Ovo - stabilna sorta.
Razmotrit ćemo samo vrste koje ne koriste dodatnu RAM memoriju. Takve vrste se zovu "na istom mjestu".
Efikasnost sortiranja se može posmatrati prema nekoliko kriterijuma:
Vrijeme utrošeno na sortiranje;
Količina RAM-a potrebna za sortiranje;
Vrijeme koje programer provede u pisanju programa.
Izdvajamo prvi kriterijum. Može se uzeti u obzir ekvivalent vremena utrošenog na sortiranje broj poređenja I broj pokreta prilikom sortiranja.
Redoslijed broja poređenja i poteza tokom sortiranja je unutar
Od O (n log n) do O (n 2);
O(n) je idealan i nedostižan slučaj.
Postoje sljedeće metode sortiranja:
Stroge (direktne) metode;
Poboljšane metode.
Stroge metode:
Način direktnog povezivanja;
Metoda direktne selekcije;
metoda direktne zamjene.
Efikasnost strogih metoda je otprilike ista.
Direktno uključivanje Sort
Elementi se mentalno dijele na gotov niz a 1,...,a i-1 i originalni niz.
U svakom koraku, počevši od i = 2 i povećavajući svaki put za jedan, iz originalnog niza se izdvaja i-ti element i pomaknut na gotovi niz, dok je umetnut na pravo mjesto.
Suština algoritma je sljedeća:
za i = 2 do n
X = a(i)
Pronalazimo mjesto među a (1) ... a (i) da uključimo x
sljedeći i
Postoje dva algoritma za sortiranje direktnog uključivanja. Prvo - bez barijere
Algoritam za sortiranje direktnog uključivanja bez barijera
za i = 2 do n
X = a(i)
Za j = i - 1 sve do 1
Ako je x< a(j)
Tada je a(j + 1) = a(j)
Inače idite na L
endif
Sljedeći j
L: a(j + 1) = x
sljedeći i
povratak
Nedostatak gornjeg algoritma je kršenje tehnologije strukturiranog programiranja, u kojem je nepoželjno koristiti bezuvjetne skokove. Ako je unutrašnja petlja organizirana kao while petlja, tada je potrebno postaviti „barijeru“, bez koje, uz negativne vrijednosti ključeva, dolazi do gubitka značaja i „zamrzavanja“ računara.
Algoritam za sortiranje direktnog uključivanja barijere
za i = 2 do n
X = a(i)
A(0) = x (a(0) - barijera)
J = i - 1
Dok je x< a(j) do
A(j+1) = a(j)
J = j - 1
Endwhile
A(j+1) = x
sljedeći i
povratak
Efikasnost algoritma direktnog uključivanja
Broj ključnih poređenja Ci na i-tom skriningu je najviše i-1, najmanje - 1; ako pretpostavimo da su sve permutacije od N ključeva jednako vjerovatne, tada je prosječan broj poređenja = i/2. Broj transfera je Mi=Ci+3 (uključujući barijeru). Minimalne procjene se javljaju u slučaju već uređenog početnog niza elemenata, dok se najgore procjene javljaju kada su inicijalno raspoređeni obrnutim redoslijedom. U određenom smislu, sortiranje po inkluziji pokazuje zaista prirodno ponašanje. Jasno je da gornji algoritam opisuje stabilan proces sortiranja: redoslijed elemenata sa jednakim ključevima ostaje nepromijenjen.
Broj poređenja u najgorem slučaju, kada je niz sortiran na suprotan način, C max = n (n - 1) / 2, odnosno - O (n 2). Broj permutacija M max = C max + 3(n-1), tj. - O (n 2). Ako je niz već sortiran, tada je broj poređenja i permutacija minimalan: C min = n-1; Mmin = =3(n-1).
Sortiraj po direktnoj razmjeni (svrstavanje u mehurićima)
Ovaj odjeljak opisuje metodu gdje je razmjena dva elementa najkarakterističnija karakteristika procesa. Algoritam za direktnu razmjenu naveden u nastavku temelji se na upoređivanju i mijenjanju mjesta za par susjednih elemenata i nastavku ovog procesa dok se svi elementi ne poređaju.
Iteriramo niz niz, svaki put pomjerajući najmanji element preostalog niza na lijevi kraj niza. Ako posmatramo nizove kao vertikalne, a ne horizontalne konstrukcije, onda se elementi mogu tumačiti kao mehurići u bačvi s vodom, pri čemu težina svakog odgovara njegovom ključu. U ovom slučaju, sa svakim prolazom, jedan mjehur se takoreći podiže do nivoa koji odgovara njegovoj težini (pogledajte ilustraciju na donjoj slici).
C min = n - 1, red O(n),
i uopšte nema pokreta.
Komparativna analiza metoda direktnog sortiranja pokazuje da je razmjensko "sortiranje" u svom klasičnom obliku križ između sortiranja korištenjem uključivanja i korištenjem selekcija. Ako su gore navedena poboljšanja napravljena na njemu, onda za dovoljno uređene nizove sortiranje mehurića čak ima prednost.
Ova metoda je uobičajeno poznata kao "bubble sort".
Algoritam metode direktne razmjene
za j = n do i korak -1
ako a(j)< a(j - 1) then
U našem slučaju dobili smo jedan prolaz u praznom hodu. Da ne biste ponovo pregledavali elemente, a samim tim i radili poređenja, trošeći vrijeme na ovo, možete upisati polje za potvrdu fl, koji ostaje u vrijednosti false, ako tokom sljedećeg prolaza neće biti izvršena zamjena. U algoritmu ispod, dodaci su označeni podebljanim slovima.
fl = istina
ako je fl = false onda return
fl=false
za j = n do i korak -1
ako a(j)< a(j - 1) then
fl = istina
Poboljšanje sortiranja mjehurićima je sortiranje s tresačom, gdje se nakon svakog prolaza smjer mijenja u unutrašnjoj petlji.
Efikasnost algoritma direktne razmjene sortiranja
Broj poređenja C max = n(n-1)/2, red O(n 2).
Broj pokreta M max = 3C max = 3n (n-1) / 2, reda O (n 2).
Ako je niz već sortiran i algoritam zastavice je primijenjen, onda je dovoljan samo jedan prolaz i tada dobijamo minimalni broj poređenja
Potrebne definicije i klasifikacija vrsta.
Sortiranje. Potrebne definicije i klasifikacija vrsta. Vrste direktnog uključivanja i selekcije. Njihova efikasnost
Sortiranje je raspored podataka u memoriji u pravilnom obliku po njihovim ključevima. Dakle, prilikom obrade podataka važno je poznavati informacijsko polje podataka i njihov smještaj u mašini. Stoga razlikuju interni(razvrstavanje u RAM) i eksterno sortiranje(razvrstavanje u eksternu memoriju). Regularnost raspored elemenata je povećanje (smanjenje) vrijednosti ključa od početka do kraja u nizu.
Ako zapisi koji se sortiraju zauzimaju veliku količinu memorije, njihovo premještanje je skupo. Da biste ih smanjili, koristite metod sortiranja adresne tablice. Ova metoda se koristi u tabela ključnih adresa. Izvodi se permutacija pokazivača, tj. Sam niz se ne pomera. Prilikom sortiranja mogu se pojaviti i isti ključevi. U ovom slučaju, poželjno je rasporediti iste ključeve nakon sortiranja istim redoslijedom kao u izvornom fajlu. Ovaj princip se koristi za održivo sortiranje.
Efikasnost sortiranja se može posmatrati iz nekoliko kriterijuma:
1) vrijeme utrošeno na sortiranje;
2) količina RAM-a potrebna za sortiranje;
3) vrijeme koje je programer potrošio na pisanje programa.
Vrijeme provedeno u sortiranju proporcionalno je broju poređenja u sortiranju i broju pomicanja elementa.
Vjeruje se da redoslijed uporednog broja tokom sortiranja može biti u rasponu od o(nlogn) prije o(n 2), Gdje o(n)- idealan i nedostižan slučaj.
Metode sortiranja se mogu klasificirati ovako:
1) stroge (direktne) metode(njihova efikasnost je otprilike ista):
· direktnu vezu;
· direktan izbor;
· direktnu razmenu;
2) poboljšane metode.
U životu je princip ovakvog sortiranja prisutan pri igranju pasijansa, čišćenju stana, kada je potrebno složiti gomilu pomiješanih stvari u odgovarajućem redoslijedu itd. Vrlo prirodan način sortiranja primijenjen je i na sređivanje podataka.
Elementi su mentalno podijeljeni u gotov niz a 1 ,...,a i-1 i originalni niz. U gotovom nizu, elementi su raspoređeni u datom redoslijedu (u silaznom ili rastućem redoslijedu). A u početnom nizu postoje elementi koje je potrebno sortirati. U svakom koraku, elementi originalne sekvence se smanjuju za jedan, a gotova sekvenca se povećava za jedan. To je zbog činjenice da se iz originalne sekvence izdvaja ja- element i prenosi se u gotovu sekvencu, dok se ubacuje na pravo mjesto među elemente gotovog niza.
Razmotrimo primjer direktnog sortiranja uključivanjem na niz elemenata: 10, 3, 11, 8, 2, 15, 44, 9 (Tablica 11.1). Potrebno ga je sortirati uzlaznim redoslijedom.
Prvo, gotova sekvenca nema elemenata. U prvom koraku, prvi element originalne sekvence, 10, postaje prvi element završene sekvence. Zatim drugi korak: element 3 iz originalnog niza se stavlja u gotov. To se dešava ovako. Ako je element veći od 10, onda ostaje na svom mjestu, a ako je manji, tada se 10 pomiče za jedan udesno i na njegovo mjesto se postavlja element. Od 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, onda 11 ostaje na mjestu. Originalni niz je sada: 8, 2, 15, 44, 9. Sljedeći koraci se rade na isti način.
Tabela 11.1
Kako radi direktno sortiranje
Broj koraka u ovom sortiranju (tabela 11.1) jednak je broju elemenata u sortiranom nizu, tj. 8 koraka = 8 elemenata.
Postoje dva načina za implementaciju ovu metodu- ovo je bez barijere (Sl. 11.1) i sa barijerom (Sl. 11.2).
Metoda direktnog uključivanja može se poboljšati pronalaženjem mjesta za umetnuti zapis u uređenoj podtabli pomoću metode binarni (dihotomno, binarno, logaritamsko) traži. Ova modifikacija metode umetanja se zove umetak sa binarnim uključivanjem.
Razmislite j‑ti korak sortiranja ( j=2, 3, ..., n). Ako K[ j]>= K[ j-1] , onda red nije prekršen i treba da idemo na R[ j+1]– oh records. Ako K[ j]< K[ j-1] , To R[ j] pohranjeno u radnoj varijabli (Rab= R[ j]) a za njega se traži mjesto u naređenom dijelu tabele - u podtabelu. Označimo donju granicu indeksa ove podtabele kao ng, vrh - kroz vg (prvobitno ng=1. vg=j-1).
Prema binarnom pretraživanju ključ K[ j] dotični zapisnik R[ j] prvo treba uporediti sa ključem K[ i] evidencije R[ i] , koji se nalazi u sredini naručene podtabele (i=(ng+vg) div 2). Ako K[ j]> K[ i], zatim se odbacuje (tj. više se ne razmatra) lijeva strana podtabele - zapisi s manjim ključevima (ng= i+1) . Ako K[ j]< K[ i] , tada se desna strana podtabele odbacuje - zapisi sa velikim ključevima (vg= i-1). Pretraga se nastavlja u ostatku podtabele. Proces dijeljenja dijelova podtabele na pola nastavlja se sve dok se ne dogodi jedna od sljedećih situacija:
1) K[ j]= K[ i] , dakle, (i+1)--ta pozicija je lokacija za dotični unos. Pomerimo zapise R[ i+1], R[ i+2], …, R[ j-1] jednu poziciju udesno i tako oslobodite prostor za umetanje (R[ i+1]= Rab).
2) K[ j]<> K[ i] I ng> vg – ključevi se ne podudaraju, a dužina posljednje podtabele je 1. U ovom slučaju, tačka umetanja je pozicija ng, pa zapisi R[ ng], R[ ng+1], … , R[ j-1] treba pomaknuti za jednu poziciju udesno (R[ ng]= Rab) .
Algoritam binarnog pretraživanja detaljno je opisan u odjeljku "Pretraga dihotomnih koincidencija".
Pogledajmo primjer j-ti korak sortiranja (određuje se mjesto zapisa sa ključem 9; j=7, K[ j]=9 ):
Prosječan broj poređenja za ovu metodu je nlog 2 (n).
Dvostruka metoda umetanja
Dvostruka metoda umetanja je modifikacija metode direktnog umetanja; poboljšava performanse sortiranja.
Za implementaciju ove metode potrebna je dodatna količina memorije, jednaka količini koju zauzima tablica koja se sortira (nazovimo je izlaznom zonom T). Na prvom koraku sortiranja u sredini izlaznog područja (pozicija m=(div 2)+1) postavlja se prvi zapis tabele R. Ostale pozicije T dok je prazna. U narednim koracima sortiranja, ključ sljedećeg zapisa R[ j] (j=2, 3, …, n) se upoređuje sa ključem za snimanje T[ m] i, u zavisnosti od rezultata poređenja, mesto za R[ j] pronađeno u T lijevo ili desno od T[ m] metoda umetanja. U ovom slučaju, brojevi krajnje lijeve ( l) i krajnje desno ( r) elemenata dovedenih u izlaznu zonu. Krajnje vrijednosti l I r jednaka 1 I n respektivno.
U algoritmu treba uzeti u obzir i sljedeće situacije:
ključ za snimanje R[j] manje od ključa za pisanje T[m], Ali l=1;
ključ za snimanje R[j] više ključa za pisanje T[m], Ali r=n.
U ovim slučajevima, za umetanje zapisa R[ j] potrebno je pomjeriti zapise podtabele zajedno sa zapisom T[ m] desno ili lijevo (koristeći metodu direktnog umetanja).
Pogledajmo primjer sortiranja pomoću ove metode.
Neka početni slijed ključeva tablice izgleda ovako:
24, 1, 28, 7, 25, 3, 6, 18, 8 (n=9, m=(n div 2)+ 1=5)
|
Broj koraka |
Izlazna zona |
|||||||||
Učitavanje...