Sắp xếp đếm DSA
Đếm sắp xếp
Thuật toán Counting Sort sắp xếp một mảng bằng cách đếm số lần mỗi giá trị xuất hiện.
Tốc độ:
{{ msgDone }}Chạy mô phỏng để xem 17 giá trị nguyên từ 1 đến 5 được sắp xếp như thế nào bằng cách sử dụng Counting Sort.
Sắp xếp đếm không so sánh các giá trị như các thuật toán sắp xếp trước đó mà chúng tôi đã xem xét và chỉ hoạt động trên các số nguyên không âm.
Hơn nữa, Sắp xếp đếm nhanh khi phạm vi giá trị có thể có \(k\) nhỏ hơn số lượng giá trị \(n\).
Làm thế nào nó hoạt động:
- Tạo một mảng mới để đếm xem có bao nhiêu giá trị khác nhau.
- Đi qua mảng cần sắp xếp.
- Đối với mỗi giá trị, hãy đếm nó bằng cách tăng mảng đếm ở chỉ mục tương ứng.
- Sau khi đếm các giá trị, duyệt qua mảng đếm để tạo mảng đã sắp xếp.
- Đối với mỗi số đếm trong mảng đếm, hãy tạo số phần tử chính xác, với các giá trị tương ứng với chỉ số của mảng đếm.
Điều kiện để sắp xếp đếm
Đây là những lý do tại sao Counting Sort được cho là chỉ hoạt động đối với một phạm vi giới hạn các giá trị số nguyên không âm:
- Giá trị số nguyên: Sắp xếp đếm dựa vào việc đếm số lần xuất hiện của các giá trị riêng biệt, do đó chúng phải là số nguyên. Với số nguyên, mỗi giá trị khớp với một chỉ mục (đối với giá trị không âm) và có giới hạn số lượng giá trị khác nhau, do đó số lượng giá trị khác nhau có thể có \(k\) không quá lớn so với số lượng giá trị \ (N\).
- Giá trị không âm: Sắp xếp đếm thường được thực hiện bằng cách tạo một mảng để đếm. Khi thuật toán duyệt qua các giá trị cần sắp xếp, giá trị x được tính bằng cách tăng giá trị mảng đếm tại chỉ số x. Nếu cố gắng sắp xếp các giá trị âm, chúng ta sẽ gặp rắc rối với việc sắp xếp giá trị -3, vì chỉ số -3 sẽ nằm ngoài mảng đếm.
- Phạm vi giá trị bị giới hạn: Nếu số lượng giá trị khác nhau có thể được sắp xếp \(k\) lớn hơn số lượng giá trị được sắp xếp \(n\), thì mảng đếm mà chúng ta cần để sắp xếp sẽ lớn hơn mảng ban đầu chúng tôi có nhu cầu sắp xếp và thuật toán trở nên không hiệu quả.
Chạy qua thủ công
Trước khi triển khai thuật toán Sắp xếp Đếm trong ngôn ngữ lập trình, chúng ta hãy chạy qua một mảng ngắn theo cách thủ công để lấy ý tưởng.
Bước 1: Chúng ta bắt đầu với một mảng chưa được sắp xếp.
myArray = [ 2, 3, 0, 2, 3, 2]
Bước 2: Chúng ta tạo một mảng khác để đếm xem mỗi giá trị có bao nhiêu mảng. Mảng có 4 phần tử, chứa các giá trị từ 0 đến 3.
myArray = [ 2, 3, 0, 2, 3, 2]
countArray = [ 0, 0, 0, 0]
Bước 3: Bây giờ chúng ta bắt đầu đếm nhé. Phần tử đầu tiên là 2 nên chúng ta phải tăng phần tử mảng đếm ở chỉ số 2.
myArray = [ 2 , 3, 0, 2, 3, 2]
countArray = [ 0, 0, 1 , 0]
Bước 4: Sau khi đếm một giá trị, chúng ta có thể xóa giá trị đó và đếm giá trị tiếp theo là 3.
myArray = [ 3 , 0, 2, 3, 2]
countArray = [ 0, 0, 1, 1 ]
Bước 5: Giá trị tiếp theo chúng ta đếm là 0 nên chúng ta tăng chỉ số 0 trong mảng đếm.
myArray = [ 0 , 2, 3, 2]
countArray = [ 1 , 0, 1, 1]
Bước 6: Chúng ta tiếp tục như vậy cho đến khi đếm hết các giá trị.
myArray = [ ]
countArray = [ 1, 0, 3, 2 ]
Bước 7: Bây giờ chúng ta sẽ tạo lại các phần tử từ mảng ban đầu và chúng ta sẽ thực hiện sao cho các phần tử được sắp xếp từ thấp nhất đến cao nhất.
Phần tử đầu tiên trong mảng đếm cho chúng ta biết rằng chúng ta có 1 phần tử có giá trị 0. Vì vậy chúng ta đẩy 1 phần tử có giá trị 0 vào mảng và chúng ta giảm phần tử ở chỉ số 0 trong mảng đếm bằng 1.
myArray = [ 0 ]
countArray = [ 0 , 0, 3, 2]
Bước 8: Từ mảng đếm ta thấy không cần tạo phần tử nào có giá trị 1.
myArray = [ 0]
countArray = [ 0, 0 , 3, 2]
Bước 9: Ta push 3 phần tử có giá trị 2 vào cuối mảng. Và khi chúng tôi tạo các phần tử này, chúng tôi cũng giảm mảng đếm ở chỉ mục 2.
myArray = [ 0, 2, 2, 2 ]
countArray = [ 0, 0, 0 , 2]
Bước 10: Cuối cùng chúng ta phải thêm 2 phần tử có giá trị 3 vào cuối mảng.
myArray = [0, 2, 2, 2, 3, 3 ]
countArray = [ 0, 0, 0, 0 ]
Cuối cùng! Mảng được sắp xếp.
Chạy mô phỏng bên dưới để xem các bước ở trên hoạt hình:
countArray = [
Chạy qua thủ công: Chuyện gì đã xảy ra?
Trước khi triển khai thuật toán bằng ngôn ngữ lập trình, chúng ta cần xem xét chi tiết hơn những gì đã xảy ra ở trên.
Chúng ta đã thấy rằng thuật toán Counting Sort hoạt động theo hai bước:
- Mỗi giá trị được tính bằng cách tăng theo chỉ số chính xác trong mảng đếm. Sau khi một giá trị được đếm, nó sẽ bị xóa.
- Các giá trị được tạo lại theo đúng thứ tự bằng cách sử dụng số đếm và chỉ mục của số đếm từ mảng đếm.
Với suy nghĩ này, chúng ta có thể bắt đầu triển khai thuật toán bằng Python.
Thực hiện sắp xếp đếm
Để thực hiện thuật toán Counting Sort trong ngôn ngữ lập trình, chúng ta cần:
- Một mảng có các giá trị cần sắp xếp.
- Phương thức 'countingSort' nhận một mảng số nguyên.
- Một mảng bên trong phương thức để đếm các giá trị.
- Một vòng lặp bên trong phương thức đếm và loại bỏ các giá trị bằng cách tăng các phần tử trong mảng đếm.
- Một vòng lặp bên trong phương thức tạo lại mảng bằng cách sử dụng mảng đếm để các phần tử xuất hiện theo đúng thứ tự.
Một điều nữa: Chúng ta cần tìm ra giá trị cao nhất trong mảng là bao nhiêu để tạo ra mảng đếm với kích thước chính xác. Ví dụ: nếu giá trị cao nhất là 5 thì mảng đếm phải có tổng cộng 6 phần tử để có thể đếm tất cả các số nguyên không âm có thể có 0, 1, 2, 3, 4 và 5.
Mã kết quả trông như thế này:
Ví dụ
def countingSort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
while len(arr) > 0:
num = arr.pop(0)
count[num] += 1
for i in range(len(count)):
while count[i] > 0:
arr.append(i)
count[i] -= 1
return arr
unsortedArr = [4, 2, 2, 6, 3, 3, 1, 6, 5, 2, 3]
sortedArr = countingSort(unsortedArr)
print("Sorted array:", sortedArr)
Chạy ví dụ »Đếm độ phức tạp của thời gian sắp xếp
Để có giải thích chung về độ phức tạp của thời gian, hãy truy cập trang này .
Để được giải thích kỹ lưỡng và chi tiết hơn về độ phức tạp về thời gian Sắp xếp chèn, hãy truy cập trang này .
Thuật toán Sắp xếp Đếm chạy nhanh đến mức nào tùy thuộc vào cả phạm vi giá trị có thể có \(k\) và số lượng giá trị \(n\).
Nói chung, độ phức tạp về thời gian cho Sắp xếp đếm là \(O(n+k)\).
Trong trường hợp tốt nhất, phạm vi của các giá trị khác nhau có thể có \(k\) là rất nhỏ so với số lượng giá trị \(n\) và Sắp xếp đếm có độ phức tạp về thời gian \(O(n)\).
Nhưng trong trường hợp xấu nhất, phạm vi các giá trị khác nhau có thể có \(k\) là rất lớn so với số lượng giá trị \(n\) và Sắp xếp đếm có thể có độ phức tạp về thời gian \(O(n^2)\) hoặc thậm chí còn tệ hơn.
Biểu đồ bên dưới cho thấy mức độ phức tạp về thời gian của Sắp xếp Đếm có thể thay đổi như thế nào.
Như bạn có thể thấy, điều quan trọng là phải xem xét phạm vi giá trị so với số lượng giá trị cần sắp xếp trước khi chọn Sắp xếp đếm làm thuật toán của bạn. Ngoài ra, như đã đề cập ở đầu trang, hãy nhớ rằng Sắp xếp đếm chỉ hoạt động với các giá trị nguyên không âm.
Chạy các mô phỏng khác nhau của Sắp xếp đếm để xem số lượng thao tác nằm giữa trường hợp xấu nhất \(O(n^2)\) (đường màu đỏ) và trường hợp tốt nhất \(O(n)\) (đường màu xanh lá cây).
{{ this.userX }}
{{ this.userK }}
Hoạt động: {{ hoạt động }}
Như đã đề cập trước đây: nếu các số cần sắp xếp thay đổi nhiều về giá trị (lớn \(k\)) và có ít số cần sắp xếp (nhỏ \(n\)) thì thuật toán Sắp xếp Đếm sẽ không hiệu quả.
Nếu chúng ta giữ cố định \(n\) và \(k\) thì các lựa chọn thay thế "Ngẫu nhiên", "Giảm dần" và "Tăng dần" trong mô phỏng ở trên sẽ dẫn đến cùng một số thao tác. Điều này là do điều tương tự xảy ra trong cả ba trường hợp: Một mảng đếm được thiết lập, các số được đếm và mảng được sắp xếp mới được tạo.
