A. KIẾN THỨC CHUNG

– Sắp xếp trong là sự sắp xếp dữ liệu được tổ chức trong bộ nhớ trong của máy tính, ở đó ta có thể sử dụng khả năng truy nhập ngẫu nhiên của bộ nhớ và do vậy sự thực hiện rất nhanh.

– Sắp xếp ngoài là sự sắp xếp được sử dụng khi số lượng đối tượng cần sắp xếp lớn không thể lưu trữ trong bộ nhớ trong mà phải lưu trữ trên bộ nhớ ngoài. Cụ thể là ta sẽ sắp xếp dữ liệu được lưu trữ trong các tập tin.

B. CÁC PHƯƠNG PHÁP SẮP XẾP ĐƠN GIẢN

1. Sắp xếp chọn (Selection Sort)

a. Lý thuyết

– Ðây là phương pháp sắp xếp đơn giản nhất được tiến hành như sau:

§ Bước 0, chọn phần tử có khóa nhỏ nhất trong n phần tử từ a[0] đến a[n-1] và hoán vị nó với phần tử a[0].

§ Bước 1, chọn phần tử có khóa nhỏ nhất trong n-1 phần tử từ a[1] đến a[n-1] và hoán vị nó với a[1].

§ Tổng quát ở bước thứ i, chọn phần tử có khoá nhỏ nhất trong n-i phần tử từ a[i] đến a[n-1] và hoán vị nó với a[i].

§ Sau n-1 bước này thì mảng đã được sắp xếp.

– Phương pháp này được gọi là phương pháp chọn bởi vì nó lặp lại quá trình chọn phần tử nhỏ nhất trong số các phần tử chưa được sắp.

– Để chọn phần tử có khoá nhỏ nhất trong n-i phần tử từ a[i] đến a[n-1] ta làm như sau:

§ Đầu tiên ta đặt khoá nhỏ nhất là khoá của a[i] (lowkey = a[i].key) và chỉ số của phần tử có khoá nhỏ nhất là i (lowindex = i).

§ Xét các phần tử a[j] (với j từ i+1 đến n-1), nếu khoá của a[j] nhỏ hơn khoá nhỏ nhất (a[j].key < lowkey) thì đặt lại lại khoá nhỏ nhất là khoá của a[j] (lowkey = a[j].key) và chỉ số của phần tử có khoá nhỏ nhất là j (lowindex = j).

§ Khi đã xét hết các a[j] (j>n-1) thì phần tử có khoá nhỏ nhất là a[lowindex].

b. Ví dụ

Sắp xếp mảng gồm 10 mẩu tin có khóa là các số nguyên: 5, 6, 2, 2, 10, 12, 9, 10, 9 và 3

Bước 0: Ta chọn được phần tử có khoá nhỏ nhất (bằng 2) trong các phần tử từ a[0] đến a[9] là a[2], hoán đổi a[0] và a[2] cho nhau. Sau bước này thì a[0] có khoá nhỏ nhất là 2.

Bước 1: Ta chọn được phần tử có khoá nhỏ nhất (bằng 2) trong các phần tử từ a[1] đến a[9] là a[3], hoán đổi a[1] và a[3] cho nhau.

Tiếp tục quá trình này và sau 9 bước thì kết thúc.

Bảng sau ghi lại các giá trị khoá tương ứng với từng bước. Trong đó, các ô chữ vàng trên nền đỏ thể hiện khoá nhỏ nhất tại mỗi bước.

       KhóaBước a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
Ban đầu 5 6 2 2 10 12 9 10 9 3
Bước 0 2 6 5 2 10 12 9 10 9 3
Bước 1 2 5 6 10 12 9 10 9 3
Bước 2 3 6 10 12 9 10 9 5
Bước 3 5 10 12 9 10 9 6
Bước 4 6 12 9 10 9 10
Bước 5 9 12 10 9 10
Bước 6 9 10 12 10
Bước 7 10 12 10
Bước 8 10 12
Kết quả 2 2 3 5 6 9 9 10 10 12

c. Lưu đồ

d. Chương trình

e. Đánh giá

2. Sắp xếp xen (Insertion Sort)

a. Lý thuyết

Trước hết ta xem phần tử  a[0] là một dãy đã có thứ tự.

§         Bước 1, xen phần tử a[1] vào danh sách đã có thứ tự a[0] sao cho a[0], a[1] là một danh sách có thứ tự.

§         Bước 2, xen phần tử a[2] vào danh sách đã có thứ tự a[0], a[1] sao cho a[0], a[1], a[2] là một danh sách có thứ tự.

§         Tổng quát, bước i, xen phần tử a[i] vào danh sách đã có thứ tự a[0], a[1], … a[i-1] sao cho a[0], a[1],.. a[i] là một danh sách có thứ tự.

§         Phần tử đang xét a[j] sẽ được xen vào vị trí thích hợp trong danh sách các phần tử đã được sắp trước đó a[0],a[1],..a[j-1] bằng cách so sánh khoá của a[j] với khoá của a[j-1] đứng ngay trước nó. Nếu khoá của a[j] nhỏ hơn khoá của a[j-1] thì hoán đổi a[j-1] và a[j] cho nhau và tiếp tục so sánh khoá của a[j-1] (lúc này a[j-1] chứa nội dung của a[j]) với khoá của a[j-2] đứng ngay trước nó…

b. Ví dụ

Sắp xếp mảng gồm 10 mẩu tin có khóa là các số nguyên: 5, 6, 2, 2, 10, 12, 9, 10, 9 và 3.

§         Bước 1: Xen a[1] vào dãy chỉ có một phần tử a[0] ta được dãy hai phần tử a[0]..a[1] có thứ tự. Việc xen này thực ra không phải làm gì cả vì hai phần tử a[0], a[1] có khoá tương ứng là 5 và 6 đã có thứ tự.

§         Bước 2: Xen a[2] vào dãy a[0]..a[1] ta được dãy ba phần tử a[0]..a[2] có thứ tự. Việc xen này được thực hiện bằng cách: so sánh khoá của a[2] với khoá của a[1], do khoá của a[2] nhỏ hơn khoá của a[1] (2<6) nên hoán đổi a[2] và a[1] cho nhau. Lại so sánh khoá của a[1] với khoá của a[0], do khoá của a[1] nhỏ hơn khoá của a[0] (2<5) nên hoán đổi a[1] và a[0] cho nhau.

Tiếp tục quá trình này và sau 9 bước thì kết thúc.

   KhóaBước a[0] a[1] a[2] a[3] a[4] a[5] a[6] A[7] a[8] a[9]
Ban đầu 5 6 2 2 10 12 9 10 9 3
Bước 1 5 6
Bước 2 2 5 6
Bước 3 2 2 5 6
Bước 4 2 2 5 6 10
Bước 5 2 2 5 6 10 12
Bước 6 2 2 5 6 9 10 12
Bước 7 2 2 5 6 9 10 10 12
Bước 8 2 2 5 6 9 9 10 10 12
Bước 9 2 2 3 5 6 9 9 10 10 12

c. Lưu đồ

d. Chương trình

e. Đánh giá

3. Sắp xếp “nổi bọt” (Bubble Sort)

a. Lý thuyết

Chúng ta tưởng tượng rằng các mẩu tin được lưu trong một mảng dọc, qua quá trình sắp, mẩu tin nào có khóa “nhẹ” sẽ được nổi lên trên. Chúng ta duyệt tòan mảng, từ dưới lên trên. Nếu hai phần tử ở cạnh nhau mà không đúng thứ tự tức là nếu phần tử “nhẹ hơn” lại nằm dưới thì phải cho nó “nổi lên” bằng cách đổi chỗ hai phần tử này cho nhau. Cụ thể là:

§         Bước 1: Xét các phần tử a[j] (j giảm từ n-1 đến 1), so sánh khoá của a[j] với khoá của a[j-1]. Nếu khoá của a[j] nhỏ hơn khoá của a[j-1] thì hoán đổi a[j] và a[j-1] cho nhau. Sau bước này thì a[0] có khoá nhỏ nhất.

§         Bước 2: Xét các phần tử a[j] (j giảm từ n-1 đến 2), so sánh khoá của a[j] với khoá của a[j-1]. Nếu khoá của a[j] nhỏ hơn khoá của a[j-1] thì hoán đổi a[j] và a[j-1] cho nhau. Sau bước này thì a[1] có khoá nhỏ thứ 2.

§         …

Sau n-1 bước thì kết thúc

b. Ví dụ

Bảng minh hoạ ví dụ sắp xếp “nổi bọt”

      Khóa
Bước
a[0] a[1] a[2] a[3] a[4] A[5] a[6] a[7] a[8] a[9]
Ban đầu 5 6 2 2 10 12 9 10 9 3
Bước 1 2 5 6 2 3 10 12 9 10 9
Bước 2   2 5 6 3 9 10 12 9 10
Bước 3     3 5 6 9 9 10 12 10
Bước 4       5 6 9 9 10 10 12
Bước 5         6 9 9 10 10 12
Bước 6           9 9 10 10 12
Bước 7             9 10 10 12
Bước 8               10 10 12
Bước 9                 10 12
Kết quả 2 2 3 5 6 9 9 10 10 12

c. Lưu đồ

d. Chương trình

e. Đánh giá

4. QuickSort

a. Lý thuyết

Thuật toán QuickSort

Ðể sắp xếp mảng a[i]..a[j] ta tiến hành các bước sau:

• Xác định chốt.
• Phân hoạch mảng đã cho thành hai mảng con a[i]..a[k-1] và a[k]..a[j].
• Sắp xếp mảng a[i]..a[k-1] (Ðệ quy).
• Sắp xếp mảng a[k]..a[j] (Ðệ quy).

Quá trình đệ quy sẽ dừng khi không còn tìm thấy chốt.

Phương pháp chọn chốt: Chọn giá trị khóa lớn nhất trong hai phần tử có khóa khác nhau đầu tiên kể từ trái qua. Nếu mảng chỉ gồm một phần tử hay gồm nhiều phần tử có khóa bằng nhau thì không có chốt.

b. Ví dụ

c. FindPivot

Phân tích hàm FindPivot

int FindPivot(int i,int j)

{         keytype  firstkey;

int k ;

/*1*/   k = i+1;

/*2*/   firstkey = a[i].key;

/*3*/   while ( (k <= j) && (a[k].key == firstkey) ) k++;

/*4*/   if (k > j)  return -1;

else

/*5*/      if (a[k].key>firstkey) return k; else return i;

}

Trong hàm FindPivot các lệnh /*1*/, /*2*/, /*3*/ và /*4*/ nối tiếp nhau, trong đó chỉ có lệnh WHILE là tốn nhiều thời gian nhất do đó thời gian thực hiện của hàm FindPivot phụ thuộc vào thời gian thực hiện của lệnh này. Trong trường hợp xấu nhất (không tìm thấy chốt) thì k chạy từ i+1 đến j, tức là vòng lặp thực hiện j-i lần, mỗi lần O(1) do đó tốn j-i thời gian. Đặc biệt khi i=0 và j=n-1, thì thời gian thực hiện là n-1 hay T(n) = O(n).

d. Partition

Trong hàm Partition các lệnh /*1*/, /*2*/, /*3*/ và /*7*/ nối tiếp nhau, trong đó thời gian thực hiện của lệnh /*3*/ là lớn nhất (các lệnh /*1*/, /*2*/ và /*7*/ chỉ tốn O(1)), do đó thời gian thực hiện của lệnh /*3*/ sẽ là thời gian thực hiện của hàm Partition.

Các lệnh /*4*/, /*5*/ và /*6*/ là thân của lệnh /*3*/, trong đó lệnh /*6*/ lấy O(1) thời gian.

Lệnh /*4*/ và lệnh /*5*/ thực hiện việc di chuyển L sang phải và R sang trái cho đến khi L và R gặp nhau, thực chất là duyệt các phần tử mảng, mỗi phần tử một lần, mỗi lần tốn O(1) thời gian. Tổng cộng việc duyệt này tốn j-i thời gian. Vòng lặp /*3*/ thực chất là để xét xem khi nào thì duyệt xong, do đó thời gian thực hiện của lệnh /*3*/ chính là thời gian thực hiện của hai lệnh /*4*/ và /*5*/ và do đó là j-i. Đặc biệt khi i=0 và j=n-1 ta có T(n) = O(n).

d. Thủ tục QuickSort

e. Đánh giá

QuickSort lấy O(nlogn) thời gian để sắp xếp n phần tử trong trường hợp tốt nhất và O(n2) trong trường hợp xấu nhất.

5. HeapSort:

a. Lý thuyết

Ðịnh nghĩa Heap: Cây sắp thứ tự bộ phận hay còn gọi là heap là cây nhị phân mà giá trị tại mỗi nút (khác nút lá) đều không lớn hơn giá trị của các con của nó.

Ta có nhận xét rằng nút gốc của cây sắp thứ tự bộ phận có giá trị nhỏ nhất.

d. Chương trình

e. Đánh giá

6. BinSort:

a. Lý thuyết

Nói chung các giải thuật đã trình bày ở trên đều có độ phức tạp là O(n2) hoặc O(nlogn). Tuy nhiên khi kiểu dữ liệu của trường khoá là một kiểu đặc biệt, chẳng hạn khoá là các số nguyên thì liệu chúng ta có thể có giải thuật sắp xếp nhanh hơn không?

Các trình bày ở các mục tiếp theo cho thấy, trong một số trường hợp, việc sắp xếp mảng gồm n mẩu tin có thể chỉ chiếm O(n) thời gian.

b. Ví dụ

d. Chương trình

void BinSort();

{

int i;

int j;

/*1*/ for (i=0; i<n; i++)

Insert(a[i], END(b[a[i].key]), b[a[i].key]);

/*2*/ for ( j= 1; j<m; j++)

Concatenate(b[0], b[j]);

}

e. Đánh giá

Trước hết thủ tục INSERT cần một thời gian O(1) để xen một phần tử vào trong danh sách. Do cách tổ chức danh sách có giữ con trỏ đến phần tử cuối cùng nên việc nối hai danh sách bằng thủ tục CONCATENATE cũng chỉ mất O(1) thời gian.

Ta thấy vòng lặp /*1*/ thực hiện n lần, mỗi lần tốn O(1) = 1 nên lấy O(n) đơn vị thời gian. Vòng lặp /*2*/ thực hiện m-1 lần, mỗi lần O(1) nên tốn O(m) đơn vị thời gian. Hai lệnh /*1*/ và /*2*/ nối tiếp nhau nên thời gian thực hiện của BinSort là T(n) = O(max(n,m)) = O(n) vì m £ n.