W tym samouczku dowiesz się, jak działa sortowanie z liczeniem. Znajdziesz również działające przykłady sortowania zliczania w językach C, C ++, Java i Python.
Sortowanie według liczenia to algorytm sortowania, który sortuje elementy tablicy, zliczając liczbę wystąpień każdego unikalnego elementu w tablicy. Liczba jest przechowywana w tablicy pomocniczej, a sortowanie odbywa się poprzez odwzorowanie liczby jako indeksu tablicy pomocniczej.
Jak działa sortowanie według liczenia?
- Znajdź maksymalny element (niech będzie
max) z podanej tablicy.
Podana tablica - Zainicjuj tablicę długości
max+1ze wszystkimi elementami 0. Ta tablica jest używana do przechowywania liczby elementów w tablicy.
Tablica zliczania - Przechowuj liczbę każdego elementu w odpowiednim indeksie w
counttablicy
Na przykład: jeśli liczba elementów 3 wynosi 2, to 2 jest przechowywane na trzeciej pozycji tablicy count. Jeśli w tablicy nie ma elementu „5”, to 0 jest zapisywane na piątej pozycji.
Liczba każdego przechowywanego elementu - Przechowuj skumulowaną sumę elementów tablicy count. Pomaga w umieszczeniu elementów we właściwym indeksie posortowanej tablicy.
Łączna liczba - Znajdź indeks każdego elementu oryginalnej tablicy w tablicy count. To daje łączną liczbę. Umieść element na indeksie obliczonym zgodnie z poniższym rysunkiem.
Sortowanie liczone - Po umieszczeniu każdego elementu we właściwej pozycji zmniejsz jego liczbę o jeden.
Algorytm sortowania zliczania
countingSort (array, size) max <- znajdź największy element w tablicy zainicjuj tablicę count ze wszystkimi zerami dla j <- 0 do rozmiaru znajdź całkowitą liczbę każdego unikalnego elementu i zapisz licznik w indeksie jth w tablicy count dla i <- 1 aby max znaleźć sumę skumulowaną i zapisać ją w tablicy count dla j <- rozmiar w dół do 1 przywróć elementy do tablicy zmniejsz liczbę każdego przywracanego elementu o 1
Przykłady w Pythonie, Javie i C / C ++
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); )
Złożoność
Złożoność czasowa:
Istnieją głównie cztery główne pętle. (Największą wartość można znaleźć poza funkcją).
| dla pętli | czas liczenia |
|---|---|
| 1 | O (maks.) |
| 2nd | O (rozmiar) |
| 3rd | O (maks.) |
| 4 | O (rozmiar) |
Ogólna złożoność = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Najgorsza złożoność przypadku:
O(n+k) - Najlepsza złożoność przypadku:
O(n+k) - Średnia złożoność przypadku:
O(n+k)
We wszystkich powyższych przypadkach złożoność jest taka sama, ponieważ bez względu na to, jak elementy są umieszczone w tablicy, algorytm przechodzi przez n+kczasy.
Nie ma porównania między żadnymi elementami, więc jest to lepsze niż techniki sortowania oparte na porównaniu. Ale źle jest, jeśli liczby całkowite są bardzo duże, ponieważ należy utworzyć tablicę o takim rozmiarze.
Złożoność przestrzeni:
Złożoność przestrzenna sortowania liczenia wynosi O(max). Im większy zakres elementów, tym większa złożoność przestrzeni.
Liczenie aplikacji sortowania
Sortowanie według liczenia jest stosowane, gdy:
- istnieją mniejsze liczby całkowite z wieloma liczbami.
- potrzebą jest złożoność liniowa.
