Datu struktūras – Laika un telpas sarežģītība šķirošanas algoritmos

Jūs iepriekš uzzinājāt, ka laika un telpas sarežģītība ir līdzeklis koda efektivitātes novērtēšanai. Šajā rakstā jūs izpētīsiet laika un telpas sarežģītību gan atlases kārtošanas (selection sort ), gan ātrās kārtošanas algoritmos (quicksort algorithms). Šie ir izplatīti algoritmi, kas tiek izmantoti datu kārtošanai masīvā (Arrays).

Atlases kārtošana – Selection sort

Atlases kārtošana ir šķirošanas algoritms, kas darbojas pēc ļoti vienkārša principa. Izveidojiet masīvu uz vienumiem un atkārtojiet no kreisās puses uz labo. Sākot ar indeksa pirmo vietu, atkārtojiet visu masīvu un nomainiet šo vērtību ar zemāko vērtību, kas atrodas pa labi no šī vienuma. Atkārtojiet, līdz viss masīvs ir sakārtots.

Atlases šķirošanai ir:

• Sliktākā gadījuma laika sarežģītība ir O(N^2) – Worst
• Vidējā gadījuma laika sarežģītība ir O(N^2) – Average
• Labākā gadījuma laika sarežģītība ir O(N^2) – Best
• Telpas sarežģītība: O(1) – Auxiliary.

Lai veiktu atlases kārtošanu, veiciet šādas darbības:

• Atrodiet mazāko vērtību un samainiet to ar pirmo masīva vērtību
• Atrodiet otro mazāko vērtību un samainiet to ar otro vietu masīvā
• Atkārtojiet, līdz visas preces ir mainītas no pasūtītās no mazākās uz lielāko

Laika sarežģītība tiek noteikta saistībā ar veikto darījumu skaitu. Ņemot vērā sarakstu ar lielumu n, kompilatoram ir jāmeklē katrs saraksta ieraksts, lai identificētu mazāko vienumu, un pēc tam jāveic maiņa uz indeksa vietu 0. Algoritma pseidokods ir šāds.

for(i = 0; i < n-1; i++)
int min_index=List[i]
for(j=i+1; j<n;j++)
if(List[j] < List[min_index])
min_index=j
swap(List[i], List[min_index])

1.  rindiņā teikts, ka saraksta List garums ir jāmeklē n-1 reizes.
2.  rindiņa iestata pagaidu mainīgo, lai saglabātu zemāko vērtību.
3.  rindiņa ir iekšējā cilpa, kurai ir jāatkārto cilpa n-1 reizes.
4.  rindiņa pārbauda, vai pozīcijā List[j] atrastā vērtība ir mazāka par pašreizējo zemāko vērtību. Ja tā, šī elementa atrašanās vieta tiek reģistrēta. Katras iekšējās cilpas beigās vērtība, kas konstatēta kā zemākā, tiek apmainīta ar pozīciju i indeksā, i tiek palielināta un procedūra sākas no jauna.

Vienmēr pārbaudiet nākamo vienumu sarakstā, līdz ir pārbaudīts katrs vienums.

Novērtējot šo algoritmu, ir jāņem vērā četri apsvērumi.

• Sliktākais scenārijs: cik daudz salīdzinājumu tiek veikts, ņemot vērā sarakstu, kas sakārtots apgrieztā secībā? Iekšējai un ārējai cilpai būs jādarbojas n reizes, lai varētu noteikt, ka sliktākais gadījums = O(n^2).
• Vidējais salīdzinājums: neatkarīgi no saraksta secības katrs vienums ir jāsalīdzina ar vidējo lielumu = O(n^2).
• Labākais salīdzinājums: tiek sniegts sakārtots salīdzinājumu skaits. Atkal, neatkarīgi no saraksta vienumiem, katrs vienums ir jāpārbauda, tāpēc labākajā gadījumā = O(n^2).
• Visbeidzot, kāda ir šīs pieejas vietas sarežģītība? Tā kā tiek veikta apmaiņa uz vietas, pagaidu masīvs nav nepieciešams. Ir trīs pagaidu mainīgie lielumi i, j un min_index; tomēr tie nav atkarīgi no saraksta lieluma. Tātad attēls dubulto sarakstu, un telpas sarežģītība attiecīgi nepalielinās. Tāpēc telpas sarežģītība = O(1).

Novērtējot laika sarežģītību, ir jāņem vērā, kas notiks, ja saraksts tiks dubultots. Protams, iekšējās un ārējās cilpas būs jāpalielina bez iterācijas, lai tās atbilstu papildu elementiem sarakstā. Līdz ar to var secināt, ka laika sarežģītība palielinās līdz ar izmēru.

ātrās kārtošanas algoritmos – quicksort algorithms

Ātrā šķirošana ir šķirošanas pieeja, kurā tiek izmantota “skaldi un valdi” metodoloģija. Ņemot vērā vienumu masīvu, masīvā tiek noteikta vieta, kur sadalīt masīvu, un to sauc par pagrieziena punktu (pivot point). Visas vērtības, kas ir lielākas par šo punktu, iet pa labi, un visas vērtības, kas ir mazākas par šo punktu, iet pa kreisi. Šajā darbībā jums ir divi masīvi. Šiem masīviem tiek piemērots tas pats process, līdz vairs nav kārtojamo elementu.

Quicksort ir:

• Sliktākā gadījuma laika sarežģītība O(n^2) – Worst
• Vidējā gadījuma laika sarežģītība O(n log n) – Average
• Labākā gadījuma laika sarežģītība O(n log n) – Best
• Telpas sarežģītība O(n) – Space complexity

Lai veiktu ātro kārtošanu, veiciet tālāk norādītās darbības.

• Izvēlieties punktu sarakstā, uz kuru pagriezties.
• Sadaliet sarakstu divos sarakstos: vienumi pa kreisi no rakursta un vienumi pa labi.
• Iestatiet mainīgos i, lai tie atkārtojas no kreisās puses uz labo pa kreisi no rakursa. Iestatiet mainīgo j, lai tas atkārtojas no labās uz kreiso rakursa kreisajā pusē.
• Kreisajā pusē esošie mainīgie i meklē vērtību, kas ir lielāka vai vienāda ar rakursu. Labajā pusē esošie mainīgie j meklē vērtību, kas ir mazāka vai vienāda ar rakursu.
• Ja j < i, vērtības šajās indeksa vietās tiek apmainītas, to atkārto, līdz i un j sastopas pagrieziena punktā.
• Sadaliet saraksta vērtības divos sarakstos, vienu pa kreisi un otru pa labi no rakurstara. Atkārtojiet procesu katrā no iegūtajiem masīviem.
• Rekursīvi pielietojiet algoritmu.

Tālāk norādītais pseidokods ātrai šķirošanai tiek veikts rekursīvi.

• Sākot no vistālāk kreisā elementa, tiek pārbaudīts katrs nākamais elements, un, ja tiek konstatēts, ka tas ir mazāks, tas tiek apmainīts.
• 3. rinda izsauc nodalījuma metodi, kas sākas 8. rindā.
• 10. rindiņa nosaka nozīmīgāko elementu, kas jāievieto saraksta labajā pusē. 10. rindā ir iestatīts mainīgais i, kas jāpiešķir mazākā elementa indeksam. Mainīgais j tiek izmantots, lai pārbaudītu elementus pa labi, no kuriem veikt salīdzinājumu ar pašreizējo mazāko elementu.
• 12. rinda nosaka, vai ir jāveic mijmaiņas darījums, mazākam elementam labajā pusē būs jāpārvieto uz pašreizējo indeksa pozīciju. 4. rinda ir paredzēta kreisā masīva kārtošanai.
• 5. rinda paredzēta pareizā masīva kārtošanai. Katrā iterācijā kārtojamā masīva lielums tiek samazināts uz pusi. Masīvi nepārtraukti sadalīsies, līdz apakšmasīvās paliek tikai viens elements. Sadalījuma izsaukšanas rezultāts noteiks pašreizējā elementa atrašanās vietu. Šī atrašanās vieta tiek palielināta un atkārtota, līdz katrs elements atrodas savā dabiski sakārtotajā pozīcijā.

QuickSort(List, low, high)
        if(low<high) 
pivot=partition(List, high, low)
QuickSort(List, how, pivot-1)
QuickSort(List, pivot+1, high) 


Partition(List,high,low)
        pivot=arr[high]
        i=(low-1)
        for j = low; j <= high-1; j++) 
if(List[j] < pivot)
        i++
        swap(List[i], List[j]) 
        swap(arr[i+1], List[j]) 
        return I + 1