Turinys
Rūšiuojant sąrašo elementų rinkinį, dažnai atliekama programavimo užduotis. Dažnai žmogus gali atlikti šią užduotį intuityviai. Tačiau kompiuterinė programa turi vadovautis tikslia instrukcijų seka, kad ją užbaigtų, ir ši seka vadinama algoritmu. Rūšiavimo algoritmas yra metodas, naudojamas tam tikroje eilėje išdėstyti neorganizuotų elementų sąrašą. Užsakymo seką nustato raktas. Yra keletas rūšiavimo algoritmų, kurie skiriasi pagal efektyvumą ir našumą. Kai kurie žinomi ir svarbūs šio tipo elementai: burbulų rūšiavimas, parinkimas, įterpimas ir greitas rūšiavimas.
Bubble rūšiuoti
„Bubble sort“ pakartotinai apsikeičia greta esančiais elementais, kurie yra netinkami, kol kiekvienas elementų sąrašas yra nuoseklus. Tokiu būdu elementai sąraše svyruoja pagal jų vertes, didžiausias (didėjančiosios tvarkos atveju), baigiasi kiekvieno iteracijos pabaigoje.
Pagrindinis šio algoritmo privalumas yra tas, kad jo įgyvendinimas yra paprastas ir pažįstamas. Be to, burbulų rūšiavimo metu elementai keičiami nenaudojant laikino saugojimo, todėl erdvės reikalavimas yra minimalus. Pagrindinis trūkumas yra tai, kad jame nėra gerų rezultatų, kai sąraše yra daug elementų. Taip yra todėl, kad tokiam užsakymui reikalingi n2 apdorojimo etapai kiekvienam elementų, kurie bus surūšiuoti, skaičiui n. Todėl akademiniam mokymui nurodomas burbulų rūšiavimas, bet ne realaus gyvenimo programoms.
Pasirinkimas rūšiuoti
Pasirinkimo rūšis pakartotinai perkelia elementų sąrašą, vienu metu pasirinkdama vieną elementą ir įdėjus ją į teisingą sekos padėtį.
Pagrindinis atrankos rūšies privalumas yra tas, kad jis veikia gerai mažame sąraše. Be to, kadangi tai yra vietos užsakymo algoritmas, jam nereikia laikinojo saugojimo, nei reikia, kad būtų išsaugotas originalus sąrašas. Pagrindinis trūkumas yra jo mažas efektyvumas dideliuose sąrašuose. Kaip burbulų rūšiavimas, kiekvienam n elementui reikia n2 žingsnių. Be to, jo veikimą lengvai veikia pradinė elementų eilė prieš atrankos procesą. Dėl šios priežasties šis tipo pasirinkimas tinka tik sąrašui, kuriame keli elementai yra atsitiktine tvarka.
Įterpimas rūšiuoti
Įterpimo rūšiavimas surūšiuoja sąrašą pakartotinai ir kiekvieną kartą įdeda netvarkingos sekos elementą į teisingą padėtį.
Pagrindinis įdėklų užsakymo privalumas yra jo paprastumas ir gerų rezultatų rodymas mažuose sąrašuose. Tai vietos užsakymo algoritmas, taigi erdvės reikalavimas yra minimalus. Trūkumas yra tai, kad jis neatlieka ir kitų rūšiavimo algoritmų. Su n2 veiksmais, kurių reikia norint dirbti, įterpti rūšiuoti neveikia su dideliais sąrašais. Tačiau tai ypač naudinga, kai pateikiami keli elementai.
Greitas rūšiavimas
Greitas rūšiavimas veikia su pasidalijimo ir užkariavimo principu. Pirma, jis suskirsto elementų sąrašą į du pogrupius, pagrįstus posūkio elementu. Visi pirmojo sąrašo elementai yra išdėstyti taip, kad jie būtų mažesni už sukamąjį, tuo tarpu visi antrojo sub-sąrašo elementai yra išdėstyti didesni už sukamąjį. Tas pats pertvaros ir organizavimo procesas atliekamas pakartotinai gautuose pogrupiuose, kol bus surengtas visas sąrašas.
Greitai rūšiuoti kai kurie laikomi geriausiais rūšiavimo algoritmais, nes yra labai naudingi efektyvumo požiūriu, nes jis gerai veikia su dideliu elementų sąrašu. Užsakant vietoje, nereikia papildomos saugojimo vietos. Mažas jo trūkumas yra tas, kad jo blogiausias veikimas yra panašus į kitų pirmiau 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 organizavimo būdą.
