Shell Sort là một giải thuật sắp xếp mang lại hiệu quả cao dựa trên giải thuật sắp xếp chèn [Insertion Sort]. Giải thuật này tránh các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp xếp chọn [nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử lớn hơn bên trái].
Đầu tiên, giải thuật này sử dụng giải thuật sắp xếp chọn trên các phần tử có khoảng cách xa nhau, sau đó sắp xếp các phần tử có khoảng cách hẹp hơn. Khoảng cách này còn được gọi là khoảng [interval] – là số vị trí từ phần tử này tới phần tử khác. Khoảng này được tính dựa vào công thức Knuth như sau:
h = h * 3 + 1 trong đó: h là Khoảng [interval] với giá trị ban đâu là 1
Chương trình Shell Sort trong C
Quảng cáo
include
include
define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7}; void printline[int count]{ int i; for[i = 0;i temp;j=j-gap]{
a[j]=a[j-gap];
}
a[j]=temp;
}
}
printf["Sap Xep Hoan Thanh\n"];
for[i=0;i hi + 1 và hk = 1.