Các thuật toán sắp xếp phần I

I, Bài toán sắp xếp

1, Định nghĩa

  • Theo D.Knuth: 40% thời gian hoạt động của máy tình là sắp xếp.
  • Do đó tìm hiểu về bài toán sắp xếp và các giải thuật tối ưu là một tác vụ thiết yếu và rất quan trọng.
  • Sắp xếp (sorting) là quá trình tổ chức lại tập dữ liệu theo thứ tự tăng dần hoặc giảm dần.
  • Dữ liệu cần sắp xếp có thể là:
    • Số (Number).
    • Chuỗi ký tự (String).
    • Object.
  • Bài toán sắp xếp có dạng:
    • Input: dãy n số A = (a1, a2, a3,..., an).
    • Output: một hoán vị (dãy được sắp xếp lại) theo thứ tự tăng dần của các phần tử có dạng (b1, b2, b3,..., bn) thoả mãn: b1 <= b2 <= b3 <= ... <= bn.
  • Bài toán sắp xếp được sắp xếp ở rất nhiều lĩnh vực:
    • Quản trị cơ sở dữ liệu.
    • Khoa học và kĩ thuật.
    • Máy tìm kiếm.
    • Các thuật toán lập lịch như thiết kế chương trình dịch, truyền thông…
    • …

2, Phân loại

  • Chúng ta có thể chia giải thuật sắp xếp thành hai loại.
  • Sắp xếp trong: đòi hỏi đưa toàn tập dữ liệu vào bộ nhớ trong của máy tính.
  • Sắp xếp ngoài: tập dữ liệu không thể cùng một lúc đưa vào hết bộ nhớ trong nhưng có thể đọc từng phần vào bộ nhớ ngoài.

3, Đặc trưng

  • Tại chỗ (in place): giải thuật sử dụng một lượng bộ nhớ không đổi, nghĩa là bộ nhớ không phụ thuộc vào độ dài của dãy cần sắp xếp.

II, Các thao tác cơ bản trong giải thuật sắp xếp

  • Giải thuật sắp xếp thường sử dụng hai thao tác cơ bản là đổi chỗ và so sánh.

1, Đổi chỗ

1
2
3
4
5
void swap(int a, int b){
    val temp = a;
    a = b;
    b = temp;
}
  • Thời gian tính của thao tác là Ο(1).

2, So sánh

  • Thao tác so sánh a và b trả về true nếu a lớn hơn hoặc bằng b. Nếu không sẽ trả về false.
1
2
3
4
boolean compare(int a, int b){
    if(a >= b) return true;
    return false;
}

III, Sơ lược về các giải thuật sắp xếp

  • Chúng ta sẽ đi tìm hiểu hai loại giải thuật sắp xếp:
    • Simple algorithm: bao gồm insertion sort, selection sort và bubble sort.
    • Fancier algorithm: bao gồm merge sort, quịck sort.

IV, Insertion sort

  • Thuật toán:
    • Tại bước k = 1, 2, 3,..., n, đưa phần tử tại k về đúng vị trí trong dãy có k phần tử đầu tiên.
    • Sau bước k, k phần tử đầu tiên được sắp xếp.
1
2
3
4
5
6
7
8
9
10
11
void createInsertionSort(int a[], int n){
    for(int i = 0; i < n; i++){
        int last = a[i];
        int j = i;
        while(j > 0 && a[j - 1] > last){
            a[j] = a[j -1];
            j = j - 1;
        }
        a[j] = last;
    }
}
  • Phân tích thời gian tính của giải thuật:
    • Best case: xảy ra khi a là mảng đã được sắp xếp. Giải thuật sử dụng 0 phép đổi chỗ, n - 1 phép so sánh.
    • Average case: n.n/4 phép đổi chỗ và phép so sánh.
    • Worst case: xảy ra khi các phần tử của a có thứ tự ngược với thứ tự cần sắp xếp. Giải thuật sử dụng n.n/2 phép so sánh và đổi chỗ.
  • Giải thuật có thời gian tính của best case là tốt nhất.
  • Giải thuật nên được sử dụng cho các tập hợp gần như đã được sắp xếp (các phần tử đứng gần đúng với vị trí cần sắp xếp).