Datu struktūras – Algoritmu kārtošana

Datu kopas kārtošana var izklausīties kā vienkāršs uzdevums, ņemot vērā to, ko esat jau apguvis jau no iepriekšējiem rakstiem šajā rakstu sērijā. Tomēr, iedziļinoties detaļās, tas var būt pārsteidzoši sarežģīti. Šajā rakstā jūs izpētīsiet

• kārtošanas algoritmus – sorting algorithms
• dažādas jums pieejamās šķirošanas metodes – Different sorting methods
• lineāro un bināro meklēšanas metodi
• kā arī darbības, kas saistītas ar šo pieeju ieviešanu,

un izpētīsiet to piedāvātās priekšrocības. Jūs arī uzzināsiet par darbībām, kas nepieciešamas ieviešanai,

• Selection – atlase,
• Insertion – ievietošanai
• Quicksort – ātrai šķirošanai,

un atklāsiet katras šķirošanas pieejas stiprās un vājās puses.

Šim izaicinājumam ir izstrādāti vairāki algoritmi un dažas datu struktūras, kas iepriekš tika apspriestas, piemēram, bināri koki – binary trees un heaps – čupas. Abas šīs datu struktūras ir izveidotas ar mērķi saglabāt datus sakārtotā veidā. Darbs ar sakārtotiem datiem vai iespēja kārtot savus datus var ievērojami ietaupīt laiku. Tāpēc elementu datu kopa, ko var pasūtīt, ir būtiski nepieciešama. Šī secība var būt

• Alphabeticaly – alfabētiskā,
• Sequentially – secīgā,
• Chronologically – hronoloģiskā secībā,
• By size of shape – pēc formas lieluma
• By hue of color – krāsas nokrāsas.

Faktiskā izmantotā metrika ir mazāk svarīga nekā fakts, ka tos var sakārtot augošā (Ascending) vai dilstošā (Descending) secībā.

Otrs apsvērums, kas tiek ņemts vērā, ir tas, vai secība ir mainīta, proti, pārkārtota (Permuted), vai arī tā ir veikta, izveidojot kopiju, vienlaikus saglabājot sākotnējo sarakstu. Atlases kārtošana ir agrīna pieeja šķirošanai, tā atdarina cilvēka pieeju problēmai. Pamatprincips ir ļoti vienkāršs.

Procesa attelojums GIF animācijā:

1. Sāciet ar meklēšanu sarakstā, lai identificētu mazāko elementu.
2. Pēc tam pārslēdziet to ar pirmo elementu, lai mazākais elements tiktu novietots augšpusē.
3. Tagad iepriekšējais pirmās vietas iemītnieks ir pārslēgts uz atbrīvoto vietu sarakstā.
4. To atkārto katram saraksta elementam, līdz saraksts ir sakārtots no mazākā līdz lielākajam.

Izpētīsim to piemērā:

Šajā diagrammā redzēsiet

• 35. elementu kas atrodās indekā, kurš atzīmēts ar nulli. Atlases kārtošanā tiek veikts salīdzinājums starp elementu ar indeksu nulli un katru masīva elementu, līdz tiek atrasts mazākais skaitlis.
• Tāpat 46. elements nākamajā vietā tiek salīdzināts ar katru elementu un šajā gadījumā tiek pārslēgts uz 6.
• Nākamais ir 36. elements, kas atrodas vietā index 2. Jūs ievērosiet, ka 9. elements indeksā 3 tiek uzskatīts par mazāko. Tomēr ir jāmeklē viss masīvs.

Procesa attelojums GIF animācijā:

Šis process tiek turpināts, līdz katrs elements ir sakārtots pēc izmēra. Mazākais pa kreisi, lielākais pa labi.

Vēl viena vienkārša pieeja šķirošanai ir ievietošanas kārtošana. Tā vietā, lai meklētu visus elementus, šī pieeja sākas ar pirmo divu elementu pārbaudi sarakstā. Pēc tam mazākais no abiem tiek pārvietots uz priekšu.

Tas tiek atkārtots katram elementam, kas tiek salīdzināts ar tajā esošo elementu, un pēc tam tiek veikta pārslēgšana pa kreisi, ja tiek konstatēts, ka tas ir mazāks.

2. elements tiek salīdzināts ar 4. elementu, kas ir mazāks, tāpēc notiek apmaiņa.

Pēc tam 2. elements tiek salīdzināts ar 1. elementu, kas ir lielāks, tāpēc salīdzinājumi vairs netiek veikti.

Pēc tam 3. elementu vispirms salīdzina ar 4. elementu, kas ir mazāks, tāpēc notiek apmaiņa.

Pēc tam 3. elements tiek salīdzināts ar 2. elementu, kas ir lielāks, tāpēc turpmāki salīdzinājumi netiek veikti.

Procesa attelojums GIF animācijā:

Izpētīsim piemēru. Ekrānā jūs pamanīsit skaitļu masīvu, kurā:

1. Pirmajam elementam 35 nav nekā lielāka pa kreisi, tāpēc tas paliek tur, kur tas ir.
2. Tad 46. elements tiek salīdzināts un arī tiek atstāts tur, kur tas ir.
3. Tālāk jūs redzat 36. elementu, kas tiek salīdzināts ar 1.indeksu, tas ir mazāks par 46, tāpēc tie tiek apmainīti.
4. Nakošajā darbībā jūs pamanīsiet 9. elementu, kas tiek salīdzināts ar 46, tāpēc tiek aizstāts ar 2. indeksa vietu.
5. Tas tiek tālāk salīdzināts ar 0. un 1. indeksa atrašanās vietu un atkal tiek apmainīts.
6. Pēc tam 4. indeksa vietā atrastais elements tiek salīdzināts ar 3. indeksa vietu un tiek apmainīts.
7. Tā tālāk tiek aizstāta ar 2. indeksa vietu un 1. indeksa vietu.
8. Salīdzina arī ar 0. indeksa vietu, bet, tā kā tā ir lielāka, tālāka kustība netiek veikta.

Procesa attelojums GIF animācijā:

Process tiek turpināts, virzoties no labās puses uz kreiso, līdz viss masīvs ir sakārtots. Gan ievietošanas, gan atlases kārtošana ir vienkāršas pieejas, kas darbojas pie vienkāršas paradigmas.

Quicksort ir sarežģītāka pieeja, ko ir sarežģītāk īstenot. Tomēr tas parāda daudz lielāku efektivitāti. Quicksort darbojas pēc šarnīra (pivot) principa. Algoritms masīvā izvēlas elementu kā rakursu. Pēc tam visi masīva vienumi, kas ir lielāki par šo vērtību, tiek pārvietoti pa labi no rakursa un visi elementi, kas ir mazāki par vērtību, un pārvietoti pa kreisi. Šo procesu atkārto abās rakursa pusēs, līdz visi vienumi ir sakārtoti. Izpētīsim to piemērā.

Šeit kā pagrieziena punkts ir atlasīts 9. elements. Izmantojot ātro kārtošanu, visi vienumi, kas ir mazāki par 9, tiek apmainīti pa kreisi un visi vienumi, kas ir lielāki par 9, tiek apmainīti pa labi. Tāpēc mazākie elementi tagad ir pārvietoti pa kreisi pēc šīs pirmās sadalīšanas.

Šajā piemērā šie mazākie elementi ir 6 un 3. Atkārtota tās pašas procedūras piemērošana iegūtajam masīvam tiek pārtraukta, kad tiek konstatēts, ka trīs ir vienīgais elements, kas nav sadalīts.

Tagad, ņemot vērtības, kas ir lielākas par sākotnēji atlasīto rakursu, jūs izvēlaties jaunu rakursu.

Šajā gadījumā tiek izvēlēts 36 un tiek veikta turpmāka elementu maiņa. Visbeidzot, atlikušās nešķirotās indeksa vietas tiek apmainītas attiecībā pret jaunu rakursu. Kad visi elementi ir sakārtoti, algoritms beidzas.

Ir daudzas papildu šķirošanas metodes, kuras var izmantot ar dažām pieejām, pat veidojot šo esošo hibrīdus. Praksē jūs, iespējams, nerakstītu savas implementācijas, jo katrā valodā ir lieliskas implementācijas. Mērķis ir parādīt, kā tie darbojas zem pārsega, lai jūs varētu izvēlēties labāko, saskaroties ar konkrēto problēmu. Tāpat kā datu struktūrās, nav viena šķirošanas algoritma, kas nodrošinātu vislabāko rezultātu katrā konkrētajā scenārijā. Katrai pieejai ir savi kompromisi, un tā dažās vidēs ir efektīvāka nekā citās.

Šajā rakstā esat izpētījis kārtošanas algoritmus un dažādas jums pieejamās šķirošanas metodes. Jūs esat arī uzzinājis par darbībām, kas jāveic atlases, ievietošanas un ātrās šķirošanas ieviešanai, un atklājāt katras šķirošanas pieejas stiprās un vājās puses.