Selles õpetuses saate teada, kuidas sortimise loendamine töötab. Samuti leiate toimivad näited sortimise loendamise kohta C, C ++, Java ja Python.
Loendamissorteerimine on sorteerimisalgoritm, mis sorteerib massiivi elemendid, lugedes massiivi iga kordumatu elemendi esinemiste arvu. Loend salvestatakse abimassiivi ja sortimine toimub kaardistades loenduse abimassiivi indeksina.
Kuidas sorteerimise loendamine töötab?
- Uurige
maxantud massiivi maksimaalne element (las see olla ).
Antud massiiv - Initsialiseeri massiivi pikkus
max+1kõigi elementidega 0. Seda massiivi kasutatakse massiivi elementide arvu salvestamiseks.
Loe massiivi - Salvestage iga elemendi arv
countmassiivis vastavasse indeksisse.
Näiteks: kui elemendi 3 arv on 2, siis salvestatakse 2 loendusmassiivi 3. positsiooni. Kui massiivi elementi "5" pole, siis 0 salvestatakse 5. positsioonis.
Iga salvestatud elemendi arv - Salvesta loenduse massiivi elementide kumulatiivne summa. See aitab elemente paigutada sorteeritud massiivi õigesse indeksisse.
Kumulatiivne arv - Leidke loendusmassiivist algse massiivi iga elemendi register. See annab kumulatiivse arvu. Asetage element alltoodud joonisel näidatud arvutatud indeksile.
Sorteerimise loendamine - Pärast iga elemendi õigesse asendisse asetamist vähendage nende arvu ühe võrra.
Sortimisalgoritmi loendamine
countingSort (massiiv, suurus) max <- leidke massiivi suurim element initsialiseerige loendusmassiiv kõigi nullidega j <- 0 jaoks suuruse leidmiseks leidke iga kordumatu elemendi koguarv ja salvestage arv i <- 1 loendusmassiivi j-sse indeksisse Kumuleeruva summa leidmiseks ja selle salvestamiseks massiivi enda jaoks j <- suurus alla 1 taastage elemendid massiivi vähenemise arvu taastamiseks iga 1 võrra
Pythoni, Java ja C / C ++ näited
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); )
Keerukus
Aja keerukus:
Põhisilmi on peamiselt neli. (Suurima väärtuse võib leida väljaspool funktsiooni.)
| for-loop | loendamise aeg |
|---|---|
| 1. | O (max) |
| 2 | O (suurus) |
| 3 | O (max) |
| 4 | O (suurus) |
Üldine keerukus = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Halvima juhtumi keerukus:
O(n+k) - Parima juhtumi keerukus:
O(n+k) - Keskmine juhtumi keerukus:
O(n+k)
Kõigil ülaltoodud juhtudel on keerukus sama, sest ükskõik kuidas elemendid massiivi paigutatakse, läbib algoritm n+kaegu.
Ühegi elemendi vahel pole võrdlust, seega on see parem kui võrdlusel põhinevad sortimistehnikad. Kuid on halb, kui täisarvud on väga suured, kuna tuleks teha selle suurusega massiiv.
Ruumi keerukus:
Sorteerimise loendamise ruumi keerukus on O(max). Mida suurem on elementide valik, seda suurem on ruumi keerukus.
Rakenduste sortimine
Loendamissorteerimist kasutatakse siis, kui:
- on väiksemaid täisarvusid mitme loendusega.
- lineaarne keerukus on vajadus.
