Tìm hiểu các giải thuật sắp xếp trên mảng

PHẦN MỞ ĐẦU 1 Lý do chọn đề tài. Một trong những vấn đề nền tảng của khoa học máy tính là sắp xếp một tập hợp các phần tử theo thứ tự cho trước nào đó.Và dữ liệu trong hệ thống thường không được sắp xếp theo một trật tự nhất định, vì vậy việc khai thác thông tin sẽ gặp khó khăn khi cần thiết. Có rất nhiều giải pháp cho vấn đề này, được biết đến như là các thuật toán sắp xếp.Ngoài những thuật toán sắp xếp tuy phức tạp nhưng có hiệu quả cao còn có những thuật toán đơn giản và rất rõ ràng và hiệu quả cũng không kém. Vậy em chọn đề tài “TÌM HIỂU CÁC GIẢI THUẬT SẮP XẾP TRÊN MẢNG ” để tìm hiểu rõ hơn về những thuật toán sắp xếp đơn giản như: Sắp nổi bọt(bubble sort), Sắp xếp chèn( Insertion sort), Sắp xếp lựa chọn(Selection sort)… 2. Mục tiêu -Giới thiệu một số thuật toán sắp xếp cơ bản. -Phân tích,đánh giá độ phức tạp của các giải thuật sắp xếp. 3. Phạm vi nghiên cứu. - giải thuật và cài đặt các thuật toán sắp xếp trên mảng. 4. Phương pháp nghiên cứu - Nêu ý tưởng của thuật toán. - Tìm hiểu giải thuật. -Vẽ sơ đồ khối. - Mô phỏng thuật toán. -Phân tích độ phức tạp của thuật toán. -Cài đặt thuật toán. PHẦN NỘI DUNG CHƯƠNG 1:GIỚI THIỆU CÁC THUẬT TOÁN SẮP XẾP 1.Định nghĩa sắp xếp Sắp xếp là một quá trình biến đổi một danh sách các đối tượng thành một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóng vai trò quan trọng trong tìm kiếm dữ liệu. Chẳng hạn, nếu danh sách đã được sắp xếp theo thứ tự tăng dần (hoặc giảm dần), ta có thể sử dụng kỹ thuật tìm kiếm nhị phân hiệu quả hơn nhiều tìm kiếm tuần tự… Trong thiết kế thuật toán, ta cũng thường xuyên cần đến sắp xếp, nhiều thuật toán được thiết kế dựa trên ý tưởng xử lý các đối tượng theo một thứ tự xác định. Các thuật toán sắp xếp được chia làm 2 loại: sắp xếp trong và sắp xếp ngoài. Sắp xếp trong được thực hiện khi mà các đối tượng cần sắp xếp được lưu ở bộ nhớ trong của máy tính dưới dạng mảng. Do đó sắp xếp trong còn được gọi là sắp xếp mảng. Khi các đối tượng cần sắp xếp quá lớn cần lưu ở bộ nhớ ngoài dưới dạng file, ta cần sử dụng các phương pháp sắp xếp ngoài, hay còn gọi là sắp xếp file. Trong chương này, chúng ta trình bày các thuật toán sắp xếp đơn giản, các thuật toán này dòi hỏi thời gian O(n2) để sắp xếp mảng n đối tượng. Sau đó chúng ta đưa ra các thuật toán phức tạp và tinh vi hơn, nhưng hiệu quả hơn, chỉ cần thời gian O(nlogn). Mảng cần được sắp xếp có thể là mảng số nguyên, mảng các số thực, hoặc mảng các xâu ký tự. Trong trường hợp tổng quát, các đối tượng cần được sắp xếp chứa một số thành phần dữ liệu, và ta cần sắp xếp mảng các đối tượng đó theo một thành phần dữ liệu nào đó. Thành phần dữ liệu đó được gọi là khoá sắp xếp. Chẳng hạn, ta có một mảng các đối tượng sinh viên, mỗi sinh viên gồm các thành phần dữ liệu: tên, tuổi, chiều cao,…, và ta muốn sắp xếp các sinh viên theo thứ tự chiều cao tăng, khi đó chiều cao là khoá sắp xếp. 2. Giới thiệu các thuật toán sắp xếp 2.1. Sắp xếp nổi bọt (bubble sort) 2.1.1. Ý tưởng + Duyệt từ cuối mảng về đầu mảng, trong quá trình duyệt nếu phần tử ở dưới (đứng phía sau) nhỏ hơn phần tử đứng ngay trên (trước) nó thì theo nguyên tắc của bọt khí phần tử nhẹ sẽ bị “trồi” lên phía trên phần tử nặng (hai phần tử này sẽ được đổi chỗ cho nhau). Kết quả là phần tử nhỏ nhất (nhẹ nhất) sẽ được đưa lên (trồi lên) trên bề mặt (đầu mảng) rất nhanh. + Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Do vậy, sau n–1 lần đi thì tất cả các phần tử trong mảng M sẽ có thứ tự tăng. 2.1.2. Thuật toán Đầu vào: Dãy (M,n) Đầu ra: Dãy (M,n) đã được sắp xếp Bước 1 : i = 0 Bước 2 : j = n Trong khi (j > i) thực hiện: Nếu M[j]<M[j-1] Đổi chổ(M[i],M[j-1]) j = j-1 Bước 3 : i = i+1 Nếu i =n: Hết dãy. Dừng Ngược lại: Lặp lại Bước 2 2.1.3. Sơ đồ khối j=n-1 M[j]<M[j-1] Bắt đầu i =0 i<n-1 i = i+1 j > i Swap(M[j], M[j-1] j = j -1 Kết thúc n,mảng M F T F T F T  2.1.4. Phân tích độ phức tạp của thuật toán + Trong mọi trường hợp: Số phép gán: G = 0 Số phép so sánh: S = (n-1) + (n-2) + … + 1 = ½n(n-1) + Trong trường hợp tốt nhất: khi mảng ban đầu đã có thứ tự tăng: Số phép hoán vị: Hmin = 0 + Trong trường hợp xấu nhất: khi mảng ban đầu đã có thứ tự giảm: Số phép hoán vị: Hmin = (n-1) + (n-2) + … + 1 = ½n(n-1) + Số phép hoán vị trung bình: Havg = ¼n(n-1) -Độ phức tạp của thuật toán. + Thuật toán sắp xếp nổi bọt khá đơn giản, dễ hiểu và dễ cài đặt. + Trong thuật toán sắp xếp nổi bọt, mỗi lần đi từ cuối mảng về đầu mảng thì phần tử nhẹ được trồi lên rất nhanh trong khi đó phần tử nặng lại “chìm” xuống khá chậm chạp do không tận dụng được chiều đi xuống (chiều từ đầu mảng về cuối mảng). + Thuật toán nổi bọt không phát hiện ra được các đoạn phần tử nằm hai đầu của mảng đã nằm đúng vị trí để có thể giảm bớt quãng đường đi trong mỗi lần đi. + số lượng các phép so sánh xãy ra không phụ thuộc vào tình trạng của dãy số ban đầu. 2.1.5. Mô phỏng thuật toán Ví dụ: Cho dãy số: 17 2 15 5 1 Sắp xếp dãy tăng dần. 1 17 2 5 15 i=1: 1 2 17 15 5 i=2: 5 1 2 1 2 17 15 i=3 5 2 1 17 15 i=4: 17 15 5 2 1 kết quả: 2.2. Sắp xếp chèn( Insertion sort) 2.2.1. Ý tưởng Thuật toán sắp xếp chèn làm việc cũng giống như tên gọi - Nó thực hiện việc quét một tập dữ liệu, với mỗi phân tử, thủ tục kiểm tra và chèn phần tử đó vào vị trí thích hợp trong danh sách đích (chứa các phần tử đứng trước nó đã được sắp xếp) được tiến hành.  Phương pháp dễ dàng nhất để thực hiện thuật toán này là dùng hai vùng chứa dữ liệu khác nhau - tập dữ liệu nguồn và tập dữ liệu mà các phần tử đã sắp xếp được chèn vào. Tuy nhiên để tiết kiệm bộ nhớ, hầu hết các ứng dụng đều chỉ sử dụng một tập dữ liệu duy nhất. Thuật toán được tiến hành bằng cách dịch chuyển phân tử hiện tại đang xét tuần tự qua những phân tử ở vùng dữ liệu phía trước đã được sắp xếp, phép hoán vị nó với phần tử liền kề được thực hiện một cách lặp lại cho tới khi tiến tới được vị trí thích hợp. 2.2.2. Thuật toán Đầu vào: Dãy (M,n) Đầu ra: Dãy (M,n) đã được sắp xếp Bước 1: i = 1 Bước 2: x = M[i]; Tìm vị trí pos thích hợp trong đoạn M[1] đến M[i-1] để chèn M[i] vào Bước 3: Dời chỗ các phần tử từ M[pos] đến M[i-1] Bước 4: M[pos] = x Bước 5: i = i+1 Nếu i < n : Lặp lại Bước 2 Ngược lại : Dừng 2.2.3. Sơ đồ khối i ++ Pos>=0 M[pos]>x M[pos+1] = M[pos] Pos -- Bắt đầu i = 1 i < n x = M[i] pos = i - 1 M[pos+1] = x n,mảng M Kết thúc F T F T  2.2.4. Phân tích độ phức tạp của thuật toán - Trường hợp tốt nhất, khi mảng M ban đầu đã có thứ tự tăng: Số phép gán: Gmin = 2×(n-1) Số phép so sánh: Smin = 1+2+…+(n-1) = n×(n-1)/2 Số phép hoán vị: Hmin = 0 - Trường hợp xấu nhất, khi mảng M ban đầu luôn có phần tử nhỏ nhất trong n-k phần tử còn lại đứng ở vị trí sau cùng sau mỗi lần hoán vị: Số phép gán: Gmax = [2×(n-1)]+[ 1+2+…+(n-1)] = [2×(n-1)] + [n×(n-1)/2] Số phép so sánh: Smax = (n-1) Số phép hoán vị: Hmax = 0 - Trung bình: Số phép gán: Gavg = 2×(n-1) + [n×(n-1)/4] Số phép so sánh: Savg = [n×(n-1)/2 + (n-1)]/2 = (n+2)×(n-1)/4 Số phép hoán vị: Havg = 0 -Độ phức tạp của thuật toán. +Các phép so sánh xãy ra trong mỗi vòng lặp tìm vị trí thích hợp pos.mỗi lần xác định vị trí pos đang xét không thích hợp thì dời phần tử M[pos-1] đến vị trí pos. +Giải thuật thực hiện tất cả n-1 vòng lặp tìm pos do số lượng phép so sánh và dời chổ này phụ thuộc vào tình trạng của dãy số ban đầu nên chỉ có thể ước lượng từng trường hợp cụ thể như sau: +Do với mỗi phân tử, insertion sort cần thực hiện so sánh với các phần tử trước nó nên tối đa số lần duyệt dữ liệu là !n. Vì vậy cũng giống như Bubble sort Insertion sort được coi là có độ phức tạp O(n2). Mặc dù có cùng độ phứctạp,Insertion sort hiệu quả hơn gần như hai lần so với Bubble sort, tuy nhiên vẫn không hiệu quả với tập dữ liệu lớn. 2.2.5. Mô phỏng thuật toán Ví dụ: Cho dãy số: 12 2 8 5 1 Sắp xếp dãy tăng dần. 8 5 1 12 2 i=1: 1 5 8 12 2 i=2: 1 12 8 5 2 i=3 : 12 8 5 2 1 i=4: 12 8 5 2 1 kết quả: 2.3. Sắp xếp lựa chọn(Selection sort) 2.3.1. Ý tưởng Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đứng ở đầu dãy. 2.3.2. Thuật toán Đầu vào: Dãy (M,n) Đầu ra: Dãy (M,n) đã được sắp xếp Bước 1:   i = 0 Bước 2:  Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ M[i] đến M[n] Bước 3 :  Đổi chỗ M[min] và M[j] Bước 4 :  Nếu i < n-1 thì i = i+1; Lặp lại Bước 2   Ngược lại: Dừng 2.3.3. Sơ đồ khối Bắt đầu Min i,j i = 0 i<n-1 Kết thúc Min = 1 j < n a[j]<a[min] j = j+1 min = j Swap a[min], a[j] j = j+1 i = i+1 F T T F T F T  2.3.4. Phân tích độ phức tạp của thuật toán -Trong mọi trường hợp: Số phép so sánh: S = (n-1)+(n-2)+…+1 = n×(n-1)/2 Số phép hoán vị: H = n-1 + Trường hợp tốt nhất, khi mảng M ban đầu đã có thứ tự tăng: Số phép gán: Gmin = 2×(n-1) + Trường hợp xấu nhất, khi mảng M ban đầu đã có thứ tự giảm dần: Số phép gán: Gmax = 2×[n+(n-1)+ … +1] = n×(n+1) + Trung bình: Số phép gán: Gavg = [2×(n-1)+n×(n+1)]/2 = (n-1) + n×(n+1)/2 -Độ phức tạp của thuật toán. + Ở lượt thứ i cần (n-1) lần so sánh để xác định phần tử nhỏ nhất hiện hành. +Số lượng phép so sánh không phụ thuộc vào tình trạng ban đầu của dãy số. + Trong mọi trường hợp số lần so sánh là: + Số lần hoán vị(mỗi hoán vị bằng 3 phép gán) phụ thuộc vào tình trạng ban đầu của dãy số. TRƯỜNG HỢP SỐ LẦN SO SÁNH SỐ PHÉP GÁN Tốt nhất n(n-1)/2 0 Xấu nhất n(n-1)/2 3n 2.3.5. Mô phỏng thuật toán Ví dụ: Cho dãy số: 12 2 15 5 1 Sắp xếp dãy tăng dần. 1 12 2 5 15 i=0: 1 15 12 2 5 i=1: 1 2 15 5 12 i=2: 12 15 5 2 1 i=3: 15 12 5 2 1 kết quả: 2.4. Sắp xếp nhanh(Quick sort) 2.4.1. ý tưởng + Phân hoạch dãy M thành 03 dãy con có thứ tự tương đối thỏa mãn điều kiện: Dãy con thứ nhất (đầu dãy M) gồm các phần tử có giá trị nhỏ hơn giá trị trung bình của dãy M, Dãy con thứ hai (giữa dãy M) gồm các phần tử có giá trị bằng giá trị trung bình của dãy M, Dãy con thứ ba (cuối dãy M) gồm các phần tử có giá trị lớn hơn giá trị trung bình của dãy M. + Nếu dãy con thứ nhất và dãy con thứ ba có nhiều hơn 01 phần tử thì chúng ta lại tiếp tục phân hoạch đệ quy các dãy con này. + Việc tìm giá trị trung bình của dãy M hoặc tìm kiếm phần tử trong M có giá trị bằng giá trị trung bình của dãy M rất khó khăn và mất thời gian. Trong thực tế, chúng ta chọn một phần tử bất kỳ (thường là phần tử đứng ở vị trí giữa) trong dãy các phần tử cần phân hoạch để làm giá trị cho các phần tử của dãy con thứ hai (dãy giữa) sau khi phân hoạch. Phần tử này còn được gọi là phần tử biên (boundary element). Các phần tử trong dãy con thứ nhất sẽ có giá trị nhỏ hơn giá trị phần tử biên và các phần tử trong dãy con thứ ba sẽ có giá trị lớn hơn giá trị phần tử biên. + Việc phân hoạch một dãy được thực hiện bằng cách tìm các cặp phần tử đứng ở tử đứng ở dãy 1 có giá trị lớn hơn giá trị phần tử giữa và phần tử đứng ở dãy 3 có giá trị nhỏ hơn giá trị phần tử giữa) để đổi chỗ (hoán vị) cho nhau. 2.4.2. Thuật toán Đầu vào: Dãy (M,n) Đầu ra: Dãy (M,n) đã được sắp xếp B1: first=1 B2: last=n B3: IF(first>=last) Thực hiện Bkt B4:X=M[(first+last)/2] B5: i=first B6: IF (M[i]>X) Thực hiện B8 B7: ELSE B7.1: i++ B7.2: Lặp lại B6 B8: j=last B9: IF (M[j]<X) Thực hiện B11 B10:ELSE B10.1: j-- B10.2: Lặp lại B9 B11: IF(i<=j) B11.1: Hoán_Vị(M[i], M[j]) B11.2: i ++ B11.3:j-- B11.4: Lặp lại B6 B12: ELSE B12.1: Phân hoạch đệ quy dãy con từ phần tử thứ First đến phần tử thứ j B12.2: Phân hoạch đệ quy dãy con từ phần tử thứ i đến phần tử thứ Last Bkt: Kết thúc . 2.4.3. Sơ đồ khối Bắt đầu i ++, j -- x= M[(left + right)]/2 i = left, j = right M[i] < x if(left<j) M[j] > x i < j i <= j if(right>i) quicksort(M, i, right) i,j, x, M[],left, right i ++ j -- swap(M[i], M[j]) quicksort(M,left, j) Kết thúc F T F T F T F T F T F 2.4.4. Phân tích độ phức tạp của thuật toán -Về nguyên tắc, có thể chọn giá trị mốc x là một phần tử tùy ý trong dãy, nhưng để đơn giản, phần tử có vị trí giữa thường được chọn, khi đó p=(l+r)/2. -Giá trị mốc x được chọn sẽ có tác động đến hiệu quả thực hiện thực toán vì nó quyết định số lần phân hoạch. +Số lần phân hoạch là ít nhất nếu ta chọn x là phần tử trung vị(median),là nhiều nhất nếu x là cục trị của dãy. +Tuy nhiên do chi phí chọn phần tử median quá cao nên trong thực tế người ta không chọn phần tử này mà chọn phần tử nằm chính giữa dãy hy vọng nó có thể gần với giá trị median. -Hiệu quả phụ thuộc vào việc chon giá trị mốc. + trường hợp tốt nhất: Mỗi lần phân hoạch đều chọn phần tử median làm mốc, khi đó dãy được phân chia thành hai phần bằng nhau và cần (n) lần phân hoạch thì sắp xếp xong. +Nếu mỗi lần phân hoạch chọn giá trị cực đại hay cực tiểu là mốc thì dãy sẽ bị phân chia thành 2 phần không đều: một phần chỉ có 1 phần tử, phần còn lại gồm (n-1)phần tử,do vậy cần n lần mới sắp xếp xong. -Độ phức tạp của thuật toán. TRƯỜNG HỢP ĐỘ PHỨC TẠP Tốt nhất O(nlogn) Trung bình O(nlogn) Xấu nhất O() 2.4.5. Mô phỏng thuật toán Ví dụ: Cho dãy số: 12 2 14 7 5 9 15 Sắp xếp dãy tăng dần. Chọn phần tử trung vị là 7. X=7 9 15 5 7 14 2 12 X=7 15 9 12 7 14 2 5 Lần 1: Lần 2: X=7 15 12 9 14 7 2 5 Phân hoạch thành 2 dãy: X=7 left right 15 12 14 9 7 5 2 Sắp xếp dãy left: 2 5 2 5 5 2 Kết quả Sắp xếp dãy right : 9 14 12 15 X=14 Chọn phần tử trung vị là 14. 15 12 14 9 X=14 14 12 9 15 Lần 1: Kết quả dãy right: 14 12 9 15 Kết quả: 15 14 12 9 7 5 2 CHƯƠNG II:CHƯƠNG TRÌNH MÔ PHỎNG CÁC THUẬT TOÁN SẮP XẾP 1. Giao diện chương trình Ví dụ : Cho dãy số a: 12 35 71 24 9 40 Sử dụng thuật toán sắp xếp nhanh(Quick sort) . 2.Một số module chính #include #include void Swap(int &X, int &Y) { int Temp = X; X = Y; Y = Temp; return; } void PartitionSort(int M[], int First, int Last) { if (First >= Last) return; int X = M[(First+Last)/2]; int i = First; int j = Last; do { while (M[i] < X) i++; while (M[j] > X) j--; if (i <= j) { Swap(M[i], M[j]); i++; j--; } } while (i <= j); PartitionSort(M, First, j); PartitionSort(M, i, Last); return; } void BubbleSort(int M[], int n) { for (inti = 1; i<n; i++) for (int j = n; j > i; j--) if (M[i] > M[j]) Swap(M[i], M[j]); return; } void InsertionSort(int M[], int n) { int pos; int x; for (int i=1; i<n; i++) { x = M[i]; pos = i-1; while((pos >= 0)&&(M[pos] > x)) { M[pos + 1] =M[pos]; pos --; } M[pos + 1] =x; } } void SelectionSort(int M[],int n ) { int min; for (int i=1; i<n ; i++) { min =i; for(int j = i+1; j <=n ; j++) if (M[j ] < M[min]) min = j; Swap(M[min],M[i]); } } void QuickSort(int M[], int n) { PartitionSort(M, 1, n); return; } void create(int M[],int n) { cout<<"\n\n\t\tNhap mang:"; for(int i=1;i<=n;i++) { cout>M[i]; } } void xuat(int M[],int n) { for(int i=1;i<=n;i++) { cout<<M[i]<<" "<<" "; } } void main() { clrscr(); int M[100],n; cout>n; create(M,n); cout<<"\n Mang truoc khi sap xep:"<<" "; xuat(M,n); //BubbleSort(M,n); QuickSort(M,n); //SelectionSort(M,n); //InsertionSort(M,n); cout<<"\n Mang sau khi sap xep:"<<" "; xuat(M,n); getch(); }