Comb Sort

Ý tưởng cơ bản của sắp xếp lược và sắp xếp bong bóng là giống nhau. Nói cách khác, sắp xếp theo kiểu lược là một cải tiến của sắp xếp bong bóng. Trong kỹ thuật sắp xếp bong bóng, các mục được so sánh với mục tiếp theo trong mỗi giai đoạn. Nhưng đối với sắp xếp theo kiểu lược, các mục được sắp xếp theo một khoảng trống cụ thể. Sau khi hoàn thành mỗi giai đoạn, khoảng cách được giảm xuống. Hệ số giảm hoặc hệ số thu nhỏ cho loại này là 1,3. Có nghĩa là sau khi hoàn thành mỗi giai đoạn, khoảng cách được chia cho 1,3.

Sự phức tạp của Kỹ thuật sắp xếp theo kiểu lược

• Độ phức tạp về thời gian: O (n log n) cho trường hợp tốt nhất. O (n ^ 2/2 ^ p) (p là một số gia tăng) cho trường hợp trung bình và O (n ^ 2) cho trường hợp xấu nhất.
• Mức độ phức tạp của không gian: O (1)

Đầu vào và Đầu ra

 Đầu vào:Danh sách dữ liệu chưa được sắp xếp:108 96 23 74 12 56 85 42 13 47 Đầu ra:Mảng trước Sắp xếp:108 96 23 74 12 56 85 42 13 47 Mảng sau Sắp xếp:12 13 23 42 47 56 74 85 96 108 

Thuật toán

 CombSort (mảng, kích thước) 

Đầu vào - Một mảng dữ liệu và tổng số trong mảng

Đầu ra - Mảng được sắp xếp

 Begin gap:=size flag:=true while gap ≠ 1 OR flag =true do gap =floor (gap / 1.3) // giá trị sàn sau khi chia if gap <1 then gap:=1 flag =false for i:=0 to size - gap -1 do if array [i]> array [i + gap] then swap array [i] with array [i + gap] flag =true; thực hiện xongEnd 

Ví dụ

 #include  #include  using namespace std; void display (int * array, int size) {for (int i =0; i  array [i + gap]) {swap (array [i], array [i + gap] ); cờ =true; }}}} int main () {int n; cout <<"Nhập số phần tử:"; cin>> n; int arr [n]; // tạo mảng với số phần tử cho trước cout <<"Nhập các phần tử:" <> arr [i]; } cout <<"Mảng trước khi Sắp xếp:"; hiển thị (arr, n); combSort (arr, n); cout <<"Mảng sau khi Sắp xếp:"; display (arr, n);} 

Đầu ra

 Nhập số phần tử:10 Nhập phần tử:108 96 23 74 12 56 85 42 13 47Mảng trước Sắp xếp:108 96 23 74 12 56 85 42 13 47Mảng sau Sắp xếp:12 13 23 42 47 56 74 85 96 108