Phân loại chuồng chim bồ câu là một ví dụ về kỹ thuật phân loại không so sánh. Nó được sử dụng khi số lượng mục và phạm vi của các giá trị khóa có thể là gần giống nhau.
Để thực hiện phân loại này, chúng ta cần tạo một số lỗ. Số lượng lỗ cần thiết được quyết định bởi phạm vi số lượng. Trong mỗi lỗ, các mục được chèn vào. Cuối cùng được xóa khỏi lỗ và được lưu trữ thành một mảng để sắp xếp thứ tự.
Sắp xếp chuồng bồ câu, còn được gọi là sắp xếp đếm, là một thuật toán sắp xếp phù hợp để sắp xếp danh sách các phần tử trong đó số phần tử (n) và số lượng các giá trị khóa có thể có (N) là gần như nhau. [1] Nó yêu cầu thời gian O (n + N).
Input: arr[]={7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7 Giải thích
-
Tìm phần tử tối thiểu và tối đa trong mảng. phần tử tối thiểu và tối đa sẽ lần lượt là ‘min’ và ‘max’. sau đó tìm phạm vi là 'max-min-1'.
-
Thiết lập một mảng ban đầu trống cho “chuồng chim bồ câu” có cùng kích thước với phạm vi.
-
Duyệt qua từng phần tử của mảng và sau đó đặt từng phần tử vào chuồng chim bồ câu của nó. Phần tử arr [i] sẽ được đưa vào lỗ tại chỉ mục arr [i] - min.
-
Vòng lặp sẽ bắt đầu trên toàn bộ mảng chuồng bồ câu theo thứ tự và đặt tất cả các phần tử từ các lỗ không trống trở lại mảng ban đầu.
Ví dụ
#include <iostream>
using namespace std;
#define MAX 7
void pigeonhole_sort(int, int, int *);
int main() {
int i, min, max;
int a[]={7,4,2,6,3,1,5};
min = a[0];
max = a[0];
for (i = 1; i < MAX; i++) {
if (a[i] < min) {
min = a[i];
}
if (a[i] > max) {
max = a[i];
}
}
pigeonhole_sort(min, max, a);
for (i = 0; i < MAX; i++) {
cout<< a[i]<<"\t";
}
}
void pigeonhole_sort(int mi, int ma, int * a) {
int size, count = 0, i;
int *current;
current = a;
size = ma - mi + 1;
int holes[size];
for (i = 0; i < size; i++) {
holes[i] = 0;
}
for (i = 0; i < size; i++, current++) {
holes[*current-mi] += 1;
}
for (count = 0, current = &a[0]; count < size; count++) {
while (holes[count]--> 0) {
*current++ = count + mi;
}
}
} Đầu ra
1 2 3 4 5 6 7