Insert Sort

Cấu trúc dữ liệu và giải thuật - Sắp xếp

Đề bài: Viết chương trình sắp xếp các phần tử trong mảng 1 chiều bằng thuật toán Insert Sort.

Nhận xét:

Bất luận trình trạng cụ thể của dãy a[] đã cho ra sao, ta cũng luôn nhìn thấy một đoạn con của dãy này đã có trật tự
Dãy hay một đoạn con  chỉ gồm 1 phần tử duy nhất xem như đã có trật tự.

Ý tưởng:

Dãy a[] đã cho a(1), a(2), …a(n) có đoạn con chỉ gồm 1 phần tử a(1) đã có trật tự (nhận xét trên). Bây giờ ta chỉ việc thêm a(2) vào đoạn con a(1) ta được a(1)a(2) đã được sắp xếp; tiếp điếm thêm a(3) vào đoạn a(1)a(2). Làm đến khi không còn phần tử nào cần chèn thì kết thúc. Kết quả: ta sẽ thu được 1 dãy tăng (giảm)

Các bước thực hiện:

• Khởi tạo “vtchen=i-1”;
• Khởi trị cho phần tử cần chèn là x=a[j]
• Vòng lặp trong: thực hiện lặp các việc sau khi “vtchen>=0” và phần tử cần chèn x<a[vtchen]
• Đẩy các phần tử sang phải một vị trí để tìm chỗ thích hợp chèn x vào đoạn con đã có trật tự cần sử dụng phép gán:  a[vtchen+1]=a[vtchen]
• Sau mỗi lần thực hiện Bước 4, giảm vị trí chèn  (vtchen=vtchen-1)
• Chèn x vào vị trí đã tìm được thích hợp. (a[vtchen+1]=x)
• Vòng lặp trong kết thúc khi vtchen vượt ngoài phạm vi dãy và “x=a[vtchen]”

Cài đặt:

#include<iostream> #include<math.h> using namespace std; void nhap(int a[],int &n) { cout<<"moi nhap so phan tu "; cin>>n; for (int i=0;i<n;i++) { cin>>a[i]; } } void xuat (int a[],int n) { for(int i=0;i<n;i++) { cout<<a[i]<<" "; } } void swap(int &a,int &b) { int tam=a;a=b;b=tam; } void insertsort(int a[],int n) { int vtchen,x; for(int i=0;i<n;i++) { x=a[i]; vtchen=i-1; while(vtchen>=0&&a[vtchen]>x) { a[vtchen+1]=a[vtchen]; vtchen--; } a[vtchen+1]=x; } } int main() { int a[1000],n; nhap(a,n); insertsort(a,n); cout<<"kq: "; xuat(a,n); }

Kết quả khi chạy chương trình:

Độ phức tạp của thuật toán:

• Tốt nhất: O(n-1)
• Xấu nhất: O(n(n-1)/2)

Được viết bởi Đinh Quang Trưởng

cấu trúc dữ liệu và giải thuật sắp xếp 3:47 PM