Šajā apmācībā jūs uzzināsiet, kā darbojas kārtošana. Jūs atradīsit arī darba kārtības skaitīšanas piemērus C, C ++, Java un Python.
Skaitīšanas kārtošana ir šķirošanas algoritms, kas kārto masīva elementus, skaitot katra masīvā esošā unikālā elementa gadījumu skaitu. Skaits tiek glabāts palīgmasīvā, un kārtošana tiek veikta, kartējot skaitīšanu kā palīgmasīva indeksu.
Kā darbojas kārtošanas skaitīšana?
- Uzziniet maksimālo elementu (ļaujiet tam būt
max) no norādītā masīva.
Dots masīvs - Inicializējiet masīva garumu
max+1ar visiem elementiem 0. Šo masīvu izmanto, lai saglabātu masīvā esošo elementu skaitu.
Count masīvs - Glabājiet katra elementa skaitu attiecīgajā
countmasīva indeksā
Piemēram: ja 3. elementa skaits ir 2, tad 2 tiek glabāts skaitīšanas masīva 3. pozīcijā. Ja elementā "5" masīvā nav, tad 0 tiek saglabāts 5. pozīcijā.
Katra saglabātā elementa skaits - Uzglabāt skaitīšanas masīva elementu kumulatīvo summu. Tas palīdz ievietot elementus pareizajā sakārtotā masīva indeksā.
Kumulatīvais skaits - Atrodiet katra sākotnējā masīva elementa indeksu skaitīšanas masīvā. Tas dod kumulatīvo skaitu. Novietojiet elementu indeksā, kas aprēķināts, kā parādīts attēlā.
Skaitīšanas kārtība - Pēc katra elementa novietošanas pareizajā stāvoklī samaziniet to skaitu par vienu.
Kārtošanas algoritma skaitīšana
countingSort (masīvs, lielums) max <- atrodiet masīva lielāko elementu, inicializējiet skaitīšanas masīvu ar visām nulles vērtībām j <- 0, lai atrastu lielumu, atrodiet katra unikālā elementa kopējo skaitu un saglabājiet skaitli j-tajā indeksā skaita masīvā i <- 1 lai maksimāli atrastu kumulatīvo summu un saglabātu to pašā skaitīšanas masīvā j <- izmērs uz leju līdz 1, atjaunojiet elementus, lai katra elementa masīva samazinājuma skaits tiktu atjaunots par
Python, Java un C / C ++ piemēri
Python Java C C ++ # Counting sort in Python programming def countingSort(array): size = len(array) output = (0) * size # Initialize count array count = (0) * 10 # Store the count of each elements in count array for i in range(0, size): count(array(i)) += 1 # Store the cummulative count for i in range(1, 10): count(i) += count(i - 1) # Find the index of each element of the original array in count array # place the elements in output array i = size - 1 while i>= 0: output(count(array(i)) - 1) = array(i) count(array(i)) -= 1 i -= 1 # Copy the sorted elements into original array for i in range(0, size): array(i) = output(i) data = (4, 2, 2, 8, 3, 3, 1) countingSort(data) print("Sorted Array in Ascending Order: ") print(data)
// Counting sort in Java programming import java.util.Arrays; class CountingSort ( void countSort(int array(), int size) ( int() output = new int(size + 1); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); // Initialize count array with all zeros. for (int i = 0; i < max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Driver code public static void main(String args()) ( int() data = ( 4, 2, 2, 8, 3, 3, 1 ); int size = data.length; CountingSort cs = new CountingSort(); cs.countSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Counting sort in C programming #include void countingSort(int array(), int size) ( int output(10); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) // The size of count must be at least (max+1) but // we cannot declare it as int count(max+1) in C as // it does not support dynamic memory allocation. // So, its size is provided statically. int count(10); // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countingSort(array, n); printArray(array, n); )
// Counting sort in C++ programming #include using namespace std; void countSort(int array(), int size) ( // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output(10); int count(10); int max = array(0); // Find the largest element of the array for (int i = 1; i max) max = array(i); ) // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countSort(array, n); printArray(array, n); )
Sarežģītība
Laika sarežģītība:
Galvenokārt ir četras galvenās cilpas. (Lielāko vērtību var atrast ārpus funkcijas.)
| for-loop | skaitīšanas laiks |
|---|---|
| 1 | O (maks.) |
| 2 | O (izmērs) |
| 3 | O (maks.) |
| 4 | O (izmērs) |
Kopējā sarežģītība = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Sliktākā gadījuma sarežģītība:
O(n+k) - Labākā gadījuma sarežģītība:
O(n+k) - Vidējā lietu sarežģītība:
O(n+k)
Visos iepriekšminētajos gadījumos sarežģītība ir vienāda, jo neatkarīgi no tā, kā elementi tiek ievietoti masīvā, algoritms iet cauri n+klaikiem.
Nav neviena elementa salīdzinājuma, tāpēc tas ir labāk nekā šķirošanas paņēmieni, kas balstīti uz salīdzināšanu. Bet tas ir slikti, ja veseli skaitļi ir ļoti lieli, jo jāizveido šāda izmēra masīvs.
Kosmosa sarežģītība:
Skaitīšanas kārtošanas telpas sarežģītība ir O(max). Lielāks elementu klāsts, lielāka ir telpas sarežģītība.
Kārtot lietojumprogrammas
Skaitīšanas kārtošana tiek izmantota, ja:
- ir mazāki veseli skaitļi ar vairākiem skaitļiem.
- vajadzība ir lineāra sarežģītība.
