Sắp xếp chèn

Sắp xếp chèn

•Sắp xếp chèn
•Cài đặt bằng mảng
•Cài đặt bằng danh sách moc nối
•Phân tích
•Bài tập

Sắp xếp bằng cách chèn:

Bắt đầu bằng một danh sách có thứ tự rỗng
Lần lượt chèn thêm các phần tử cần sắp xếp vào danh sách có thứ tự đó. (Trong quá trình chèn phải đảm bảo danh sách vẫn đúng thứ tự)
Kết thúc ta thu được danh sách các phần tử đã được sắp xếp theo thứ tự

Các phần tử cần sắp xếp: hen, cow, cat, ram, ewe, dog

Danh sách lưu trữ bằng mảng

void insert(int A[], int & end, int value) {
  if (end == ‐1) {
    end++;
    A[end] = value;
  } else {
    int pos = 0, i;
    while (A[pos] < value) pos++;
    for (i = end; i >= pos; i‐‐) A[i + 1] = A[i];
    A[pos] = value;
    end = end + 1;
  }
}

Hàm sắp xếp chèn, các phần tử cần sắp xếp được lưu ở mảng B, kết quả được lưu ở mảng A, n là số phần tử

void insertionSort(const int B[], int n, int A[]) {
  int end = ‐1;
  for (int i = 0; i < n; i++)
    insert(A, end, B[i]);
}

Lưu trữ bằng danh sách móc nối

typedef struct node {
  long masoSV;
  char hoten[30];
  char diachi[50];
  float diemTB;
  struct node * pNext;
}NODE;

NODE *list=NULL;

int insert(NODE * & pHead, long msSV, char ht[], char dc[], float diem) {
  NODE * ptr = (NODE * ) malloc(sizeof(NODE));
  ptr‐ > masoSV = msSV;
  strcpy(ptr‐ > hoten, ht);
  strcpy(ptr‐ > diachi, dc);
  ptr‐ > diemTB = diem;
  if (pHead == NULL) {
    ptr‐ > pNext = NULL;
    pHead = ptr;
  } else {
    if (pHead‐ > masoSV >= msSV) {
      ptr‐ > pNext = pHead;
      pHead = ptr;
    } else {
      NODE * preQ = pHead;
      NODE * q = pHead‐ > pNext;
      while (q != NULL && q‐ > masoSV < msSV) {
        preQ = q;
        q = q‐ > pNext;
      }
      ptr‐ > pNext = q;
      preQ‐ > pNext = ptr;
    }
  }
}

Phân tích

Thời gian thực hiện thuật toán chèn chính bằng tổng thời gian thực hiện các phép chèn vào danh sách có thứ tự.

Trong trường hợp cài đặt bằng mảng:

Danh sách rỗng thì cần 1 so sánh + 2 phép gán
Tại thời điểm danh sách có end (0≤i<n) phần tử cần:
- 1 phép so sánh
- (i-k+1) phép so sánh và k phép dịch chuyển vị trí (k là vị trí cần chèn) → tổng là i
- Hai phép gán

n là số lượng phần tử cần sắp xếp

Số lệnh và phép so sánh thực hiện :

Danh sách rỗng O(1)
Danh sách khác rỗng O(n 2 )

Trường hợp sử dụng danh sách móc nối

Nếu danh sách rỗng cần 5 lệnh gán + 1 so sánh + 2 gán
Danh sách khác rỗng (có k>0 phần tử) vòng lặp while thực hiện j lần (1≤j≤k) → trung bình là k/2
Giá trị của k sẽ là từ 1 đến n-1 (số lượng phần tử).

Phân tích

Khi cài đặt trên mảng, số lượng các phần tử phải dịch là lớn, nhất là khi sắp xếp với số lượng phần tử lớn, làm ảnh hưởng rất nhiều tới hiệu quả của thuật toán
Khi áp dụng trên danh sách móc nối thì không phải thực hiện dịch chuyển phần tử mà chỉ thay đổi giá trị một vài con trỏ
Sắp xếp chèn hiệu quả khi thực hiện trên danh sách móc nối !