Shell Sort

Kỹ thuật sắp xếp trình bao dựa trên sắp xếp chèn. Trong sắp xếp chèn đôi khi chúng ta cần phải dịch chuyển khối lớn để chèn một mục vào đúng vị trí. Sử dụng shell sort, chúng ta có thể tránh được một số lượng lớn dịch chuyển. Việc phân loại được thực hiện với một khoảng thời gian cụ thể. Sau mỗi lần vượt qua, khoảng thời gian được giảm xuống để tạo khoảng thời gian nhỏ hơn.

Sự phức tạp của Kỹ thuật Sắp xếp Shell

• Độ phức tạp về thời gian:O (n log n) đối với trường hợp tốt nhất và đối với các trường hợp khác, nó phụ thuộc vào chuỗi khoảng cách.
• Độ phức tạp của không gian:O (1)

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

 Đầu vào:Danh sách chưa được sắp xếp:23 56 97 21 35 689 854 12 47 66 Đầu ra:Mảng trước Sắp xếp:23 56 97 21 35 689 854 12 47 66 Dải sau khi Sắp xếp:12 21 23 35 47 56 66 97 689 854 

Thuật toán

 shellSort (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

 Bắt đầu cho khoảng trống:=size / 2, khi khoảng cách> 0 và khoảng cách được cập nhật với khoảng trống / 2 do for j:=gap to size– 1 do for k:=j-gap to 0, giảm theo giá trị khoảng trống do if array [k + gap]> =array [k] break else trao đổi mảng [k + gap] với array [k] done doneEnd 

Ví dụ

 #include  using namespace std; void swapping (int &a, int &b) {// hoán đổi nội dung của a và b int temp; temp =a; a =b; b =temp;} void display (int * array, int size) {for (int i =0; i 
 0; gap =gap / 2) {// ban đầu gap =n / 2, giảm theo gap / 2 for (j =gap; j  =0; k - =gap) {if (arr [k + gap]> =arr [k]) break; hoán đổi khác (arr [k + gap], arr [k]); }}}} 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); shellSort (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 các phần tử:23 56 97 21 35 689 854 12 47 66Mảng trước Sắp xếp:23 56 97 21 35 689 854 12 47 66Mảng sau Sắp xếp:12 21 23 35 47 56 66 97 689 854