Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Counting Sort, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Counting Sort thông qua các phần sau.
Nội dung chính
1. Giới thiệu
Sắp xếp đếm(Counting Sort) là một kỹ thuật sắp xếp dựa trên các khóa giữa một phạm vi cụ thể. Nó hoạt động bằng cách đếm số lượng các đối tượng có các giá trị khóa riêng biệt (loại băm). Sau đó, thực hiện một số phép tính để tính toán vị trí của mỗi đối tượng trong chuỗi đầu ra.
Bạn có thể hiểu nó với sự trợ giúp của một ví dụ sau:
Để đơn giản, hãy xem xét dữ liệu trong phạm vi từ 0 đến 9.
Dữ liệu đầu vào: 1, 4, 1, 2, 7, 5, 2
1) Lấy một mảng đếm để lưu trữ số lượng của mỗi đối tượng duy nhất.
Chỉ số: 0 1 2 3 4 5 6 7 8 9
Đếm: 0 2 2 0 1 1 0 1 0 0
2) Sửa đổi mảng đếm sao cho mỗi phần tử ở mỗi chỉ mục lưu trữ tổng của các lần đếm trước đó.
Chỉ số: 0 1 2 3 4 5 6 7 8 9
Đếm: 0 2 4 4 5 6 6 7 7 7
Mảng đếm đã sửa đổi cho biết vị trí của từng đối tượng trong trình tự đầu ra.
3) Xuất ra từng đối tượng từ chuỗi đầu vào theo sau là giảm số lượng của nó đi 1.
Xử lý dữ liệu đầu vào: 1, 4, 1, 2, 7, 5, 2. Vị trí của 1 là 2.
Đặt dữ liệu 1 ở chỉ mục 2 trong đầu ra. Giảm số lượng đi 1 vị trí dữ liệu tiếp theo 1 ở chỉ mục 1 nhỏ hơn chỉ mục này.
2. Code ví dụ trên nhiều ngôn ngữ
C++
// C++ Program for counting sort
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
#define RANGE 255
// The main function that sort
// the given string arr[] in
// alphabatical order
void countSort(char arr[])
{
// The output character array
// that will have sorted arr
char output[strlen(arr)];
// Create a count array to store count of inidividul
// characters and initialize count array as 0
int count[RANGE + 1], i;
memset(count, 0, sizeof(count));
// Store count of each character
for (i = 0; arr[i]; ++i)
++count[arr[i]];
// Change count[i] so that count[i] now contains actual
// position of this character in output array
for (i = 1; i <= RANGE; ++i)
count[i] += count[i - 1];
// Build the output character array
for (i = 0; arr[i]; ++i) {
output[count[arr[i]] - 1] = arr[i];
--count[arr[i]];
}
/*
For Stable algorithm
for (i = sizeof(arr)-1; i>=0; --i)
{
output[count[arr[i]]-1] = arr[i];
--count[arr[i]];
}
For Logic : See implementation
*/
// Copy the output array to arr, so that arr now
// contains sorted characters
for (i = 0; arr[i]; ++i)
arr[i] = output[i];
}
// Driver code
int main()
{
char arr[] = "cafedev.vn";
countSort(arr);
cout << "Sorted character array is " << arr;
return 0;
} C
// C Program for counting sort
#include <stdio.h>
#include <string.h>
#define RANGE 255
// The main function that sort the given string arr[] in
// alphabatical order
void countSort(char arr[])
{
// The output character array that will have sorted arr
char output[strlen(arr)];
// Create a count array to store count of inidividul
// characters and initialize count array as 0
int count[RANGE + 1], i;
memset(count, 0, sizeof(count));
// Store count of each character
for (i = 0; arr[i]; ++i)
++count[arr[i]];
// Change count[i] so that count[i] now contains actual
// position of this character in output array
for (i = 1; i <= RANGE; ++i)
count[i] += count[i - 1];
// Build the output character array
for (i = 0; arr[i]; ++i) {
output[count[arr[i]] - 1] = arr[i];
--count[arr[i]];
}
/*
For Stable algorithm
for (i = sizeof(arr)-1; i>=0; --i)
{
output[count[arr[i]]-1] = arr[i];
--count[arr[i]];
}
For Logic : See implementation
*/
// Copy the output array to arr, so that arr now
// contains sorted characters
for (i = 0; arr[i]; ++i)
arr[i] = output[i];
}
// Driver program to test above function
int main()
{
char arr[] = "cafedev.vn"; //"applepp";
countSort(arr);
printf("Sorted character array is %sn", arr);
return 0;
}
Java
// Java implementation of Counting Sort
class CountingSort {
void sort(char arr[])
{
int n = arr.length;
// The output character array that will have sorted arr
char output[] = new char[n];
// Create a count array to store count of inidividul
// characters and initialize count array as 0
int count[] = new int[256];
for (int i = 0; i < 256; ++i)
count[i] = 0;
// store count of each character
for (int i = 0; i < n; ++i)
++count[arr[i]];
// Change count[i] so that count[i] now contains actual
// position of this character in output array
for (int i = 1; i <= 255; ++i)
count[i] += count[i - 1];
// Build the output character array
// To make it stable we are operating in reverse order.
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
--count[arr[i]];
}
// Copy the output array to arr, so that arr now
// contains sorted characters
for (int i = 0; i < n; ++i)
arr[i] = output[i];
}
// Driver method
public static void main(String args[])
{
CountingSort ob = new CountingSort();
char arr[] = { 'c', 'f', 'e', 'd', 'e', 'v', '.',
'v', 'n'};
ob.sort(arr);
System.out.print("Sorted character array is ");
for (int i = 0; i < arr.length; ++i)
System.out.print(arr[i]);
}
} Python 3
# Python program for counting sort
# The main function that sort the given string arr[] in
# alphabetical order
def countSort(arr):
# The output character array that will have sorted arr
output = [0 for i in range(len(arr))]
# Create a count array to store count of inidividul
# characters and initialize count array as 0
count = [0 for i in range(256)]
# For storing the resulting answer since the
# string is immutable
ans = ["" for _ in arr]
# Store count of each character
for i in arr:
count[ord(i)] += 1
# Change count[i] so that count[i] now contains actual
# position of this character in output array
for i in range(256):
count[i] += count[i-1]
# Build the output character array
for i in range(len(arr)):
output[count[ord(arr[i])]-1] = arr[i]
count[ord(arr[i])] -= 1
# Copy the output array to arr, so that arr now
# contains sorted characters
for i in range(len(arr)):
ans[i] = output[i]
return ans
# Driver program to test above function
arr = "cafedev.vn"
ans = countSort(arr)
print("Sorted character array is % s" %("".join(ans))) C#
// C# implementation of Counting Sort
using System;
class GFG {
static void countsort(char[] arr)
{
int n = arr.Length;
// The output character array that
// will have sorted arr
char[] output = new char[n];
// Create a count array to store
// count of inidividul characters
// and initialize count array as 0
int[] count = new int[256];
for (int i = 0; i < 256; ++i)
count[i] = 0;
// store count of each character
for (int i = 0; i < n; ++i)
++count[arr[i]];
// Change count[i] so that count[i]
// now contains actual position of
// this character in output array
for (int i = 1; i <= 255; ++i)
count[i] += count[i - 1];
// Build the output character array
// To make it stable we are operating in reverse order.
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
--count[arr[i]];
}
// Copy the output array to arr, so
// that arr now contains sorted
// characters
for (int i = 0; i < n; ++i)
arr[i] = output[i];
}
// Driver method
public static void Main()
{
char[] arr = { 'c', 'f', 'e', 'd', 'e', 'v', '.',
'v', 'n'};
countsort(arr);
Console.Write("Sorted character array is ");
for (int i = 0; i < arr.Length; ++i)
Console.Write(arr[i]);
}
} PHP
<?php
// PHP Program for counting sort
$RANGE = 255;
// The main function that sort
// the given string arr[] in
// alphabatical order
function countSort($arr)
{
global $RANGE;
// The output character array
// that will have sorted arr
$output = array(strlen($arr));
$len = strlen($arr);
// Create a count array to
// store count of inidividul
// characters and initialize
// count array as 0
$count = array_fill(0, $RANGE + 1, 0);
// Store count of
// each character
for($i = 0; $i < $len; ++$i)
++$count[ord($arr[$i])];
// Change count[i] so that
// count[i] now contains
// actual position of this
// character in output array
for ($i = 1; $i <= $RANGE; ++$i)
$count[$i] += $count[$i - 1];
// Build the output
// character array
// To make it stable we are operating
// in reverse order.
for ($i = $len-1; $i >= 0 ; $i--)
{
$output[$count[ord($arr[$i])] - 1] = $arr[$i];
--$count[ord($arr[$i])];
}
// Copy the output array to
// arr, so that arr now
// contains sorted characters
for ($i = 0; $i < $len; ++$i)
$arr[$i] = $output[$i];
return $arr;
}
// Driver Code
$arr = "cafedev.vn"; //"applepp";
$arr = countSort($arr);
echo "Sorted character array is " . $arr;
?>
Kết quả:
Sorted character array is acdeefvvn.3. Độ phức tạp
Độ phức tạp thời gian: O (n + k) với n là số phần tử trong mảng đầu vào và k là phạm vi đầu vào.
Không gian phụ trợ: O (n + k)
Vấn đề với cách đếm trước đó là chúng ta không thể sắp xếp các phần tử nếu chúng ta có số âm trong đó. Bởi vì không có chỉ số mảng âm. Vì vậy, những gì chúng ta làm là, chúng ta tìm phần tử tối thiểu và chúng ta sẽ lưu trữ số lượng phần tử tối thiểu đó ở chỉ số 0 như sau:
C++
// Counting sort which takes negative numbers as well
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void countSort(vector<int>& arr)
{
int max = *max_element(arr.begin(), arr.end());
int min = *min_element(arr.begin(), arr.end());
int range = max - min + 1;
vector<int> count(range), output(arr.size());
for (int i = 0; i < arr.size(); i++)
count[arr[i] - min]++;
for (int i = 1; i < count.size(); i++)
count[i] += count[i - 1];
for (int i = arr.size() - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < arr.size(); i++)
arr[i] = output[i];
}
void printArray(vector<int>& arr)
{
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
vector<int> arr = { -5, -10, 0, -3, 8, 5, -1, 10 };
countSort(arr);
printArray(arr);
return 0;
}
Java
// Counting sort which takes negative numbers as well
import java.util.*;
class GFG {
static void countSort(int[] arr)
{
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1;
int count[] = new int[range];
int output[] = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
static void printArray(int[] arr)
{
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println("");
}
// Driver code
public static void main(String[] args)
{
int[] arr = { -5, -10, 0, -3, 8, 5, -1, 10 };
countSort(arr);
printArray(arr);
}
}
Python3
# Python program for counting sort
# which takes negative numbers as well
# The function that sorts the given arr[]
def count_sort(arr):
max_element = int(max(arr))
min_element = int(min(arr))
range_of_elements = max_element - min_element + 1
# Create a count array to store count of individual
# elements and initialize count array as 0
count_arr = [0 for _ in range(range_of_elements)]
output_arr = [0 for _ in range(len(arr))]
# Store count of each character
for i in range(0, len(arr)):
count_arr[arr[i]-min_element] += 1
# Change count_arr[i] so that count_arr[i] now contains actual
# position of this element in output array
for i in range(1, len(count_arr)):
count_arr[i] += count_arr[i-1]
# Build the output character array
for i in range(len(arr)-1, -1, -1):
output_arr[count_arr[arr[i] - min_element] - 1] = arr[i]
count_arr[arr[i] - min_element] -= 1
# Copy the output array to arr, so that arr now
# contains sorted characters
for i in range(0, len(arr)):
arr[i] = output_arr[i]
return arr
# Driver program to test above function
arr = [-5, -10, 0, -3, 8, 5, -1, 10]
ans = count_sort(arr)
print("Sorted character array is " + str(ans))
Kết quả
-10 -5 -3 -1 0 5 8 10 4. Những điểm cần lưu ý:
1. Sắp xếp đếm sẽ hiệu quả nếu phạm vi dữ liệu đầu vào không lớn hơn đáng kể so với số đối tượng được sắp xếp. Hãy xem xét tình huống trong đó chuỗi đầu vào nằm trong khoảng từ 1 đến 10K và dữ liệu là 10, 5, 10K, 5K.
2. Nó không phải là sự sắp xếp dựa trên so sánh. Độ phức tạp thời gian chạy của nó là O (n) với không gian tỷ lệ với phạm vi dữ liệu.
3. Nó thường được sử dụng như một quy trình con cho một thuật toán sắp xếp khác như sắp xếp cơ số.
4. Sắp xếp đếm sử dụng băm một phần để đếm sự xuất hiện của đối tượng dữ liệu trong O (1).
5. Sắp xếp đếm có thể được mở rộng để làm việc cho các đầu vào âm.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
