Trong hướng dẫn này, bạn sẽ tìm hiểu cách thức sắp xếp đếm hoạt động. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về sắp xếp đếm trong C, C ++, Java và Python.
Sắp xếp đếm là một thuật toán sắp xếp sắp xếp các phần tử của một mảng bằng cách đếm số lần xuất hiện của mỗi phần tử duy nhất trong mảng. Số đếm được lưu trữ trong một mảng phụ và việc sắp xếp được thực hiện bằng cách ánh xạ số đếm như một chỉ số của mảng phụ.
Cách đếm sắp xếp hoạt động?
- Tìm phần tử lớn nhất (giả sử
max) từ mảng đã cho.
Mảng đã cho - Khởi tạo một mảng có độ dài
max+1với tất cả các phần tử 0. Mảng này được sử dụng để lưu trữ số lượng các phần tử trong mảng.
Đếm mảng - Lưu trữ số lượng của từng phần tử tại chỉ số tương ứng của chúng trong
countmảng
Ví dụ: nếu số lượng của phần tử 3 là 2 thì 2 được lưu trữ ở vị trí thứ 3 của mảng đếm. Nếu phần tử "5" không có trong mảng, thì 0 được lưu ở vị trí thứ 5.
Số lượng mỗi phần tử được lưu trữ - Lưu trữ tổng tích lũy của các phần tử của mảng đếm. Nó giúp đặt các phần tử vào chỉ mục chính xác của mảng đã sắp xếp.
Số lượng tích lũy - Tìm chỉ số của từng phần tử của mảng ban đầu trong mảng đếm. Điều này cho biết số lượng tích lũy. Đặt phần tử tại chỉ số được tính như trong hình dưới đây.
Đếm sắp xếp - Sau khi đặt mỗi phần tử vào đúng vị trí của nó, hãy giảm số lượng của nó đi một phần.
Thuật toán sắp xếp đếm
countSort (mảng, kích thước) max <- tìm phần tử lớn nhất trong mảng Khởi tạo mảng đếm với tất cả các số 0 cho j <- 0 để kích thước tìm tổng số của từng phần tử duy nhất và lưu số đếm ở chỉ số thứ j trong mảng đếm cho i <- 1 để tối đa tìm tổng tích lũy và lưu trữ nó trong chính mảng đếm cho j <- kích thước giảm xuống 1 khôi phục các phần tử vào mảng giảm số lượng của mỗi phần tử được khôi phục 1
Ví dụ về Python, Java và 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); )
Phức tạp
Thời gian phức tạp:
Chủ yếu có bốn vòng lặp chính. (Việc tìm giá trị lớn nhất có thể được thực hiện bên ngoài hàm.)
| vòng lặp | thời gian đếm |
|---|---|
| Ngày 1 | O (tối đa) |
| lần 2 | O (kích thước) |
| lần thứ 3 | O (tối đa) |
| lần thứ 4 | O (kích thước) |
Độ phức tạp tổng thể = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Trường hợp phức tạp tồi tệ nhất:
O(n+k) - Độ phức tạp của trường hợp tốt nhất:
O(n+k) - Độ phức tạp của trường hợp trung bình:
O(n+k)
Trong tất cả các trường hợp trên, độ phức tạp là như nhau vì cho dù các phần tử được đặt trong mảng như thế nào thì thuật toán cũng trải qua n+kthời gian.
Không có sự so sánh giữa bất kỳ yếu tố nào, vì vậy nó tốt hơn so với kỹ thuật sắp xếp dựa trên so sánh. Tuy nhiên, thật tệ nếu các số nguyên rất lớn vì mảng có kích thước đó sẽ được tạo ra.
Không gian phức tạp:
Độ phức tạp không gian của Sắp xếp Đếm là O(max). Phạm vi phần tử càng lớn thì độ phức tạp về không gian càng lớn.
Đếm các ứng dụng sắp xếp
Sắp xếp đếm được sử dụng khi:
- có số nguyên nhỏ hơn với nhiều số đếm.
- sự phức tạp tuyến tính là nhu cầu.
