Nội dung chính
Bài tập C - Sắp xếp Shell Sort trong C
Đề bài: Viết chương trình C sắp xếp một dãy số theo thứ tự tăng dần bằng thuật toán Shell Sort.
Lời giải
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
Dưới đây là chương trình C để giải bài sắp xếp Shell Sort trong C:
#include <stdio.h>
#include <stdbool.h>
#define MAX 10
int arr[MAX] = {6, 7, 0, 2, 8, 1, 3, 9, 4, 5};
//ham sap xep
void shellSort(){
int inner, outer;
int valueToInsert;
int interval = 1;
int elements = MAX;
int i = 0;
while(interval <= elements / 3) {
interval = interval * 3 + 1;
}
while(interval > 0) {
for(outer = interval; outer < elements; outer++) {
valueToInsert = arr[outer];
inner = outer;
while(inner > interval -1 && arr[inner - interval]
>= valueToInsert) {
arr[inner] = arr[inner - interval];
inner -= interval;
printf(" Di chuyen phan tu :%d\n",arr[inner]);
}
arr[inner] = valueToInsert;
printf(" Chen phan tu: %d, tai vi tri: %d\n", valueToInsert, inner);
}
interval = (interval -1) /3;
i++;
printf("Vong lap thu %d#:", i);
display();
}
}
void display() {
int i;
printf("[");
// Duyet qua tat ca phan tu
for(i = 0; i < MAX; i++) {
printf("%d ", arr[i]);
}
printf("]\n");
}
main() {
printf("Mang du lieu dau vao: ");
display();
printf("-----------------------------\n");
shellSort();
printf("-----------------------------\n");
printf("Mang sau khi da sap xep: ");
display();;
}
Chạy chương trình C trên cho kết quả như sau:
