Turinys
Užsakyti elementų rinkinį sąraše yra dažna užduotis programuojant. Dažnai žmogus šią užduotį gali atlikti intuityviai. Tačiau kompiuterinė programa, norėdama ją užbaigti, turi laikytis tikslios instrukcijų sekos, ir ta seka vadinama algoritmu. Užsakymo algoritmas yra metodas, naudojamas išdėstyti neorganizuotų daiktų sąrašą tam tikra tvarka. Užsakymo seka nustatoma raktu. Yra keletas rūšiavimo algoritmų, kurie skiriasi efektyvumu ir našumu. Keletas žinomų ir svarbių šio tipo yra: burbulų rūšiavimas, pasirinkimo rūšiavimas, įterpimo rūšiavimas ir greitas rūšiavimas.
Burbulas rūšiuoti
Burbulų rūšiavimas pakartotinai keičia gretimus elementus, kurie nėra tvarkingi, kol visas daiktų sąrašas yra nuoseklus. Tokiu būdu elementai sąraše sklando pagal savo vertes, o didžiausias (didėjančio rūšiavimo atveju) eina į pabaigą kiekvienos kartojimo pabaigoje.
Pagrindinis šio algoritmo pranašumas yra tas, kad jį lengva ir žinoma įgyvendinti. Be to, burbulų rūšiavime elementai keičiami vietomis nenaudojant laikinos saugyklos, todėl vietos poreikis yra minimalus. Pagrindinis trūkumas yra tai, kad jis neparodo gerų rezultatų, kai sąraše yra daug elementų. Taip yra todėl, kad tokio tipo rūšiavimui reikia n² apdorojimo žingsnių kiekvienam n elementų, kurie bus rūšiuojami, skaičiui. Todėl burbulų rūšis tinka akademiniam švietimui, bet ne realiam gyvenimui.
Pasirinkimo rūšiavimas
Pasirinkimo rūšiavimas pakartotinai ieško elementų sąraše, pasirinkdamas po vieną elementą ir nustatydamas jį teisingoje sekos vietoje.
Pagrindinis atrankos rūšiavimo privalumas yra tas, kad jis gerai veikia trumpą sąrašą. Be to, kadangi tai yra vietos užsakymo algoritmas, jam nereikia laikinos saugyklos, išskyrus tai, kas būtina originaliam sąrašui išsaugoti. Pagrindinis trūkumas yra mažas efektyvumas dideliuose sąrašuose. Kaip ir burbulų rūšiavimui, kiekvienam n elementui reikia n² žingsnių skaičiaus. Be to, jo našumui lengvai įtakoja pradinė elementų tvarka prieš rūšiavimą. Todėl šis pasirinkimo tipas tinka tik sąrašui, kuriame keli elementai yra atsitiktine tvarka.
Įterpimo rūšiavimas
Įterpimo rūšiavimas nuskaito sąrašą pakartotinai ir kiekvieną kartą įterpia elementą iš netvarkingos sekos į teisingą padėtį.
Pagrindinis rūšiavimo pagal įterpimą privalumas yra paprastumas, be to, rodomas geras našumas mažuose sąrašuose. Tai vietos užsakymo algoritmas, todėl vietos reikalavimas yra minimalus. Trūkumas yra tas, kad jis veikia ne taip gerai, kaip kiti rūšiavimo algoritmai. Kai darbui reikalingi n² žingsniai, įterpimo rūšiavimas taip pat neveikia dideliuose sąrašuose. Tačiau tai ypač naudinga su kelių elementų sąrašais.
Greitas rūšiavimas
Greitas rūšiavimas veikia padalijimo ir užkariavimo principu. Pirmiausia, jis suskirsto elementų sąrašą į du pogrupio elementus. Visi pirmojo antrinio sąrašo elementai yra išdėstyti taip, kad jie būtų mažesni už pasukimą, o visi antrojo antrojo sąrašo elementai yra išdėstyti taip, kad būtų didesni už suvestį. Gautuose antriniuose sąrašuose pakartotinai atliekamas tas pats skaidymo ir organizavimo procesas, kol sutvarkomas visas sąrašas.
Kai kurie mano, kad greitas rūšiavimas yra geriausias rūšiavimo algoritmas dėl savo reikšmingo efektyvumo pranašumo, nes jis gerai veikia su dideliu elementų sąrašu. Užsakant vietoje taip pat nereikia papildomos saugojimo vietos. Nedidelis trūkumas yra tas, kad blogiausias jo veikimas yra panašus į kitų aukščiau aprašytų algoritmų vidutinį našumą. Tačiau svarbu pažymėti, kad šis blogiausias atvejis yra labai retas. Apskritai greitas rūšiavimas sukuria efektyviausią ir plačiausiai naudojamą bet kokio dydžio sąrašo tvarkymo metodą.
