SKAITĪŠANAS KĀRTOŠANA — DATU STRUKTŪRU UN ALGORITMU APMĀCĪBAS — TECHCODEVIEW.COM

Kas ir skaitīšanas kārtošana?

Skaitīšana Kārtot ir nebalstīts uz salīdzināšanu šķirošanas algoritms, kas darbojas labi, ja ir ierobežots ievades vērtību diapazons. Tas ir īpaši efektīvs, ja ievades vērtību diapazons ir mazs salīdzinājumā ar kārtojamo elementu skaitu. Pamatideja aiz muguras Skaitīšana Kārtot ir saskaitīt biežums katru atšķirīgo elementu ievades masīvā un izmantojiet šo informāciju, lai novietotu elementus to pareizajās kārtotajās pozīcijās.

Kā darbojas skaitīšanas kārtošanas algoritms?

1. darbība:

Uzziniet, maksimums elements no dotā masīva.

Maksimālā elementa atrašana inputArray[]

2. darbība:

Inicializēt a countArray[] garuma max+1 ar visiem elementiem kā 0 . Šis masīvs tiks izmantots ievades masīva elementu notikumu glabāšanai.

Inicializēt countArray[]

3. darbība:

Iekš countArray[] , saglabā katra unikālā ievades masīva elementa skaitu to attiecīgajos rādītājos.
Piemēram: Elementu skaits 2 ievades masīvā ir 2. Tātad, veikals 2 pie indeksa 2 iekš countArray[] . Līdzīgi elementu skaits 5 ievades masīvā ir 1 , tātad veikals 1 pie indeksa 5 iekš countArray[] .

Saglabājiet katra elementa skaitu programmā countArray[]

4. darbība:

Uzglabājiet kumulatīvā summa vai prefiksa summa no elementiem countArray[] darot countArray[i] = countArray[i – 1] + countArray[i]. Tas palīdzēs ievietot ievades masīva elementus pareizajā rādītājā izvades masīvā.

Saglabājiet kumulatīvo summu countArray[]

5. darbība:

Atkārtojiet no ievades masīva beigām un tāpēc, ka, šķērsojot ievades masīvu no beigām, tiek saglabāta vienādu elementu secība, kas galu galā padara šo kārtošanas algoritmu stabils .

Atjaunināt outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .

Arī atjaunināt countArray[ inputArray[i] ] = countArray[ inputArray[i] ] - -.

6. darbība: Ja i = 6 ,

math.pow java

Atjaunināt outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Arī atjaunināt countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

InputArray[6] ievietošana pareizajā pozīcijā outputArray[]

7. darbība: Ja i = 5 ,

Atjaunināt outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Arī atjaunināt countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

InputArray[5] ievietošana pareizajā pozīcijā outputArray[]

8. darbība: Ja i = 4 ,

Atjaunināt outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Arī atjaunināt countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

InputArray[4] ievietošana pareizajā pozīcijā outputArray[]

9. darbība: Ja i = 3 ,

Atjaunināt outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Arī atjaunināt countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

InputArray[3] ievietošana pareizajā pozīcijā outputArray[]

10. darbība: Ja i = 2 ,

Atjaunināt outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Arī atjaunināt countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

InputArray[2] ievietošana pareizajā pozīcijā outputArray[]

11. darbība: Ja i = 1 ,

Atjaunināt outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Arī atjaunināt countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

InputArray[1] ievietošana pareizajā pozīcijā outputArray[]

12. darbība: Ja i = 0,

Atjaunināt outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Arī atjaunināt countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

InputArray[0] ievietošana pareizajā pozīcijā outputArray[]

Skaitīšanas kārtošanas algoritms:

Deklarē papildu masīvu countArray[] izmēra max(inputArray[])+1 un inicializējiet to ar 0 .
Traversa masīvs ievadmasīvs[] un kartējiet katru elementu ievadmasīvs[] kā indekss countArray[] masīvs, t.i., izpildīt countArray[inputArray[i]]++ priekš 0 <= i < N .
Aprēķiniet prefiksa summu katrā masīva indeksā inputArray [].
Izveidojiet masīvu outputArray[] izmēra N .
Traversa masīvs ievadmasīvs[] no beigām un atjaunināt outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Arī atjaunināt countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Zemāk ir aprakstīta iepriekš minētā algoritma ieviešana:

Java

import> java.util.Arrays;> public> class> CountSort {> >public> static> int>[] countSort(>int>[] inputArray) {> >int> N = inputArray.length;> >int> M =>0>;> >for> (>int> i =>0>

; i   M = Math.max(M, inputArray[i]);  }  int[] countArray = new int[M + 1];  for (int i = 0; i   countArray[inputArray[i]]++;  }  for (int i = 1; i <= M; i++) {  countArray[i] += countArray[i - 1];  }  int[] outputArray = new int[N];  for (int i = N - 1; i>= 0; i--) { izvadu masīvs[skaitsMasīvs[ievades masīvs[i]] - 1] = ievadmasīvs[i];  countArray[inputArray[i]]--;  } return outputArray;  } public static void main(String[] args) { int[] inputArray = {4, 3, 12, 1, 5, 5, 3, 9};  int[] outputArray = countSort(inputArray);  for (int i = 0; i System.out.print(outputArray[i] + ' '); } } }>

C#

using> System;> using> System.Collections.Generic;> class> GFG> {> >static> List<>int>>CountSort (saraksts<>int>>inputArray)> >{> >int> N = inputArray.Count;> >// Finding the maximum element of the array inputArray[].> >int> M = 0;> >for> (>int>

i = 0; i   M = Math.Max(M, inputArray[i]);  // Initializing countArray[] with 0  List countArray = jauns saraksts (jauns int[M + 1]);  // Katra inputArray[] elementa kartēšana kā masīva countArray[] indekss // priekš (int i = 0; i countArray[inputArray[i]]++; // Prefiksa summas aprēķināšana katrā masīva countArray indeksā // [] for (int i = 1; i<= M; i++)  countArray[i] += countArray[i - 1];  // Creating outputArray[] from the countArray[] array  List outputArray = jauns saraksts (jauns int[N]);  for (int i = N - 1; i>= 0; i--) { izvadu masīvs[skaitsMasīvs[ievades masīvs[i]] - 1] = ievadmasīvs[i];  countArray[inputArray[i]]--;  } return outputArray;  } // Draivera kods static void Main() { // Ievades masīva saraksts inputArray = jauns saraksts {4, 3, 12, 1, 5, 5, 3, 9};  // Izvades masīvu saraksts outputArray = CountSort(inputArray);  for (int i = 0; i Console.Write(outputArray[i] + ' '); Console.WriteLine(); } }>

Javascript

function> countSort(inputArray) {> >const N = inputArray.length;> >// Finding the maximum element of inputArray> >let M = 0;> >for>

(let i = 0; i   M = Math.max(M, inputArray[i]);  }  // Initializing countArray with 0  const countArray = new Array(M + 1).fill(0);  // Mapping each element of inputArray as an index of countArray  for (let i = 0; i   countArray[inputArray[i]]++;  }  // Calculating prefix sum at every index of countArray  for (let i = 1; i <= M; i++) {  countArray[i] += countArray[i - 1];  }  // Creating outputArray from countArray  const outputArray = new Array(N);  for (let i = N - 1; i>= 0; i--) { izvadu masīvs[skaitsMasīvs[ievades masīvs[i]] - 1] = ievadmasīvs[i];  countArray[inputArray[i]]--;  } return outputArray; } // Draivera kods const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Ievades masīva kārtošana const outputArray = countSort(inputArray); // Sakārtotā masīva drukāšana console.log(outputArray.join(' ')); //Šo kodu ir sagatavojis Utkarsh>>

jaukšana datu struktūrā

> 
    
   
      
  
     
      
     
    
 
     #include> using> namespace> std;> vector<>int>>countSort(vector<>int>>& inputArray)> {> >int> N = inputArray.size();> >// Finding the maximum element of array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i   M = max(M, inputArray[i]);  // Initializing countArray[] with 0  vector countArray(M + 1, 0);  // Katra inputArray[] elementa kartēšana kā masīva countArray[] indekss // priekš (int i = 0; i countArray[inputArray[i]]++; // Prefiksa summas aprēķināšana katrā masīva countArray indeksā // [] for (int i = 1; i<= M; i++)  countArray[i] += countArray[i - 1];  // Creating outputArray[] from countArray[] array  vector izvades masīvs(N);  for (int i = N - 1; i>= 0; i--) { izvadu masīvs[skaitsMasīvs[ievades masīvs[i]] - 1] = ievadmasīvs[i];  countArray[inputArray[i]]--;  } return outputArray; } // Draivera kods int main() { // Ievades masīva vektors inputArray = {4, 3, 12, 1, 5, 5, 3, 9};  // Izvades masīva vektors outputArray = countSort(inputArray);  for (int i = 0; i cout<< outputArray[i] << ' ';  return 0; }>  
 
 
 
    
 >
 
    
 >
 
 Python3
    
      
  
     
      
     
    
 
     def> count_sort(input_array):> ># Finding the maximum element of input_array.> >M>=> max>(input_array)> ># Initializing count_array with 0> >count_array>=> [>0>]>*> (M>+> 1>)> ># Mapping each element of input_array as an index of count_array> >for> num>in> input_array:> >count_array[num]>+>=> 1> ># Calculating prefix sum at every index of count_array> >for> i>in> range>(>1>, M>+> 1>):> >count_array[i]>+>=> count_array[i>-> 1>]> ># Creating output_array from count_array> >output_array>=> [>0>]>*> len>(input_array)> >for> i>in> range>(>len>(input_array)>-> 1>,>->1>,>->1>):> >output_array[count_array[input_array[i]]>-> 1>]>=> input_array[i]> >count_array[input_array[i]]>->=> 1> >return> output_array> # Driver code> if> __name__>=>=> '__main__'>:> ># Input array> >input_array>=> [>4>,>3>,>12>,>1>,>5>,>5>,>3>,>9>]> ># Output array> >output_array>=> count_sort(input_array)> >for> num>in> output_array:> >print>(num, end>=>' '>)>  
 
 
 
    
 >
 
    
 >
 
  Izvade  
 1 3 3 4 5 5 9 12>
 Skaitīšanas kārtošanas sarežģītības analīze:
      Laika sarežģītība    : O(N+M), kur    N    un    M    ir izmērs    ievadmasīvs[]    un    countArray[]    attiecīgi.  Sliktākais gadījums: O(N+M).
 Vidējais gadījums: O(N+M).
 Labākais gadījums: O(N+M).
 
 
     Palīgtelpa:    O(N+M), kur    N    un    M    ir aizņemtā telpa    outputArray[]    un    countArray[]    attiecīgi.
 
 Skaitīšanas kārtošanas priekšrocības:
  Skaitīšanas kārtošana parasti darbojas ātrāk nekā visi uz salīdzināšanu balstītie kārtošanas algoritmi, piemēram, sapludināšanas kārtošana un ātrā kārtošana, ja ievades diapazons atbilst ievades reižu skaitam.
 Skaitīšanas kārtošanu ir viegli kodēt
 Skaitīšanas kārtošana ir a    stabils algoritms    .
 
 Skaitīšanas šķirošanas trūkums:
  Skaitīšanas kārtošana nedarbojas ar decimāldaļām.
 Skaitīšanas kārtošana ir neefektīva, ja kārtojamo vērtību diapazons ir ļoti liels.
 Skaitīšanas kārtošana nav    Šķirošana uz vietas    algoritms, tas izmanto papildu vietu masīva elementu kārtošanai.

TechCodeview

Skaitīšanas kārtošana — datu struktūru un algoritmu apmācības

Kas ir skaitīšanas kārtošana?

Kā darbojas skaitīšanas kārtošanas algoritms?

Skaitīšanas kārtošanas algoritms:

Java

C#

Javascript

Python3

Skaitīšanas kārtošanas sarežģītības analīze:

Skaitīšanas kārtošanas priekšrocības:

Skaitīšanas šķirošanas trūkums: