Đề tài Các thuật toán sắp xếp cơ bản

.................................................................... 2 4. SẮP XẾP NHANH (QUICK SORT) .............................................................................................................. 3 CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN 1. Sắp xếp chọn (Selection Sort) a. Ý tưởng: Xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. b. Giải thuật:  Bước 1: i = 1  Bước 2: Tìm phần tử a[Min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]  Bước 3: Hoán vị a[Min] và a[i]  Bước 4: Nếu i ≤ n-1 thì i = i + 1 và lặp lại bước 2, ngược lại thì c. Độ phức tạp: O(n2) d. Code tham khảo: void selectionSort(int a[], int n) { for (int i = 0; i <= n-2; ++i) { int Min = a[i]; for (int j = i+1; j <= n-1; ++j) { if (a[j] < Min) { Min = a[j]; int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } } } 2. Sắp xếp chèn (Insertion Sort) NGUYỄN CHÁNH ĐẠI – MAI PHƯỚC VINH – TẤT HUỲNH ANH KHÔI TRANG 1 CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN a. Ý tưởng: Sắp xếp chèn là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ hai, so với các quân đứng trước nó để chèn vào vị trí thích hợp. b. Giải thuật:  Bước 1: i = 1  Bước 2: Lần lượt so sánh và đổi chỗ (nếu cần) từ phần tử kế bên phần tử đang xét đến hết mảng  Bước 3: i = i + 1  Bước 4: Nếu i < n thì quay lại bước 2, ngược lại thì dừng c. Độ phức tạp: O(n2) d. Code tham khảo: void insertionSort(int a[], int n) { int key; for (int i = 1; i < n; ++i){ key = a[i]; int x = i-1; while (x >= 0 && a[x] > key){ a[x+1] = a[x]; --x; } a[x+1] = key; } } 3. Sắp xếp nổi bọt (Bubble Sort) a. Ý tưởng: Xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. NGUYỄN CHÁNH ĐẠI – MAI PHƯỚC VINH – TẤT HUỲNH ANH KHÔI TRANG 2 CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN b. Giải thuật:  Bước 1: i = 0  Bước 2: Lần lượt so sánh và đổi chổ (nếu cần) từ phải sang trái đối với các phần từ từ a[n] đến a[i]  Bước 3: i = i + 1  Bước 4: Nếu i < n thì quay lại Bước 2, ngược lại dừng. c. Độ phức tạp: O(n2) d. Code tham khảo void BubbleSort(int a[], int n){ for (int i = 0; i < n-1; ++i){ for (int j = i+1; j < n; ++j) { if (a[i] > a[j]) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } } } 4. Sắp xếp nhanh (Quick Sort) a. Ý tưởng: Tìm cách chia đôi dãy ban đầu bằng cách chọn ra một phần tử là chốt (pivot). Từ dãy ban đầu, tất cả phần tử nhỏ hơn phần tử chốt thì đưa về bên trái dãy, tất cả các phần tử lớn hơn hoặc bằng phần tử chốt thì đưa về bên phải dãy. Sau bước này ta có phần tử chốt là đứng đúng vị trí. Dãy ban đầu phân chia làm hai dãy con nằm hai bên chốt. Tiếp tục phân chia các dãy con theo cách tương tự đến khi mọi dãy con đều có độ dài bằng 1. Có thể lựa chọn phần tử chốt nằm đầu, cuối hay giữa dãy. Ở đây ta sẽ lựa chọn phần tử chốt nằm gần giữa dãy nhất. b. Giải thuật: NGUYỄN CHÁNH ĐẠI – MAI PHƯỚC VINH – TẤT HUỲNH ANH KHÔI TRANG 3 CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN  Bước 1: pivot = a[(l + r) / 2]  Bước 2: i = l; j = r  Bước 3:  Nếu a[i] < pivot thì i = i + 1  Nếu a[j] > pivot thì j = j – 1  Bước 4: Nếu i ≥ j thì đổi chỗ a[i] với a[j], quay về bước 3  Bước 5: Lặp lại từ Bước 1 đến Bước 4 với đoạn a[l] đến a[j] và a[i] đến a[r] cho đến khi tất cả đoạn có độ dài là 1. c. Độ phức tạp:  Trường hợp tốt nhất: O(nlog2n)  Trường hợp xấu nhất: O(n2)  Trường hợp trung bình: O(nlog2n) d. Code tham khảo: void quickSort(int a[], int l, int r) { if (l >= r) return; int pivot = a[(l + r) / 2]; int i = l, j = r; while (i <= j) { while (a[i] < pivot) ++i; while (a[j] > pivot) --j; if (i <= j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; ++i; --j; } } quickSort(a, l, j); quickSort(a, i, r); NGUYỄN CHÁNH ĐẠI – MAI PHƯỚC VINH – TẤT HUỲNH ANH KHÔI TRANG 4 CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN } NGUYỄN CHÁNH ĐẠI – MAI PHƯỚC VINH – TẤT HUỲNH ANH KHÔI TRANG 5