Nội dung chính
Bài tập C - Sắp xếp chèn (Insertion 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 chèn (Insertion Sort).
Lời giải
Sắp xếp chèn là một giải thuật sắp xếp dựa trên so sánh in-place. Ở đây, một danh sách con luôn luôn được duy trì dưới dạng đã qua sắp xếp. Sắp xếp chèn là chèn thêm một phần tử vào danh sách con đã qua sắp xếp. Phần tử được chèn vào vị trí thích hợp sao cho vẫn đảm bảo rằng danh sách con đó vẫn sắp theo thứ tự.
Với cấu trúc dữ liệu mảng, chúng ta tưởng tượng là: mảng gồm hai phần: một danh sách con đã được sắp xếp và phần khác là các phần tử không có thứ tự. Giải thuật sắp xếp chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, và các phần tử không có thứ tự sẽ được di chuyển và được chèn vào vị trí thích hợp trong danh sách con (của cùng mảng đó).
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.
Dưới đây là chương trình C để giải bài sắp xếp chèn (Insertion 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};
void insertionSort() {
int valueToInsert;
int holePosition;
int i;
// lap qua tat ca cac so
for(i = 1; i < MAX; i++){
// chon mot gia tri de chen
valueToInsert = arr[i];
// lua chon vi tri de chen
holePosition = i;
// kiem tra xem so lien truoc co lon hon gia tri duoc chen khong
while (holePosition > 0 && arr[holePosition-1] > valueToInsert) {
arr[holePosition] = arr[holePosition-1];
holePosition--;
printf(" Di chuyen phan tu : %d\n" , arr[holePosition]);
}
if(holePosition != i) {
printf(" Chen phan tu : %d, tai vi tri : %d\n" , valueToInsert, holePosition);
// chen phan tu tai vi tri chen
arr[holePosition] = valueToInsert;
}
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");
insertionSort();
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:
