Rūšiavimas - tai pagrindinė operacija, kurioje masyvo elementai yra išdėstyti tam tikroje konkrečioje eilutėje, siekiant padidinti jos paiešką. Paprastais žodžiais tariant, duomenys surūšiuoti taip, kad juos būtų lengva ieškoti.
Palyginimo diagrama
| Palyginimo pagrindas | Įterpimas Rūšiuoti | Pasirinkimas Rūšiuoti |
|---|---|---|
| Pagrindinis | Duomenys surūšiuoti įterpiant duomenis į esamą rūšiuojamą failą. | Duomenys surūšiuoti pasirinkdami ir padedant nuoseklius elementus į suskirstytą vietą. |
| Gamta | Stabili | Nestabili |
| Vykdomas procesas | Elementai yra žinomi iš anksto, o jų vieta yra ieškoma. | Vieta yra anksčiau žinoma, kai elementai ieškomi. |
| Skubūs duomenys | Įterpimo tvarka yra gyvas rūšiavimo metodas, kuris gali būti naudojamas nedelsiant. | Ji negali išspręsti tiesioginių duomenų, ji turi būti pradžioje. |
| Geriausias atvejo sudėtingumas | O (n) | O (n 2 ) |
Įterpimo rūšiavimo apibrėžimas
Įterpimo rūšiavimo darbai įterpiami į esamą rūšiuojamo failo reikšmių rinkinį. Jis sukuria suskirstytą masyvą vienu metu įterpdamas vieną elementą. Šis procesas tęsiasi tol, kol visa eilė surūšiuojama tam tikra tvarka. Pagrindinė įterpimo rūšies koncepcija yra įterpti kiekvieną elementą į atitinkamą vietą galutiniame sąraše. Įdėjimo rūšiavimo metodas taupo efektyvų atminties kiekį.
Įterpimo darbai
- Jis naudoja du masyvų rinkinius, kuriuose saugomi surūšiuoti duomenys ir kiti nerūšiuoti duomenys.
- Rūšiavimo algoritmas veikia tol, kol nerūšiuotų rinkinių elementai yra.
- Tarkime, kad masyve yra „n“ skaičių elementų. Iš pradžių surūšiuotame rinkinyje yra elementas su indeksu 0 (LB = 0). Likę elementai yra nerūšiuotame sąrašo skaidinyje.
- Pirmasis nerūšiuotos dalies elementas turi masyvo indeksą 1 (jei LB = 0).
- Po kiekvieno iteracijos jis pasirenka pirmąjį nerūšiuoto skaidinio elementą ir įterpia jį į tinkamą vietą surūšiuotame rinkinyje.
Įterpimo privalumai
- Lengvai įgyvendinama ir labai efektyvi, kai naudojama su mažais duomenų rinkiniais.
- Papildomas atminties vietos reikalavimas įterpti yra mažesnis (ty O (1)).
- Jis laikomas gyvo rūšiavimo metodu, nes sąrašas gali būti rūšiuojamas, kai gaunami nauji elementai.
- Tai greičiau nei kiti rūšiavimo algoritmai.
Pavyzdys :
Atrankos apibrėžimas Rūšiuoti
Pasirinkimas atlieka rūšiavimą, ieškodamas minimalios vertės skaičiaus ir pateikdamas jį į pirmąją arba paskutinę poziciją pagal užsakymą (didėjimo arba mažėjimo tvarka). Toliau tęsiamas minimalaus rakto paieškos ir tinkamos padėties paieškos procesas, kol visi elementai bus išdėstyti dešinėje padėtyje.
Pasirinkimo rūšiavimas
- Tarkime, ARR masyvas su N elementais atmintyje.
- Pirmajame leidime mažiausias raktas yra ieškomas kartu su jo padėtimi, tada ARR [POS] yra keičiamas su ARR [0]. Todėl ARR [0] yra rūšiuojama.
- Antrajame leidime vėl mažiausios vertės padėtis nustatoma N-1 elementų poskyryje. Pakeiskite ARR [POS] su ARR [1].
- Perėjime N-1 atliekamas tas pats procesas, siekiant surūšiuoti N elementų skaičių.
Pavyzdys :
Pagrindiniai skirtumai tarp įterpimo ir pasirinkimo rūšiavimo
- Įterpimo tvarka paprastai atlieka įterpimo operaciją. Priešingai, atrankos rūšys atlieka reikiamų elementų parinkimą ir išdėstymą.
- Manoma, kad įterpimo rūšis yra stabili, o atrankos rūšys nėra stabilus algoritmas.
- Įterpimo rūšiavimo algoritme elementai yra anksčiau žinomi. Priešingai, pasirinkimo rūšiuoti yra vieta iš anksto.
- Įterpimo rūšys yra gyvas rūšiavimo metodas, kuriame atvykstantys elementai yra iš karto surūšiuoti sąraše, o atrankos rūšys negali veikti gerai ir nedelsiant.
- Įterpimo rūšys geriausiu atveju turi O (n) veikimo laiką. Priešingai, geriausias atrankos rūšies sudėtingumo laikas yra O (n2).
Įterpimo sudėtingumas
Geriausias įterpimo rūšies sudėtingumas yra O (n) kartus, ty kai masyvas yra anksčiau surūšiuotas. Tuo pačiu būdu, kai masyvas yra surūšiuotas atvirkštine tvarka, pirmasis nesurūšiuoto masyvo elementas turi būti lyginamas su kiekvienu rūšiuojamo rinkinio elementu. Taigi, blogiausiu atveju, įterpimo rūšies eigos laikas yra kvadratinis, ty O (n2) . Vidutiniu atveju taip pat turi atlikti minimalius (k-1) / 2 palyginimus. Taigi vidutinis atvejis taip pat turi kvadratinį veikimo laiką O (n2).
Atrankos sudėtingumas Rūšiuoti
Kadangi atrankos, rūšiavimo darbas nepriklauso nuo masyvo elementų pirmosios eilės, todėl nėra daug skirtumo tarp geriausio ir blogiausio pasirinkimo rūšies sudėtingumo.
Atrankos rūšys pasirenka minimalų vertės elementą, atrankos procese tikrinamas visas „n“ elementų skaičius; todėl n-1 palyginimai atliekami pirmame leidime. Tada elementai keičiami. Panašiai ir antrajame leidime taip pat rasti antrą mažiausią elementą, todėl reikia nuskaityti likusius n-1 elementus ir procesas tęsiamas tol, kol visa masyvas surūšiuoti.
Taigi atrankos rūšies veikimo laiko sudėtingumas yra O (n2) .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
Išvada
Tarp abiejų rūšiavimo algoritmų, įterpimo rūšis yra greita, efektyvi, stabili, o atrankos rūšys veikia efektyviai tik tada, kai dalyvauja nedidelis elementų rinkinys arba sąrašas yra iš dalies surūšiuotas. Atrankos būdu atliktų palyginimų skaičius yra didesnis už atliktus judesius, o įterpimo metu elementų perkėlimo ar keitimo skaičius yra didesnis už atliktus palyginimus.
