Cấu trúc dữ liệu và giải thuật - Chương 4: Các phương pháp sắp xếp cơ bản - Ngô Quang Thạch

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGÔ QUANG THẠCH Email: thachnq@gmail.com ĐT: 01273984123 Chương 4: Các phương pháp sắp xếp cơ bản Định nghĩa bài toán sắp xếp Phương pháp chọn (Selection sort) Phương pháp chèn (Insertion sort) Phương pháp đổi chỗ (Interchange sort) Phương pháp nổi bọt (Bubble sort) Phương pháp sắp xếp nhanh (Quick sort) Định nghĩa bài toán sắp xếp
Phát biểu bài toán: - Cho tập n đối tượng (phần tử). - Hãy sắp xếp n đối tượng trên theo thứ tự tăng (giảm)
Tổ chức dữ liệu - int n Số phần tử cần sắp xếp - int A[n] Lưu trữ tập hợp n phần tử Định nghĩa bài toán sắp xếp
Sắp xếp là một quá trình xử lý bố trí lại một danh sách các đối tượng theo thứ tự nào đó.
Ví dụ: Cần sắp xếp danh sách thí sinh theo tên với thứ tự Alphabet, hoặc sắp xếp danh sách sinh viên theo điểm trung bình với thứ tự từ cao đến thấp.
Các đối tượng cần được sắp xếp thường có nhiều thuộc tính chúng ta cần chọn một thuộc tính làm khóa và sắp xếp theo khóa này. Phương pháp chọn (Selection sort) 1. Ý tưởng  Chọn phần tử nhỏ nhất trong n phần tử đầu, đưa phần tử này về vị trí đầu của dãy.  Tiếp tục quá trình với n-1 phần tử còn lại và bắt đầu từ vị trí thứ 2, lặp lại quá trình trên cho dãy gồm n-1 phần tử còn lại.  Thuật toán thực hiện n-1 lần để lần lượt đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí dẫn đầu Phương pháp chọn (Selection sort)
2. Thuật toán
Đầu vào: n – số phần tử mảng a – mảng chứa các phần tử bất kỳ
Đầu ra: a- mảng đã được sắp xếp tăng dần
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ừ a[i] đến a[n-1]
Bước 3: Hoán vị a[i] với a[min]
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ì n-1 phần tử đã được sắp xếp => Dừng thuật toán Phương pháp chọn (Selection sort)
3. Cài đặt void SelectionSort(int a[ ], int n) { int vtmin, i, j, tg; for(i=0;i<n-1;i++) { vtmin=i; for(j=i+1; j<n; j++) if (a[j]<a[vtmin]) vtmin=j; if(vtmin!=i)//Hoán đổi phần tử a[vtmin] với a[i] { tg=a[vtmin]; a[vtmin]=a[i]; a[i]=tg; } } } Phương pháp chọn (Selection sort)
4. Ví dụ minh họa
Cho dãy số a: a = 12 2 8 5 1 6 4 15 Sắp xếp dãy số tăng dần. Mô tả các bước chạy khi thực hiện thuật toán với dãy trên Phương pháp chọn (Selection sort) i=1 => j = 2 -> 7 và vtmin = 1 => Không hoán đổi 1 i=0 => j = 1 -> 7 và vtmin = 4 => Hoán đổi a[0] và a[4] 0 Phương pháp chọn (Selection sort) i=2 => j = 3 -> 7 và vtmin = 6 => Hoán đổi a[2] & a[6] 2 i=3 => j = 4 -> 7 và vtmin = 3 => Ko hoán đổi 3 Phương pháp chọn (Selection sort) i=4 => j = 5 -> 7 và vtmin = 5 => Hoán đổi a[4] & a[5] 4 i=5 => j = 6 -> 7 và vtmin = 6 => Hoán đổi a[5] & a[6] 5 Phương pháp chọn (Selection sort) Vậy dãy đã sắp xếp là: a = 1 2 4 5 6 8 12 15 This image cannot currently be displayed. i=6 => j = 7 -> 7 và vtmin = 6 => Không hoán đổi 6 => dừng thuật toán Phương pháp chèn (Insertion sort) 1. Ý tưởng  Giả sử có dãy a0, a1,,ai-1 đã được sắp xếp. Ý tưởng của thuật toán là chèn thêm phần tử mới ai vào vị trí thích hợp của đoạn a1ai-1 sao cho được dãy mới a1ai đã được sắp xếp  Nguyên tắc sắp xếp như sau: đoạn gồm phần tử a0 đã được sắp xếp, thêm a1 vào được a0,a1 đã được sắp xếp, tiếp tục thêm a2 vào được a0, a1, a2 đã sắp xếptiếp tục để thêm an vào để được a0,a1,,an đã sắp xếp. Phương pháp chèn (Insertion sort)
2.Thuật toán
Đầu vào: n – số phần tử mảng
a – mảng chứa các phần tử bất kỳ
Đầu ra: a- mảng đã được sắp xếp tăng dần
Bước 1: i=1 //giả sử a[0] đã được sắp xếp
Bước 2: tìm vị trí pos thích hợp trong đoạn từ a[0] đến a[i-1] để chèn a[i] vào
Bước 3: đổi chỗ các phần tử từ a[pos] đến a[i-1] sang phải một vị trí để được vị trí chèn a[i] vào
Bước 4: chèn a[i] vào vị trí pos tìm được bằng cách gán a[pos]=a[i]
Bước 5: i=i+1
Nếu i lặp lại bước 2
Ngược lại => Dừng thuật toán Phương pháp chèn (Insertion sort)
3. Cài đặt void InsertionSort(int a[ ], int n) { int pos,i,x; for(i=1;i<n;i++) { x=a[i]; pos=i-1; while((pos>=0)&&(a[pos]>x)) //tìm vị trí chèn a[i] { a[pos+1]=a[pos]; pos--; } a[pos+1]=x; //chèn x vào dãy } } Phương pháp chèn (Insertion sort)
4. Ví dụ minh họa
Cho dãy số a: a = 12 2 8 5 1 6 4 15 Sắp xếp dãy tăng dần Mô tả các bước chạy khi thực hiện thuật toán với dãy trên Phương pháp chèn (Insertion sort) 1 i=1 => Cần chèn phần tử a[1] vào dãy a[0] => pos=-1 Vi tri so pos=pos+1 2 i=2 => Cần chèn phần tử a[2] vào dãy a[0],a[1] => pos=1 Phương pháp chèn (Insertion sort) 3 i=3 => Cần chèn phần tử a[3] vào dãy a[0],a[1],a[2] => pos = 1 i=4 => Cần chèn phần tử a[4] vào dãy a[0],a[1],a[2],a[3] => pos = 0 4 Phương pháp chèn (Insertion sort) i=5 => Cần chèn phần tử a[5] vào dãy a[0],a[1],a[2],a[3],a[4] => pos = 3 5i=6 => Cần chèn phần tử a[6] vào dãy a[0],a[1],a[2],a[3],a[4],a[5] => vi tri 2 6 Phương pháp chèn (Insertion sort) i=7 => Cần chèn phần tử a[7] vào dãy a[0],a[1],a[2],a[3],a[4],a[5],a[6] => pos = 7 7 => dừng Vậy dãy đã sắp xếp là a = 1 2 4 5 6 8 12 15 Phương pháp đổi chỗ (Interchange sort)
1. Ý tưởng
Xuất phát từ phần tử đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế. (Nghịch thế là số lớn đứng trước số nhỏ)
Lặp lại xử lý trên với các phần tử tiếp theo trong dãy. Phương pháp đổi chỗ (Interchange sort)
2. Thuật toán
Đầu vào: n – số phần tử mảng a – mảng chứa các phần tử bất kỳ
Đầu ra: a- mảng đã được sắp xếp tăng dần
Bước 1: i = 1; // bắt đầu từ đầu dãy
Bước 2: j = i+1;//tìm các phần tử a[j] i  Nếu a[j]<a[i]: đổi chổ a[i], a[j]; //xét cặp a[i], a[j]  j = j+1;
Bước 3 : i = i+1;  Nếu i < n Lặp lại bước 2  Ngược lại: Dừng. Phương pháp đổi chỗ (Interchange sort)
3. Cài đặt void InterchangeSort(int a[], int N ) { int i, j; for (i = 0 ; i<N-1 ; i++) for (j =i+1; j < N ; j++) if(a[j ]< a[i]) // nếu có sự sai vị trí thì đổi chỗ Hoanvi(a[i],a[j]); } Phương pháp đổi chỗ (Interchange sort)
4. Ví dụ minh họa
Cho dãy số a: a = 12 2 8 5 1 6 4 15 Sắp xếp dãy tăng dần Mô tả các bước chạy khi thực hiện thuật toán với dãy trên Phương pháp đổi chỗ (Interchange sort) i=0 => So sánh phần từ a[0] với các phần tử a[j] (j=>1..7) j=2,3 => Các cặp bình thường, j=4 cần điều chỉnh i=0 j=1 i=0 j=4 Phương pháp đổi chỗ (Interchange sort) i=1 => So sánh phần từ a[1] với các phần tử a[j] (j=>2..7) i=1 j=2 i=1 j=3 Phương pháp đổi chỗ (Interchange sort) i=1 => So sánh phần từ a[1] với các phần tử a[j] (j=>2..7) j=4i=1 Phương pháp đổi chỗ (Interchange sort) i=2 => So sánh phần từ a[2] với các phần tử a[j] (j=>3..7) j=3 i=2 j=4 i=2 Phương pháp đổi chỗ (Interchange sort) j=6i=2 Phương pháp đổi chỗ (Interchange sort) j=4i=3 i=3 => So sánh phần từ a[3] với các phần tử a[j] (j=>4..7) j=5i=3 Phương pháp đổi chỗ (Interchange sort) j=6i=3 Phương pháp đổi chỗ (Interchange sort) j=5i=4 i=4 => So sánh phần từ a[4] với các phần tử a[j] (j=>5..7) j=6i=4 Phương pháp đổi chỗ (Interchange sort) j=6i=5 i=5 => So sánh phần từ a[5] với các phần tử a[j] (j=>6..7) Phương pháp đổi chỗ (Interchange sort) i=6 i=6 => So sánh phần từ a[6] với các phần tử a[j] (j=>7..7) Phương pháp nổi bọt (Bubble sort)
1. Ý tưởng Xuất phát từ đầu dãy hay cuối dãy và tiến hành đổi chỗ cặp phần tử kế cận nhau để đưa phần tử nhỏ hơn hoặc lớn hơn về vị trí cao nhất hay thấp nhất trong dãy. Sau khi đã chuyển vị trí này không xét nữa => Lặp lại quá trình này khi dãy ko còn phần tử nào nữa Phương pháp nổi bọt (Bubble sort)
2. Thuật toán
Bước 1: i = 0
Bước 2: j = n-1 //duyệt từ cuối đến ptử thứ i Trong khi j>i thực hiện nếu a[j] < a[j-1] thì hoán đổi hai phần tử j=j-1
Bước 3: i=i+1 Nếu i>=n-1 => Hết dãy và dừng thuật toán Ngược lại lặp lại bước 2 Phương pháp nổi bọt (Bubble sort)
3. Cài đặt void BubbleSort(int a[ ], int n) { int i,j,tg; for(i=0;i<n-1;i++) for(j=n-1;j>i;j--) if ( a[ j ] < a[ j-1] ) { tg = a[ j ]; a[ j ] = a[ j-1]; a[ j-1 ] = tg; } } Phương pháp nổi bọt (Bubble sort)
4. Ví dụ minh họa Cho dãy số a: a = 2 12 8 5 1 6 4 15 Sắp xếp dãy tăng dần Phương pháp nổi bọt (Bubble sort) i=0 j=6 i=0 j=4 i=0 i=0 i=0 j=3 j=2 j=1 2 12 Phương pháp nổi bọt (Bubble sort) i=1 i=1 i=1 j=5 j=4 j=3 Phương pháp nổi bọt (Bubble sort) i=2 i=2 j=5 j=4 Phương pháp nổi bọt (Bubble sort) i=3 i=3 j=6 j=5 Phương pháp nổi bọt (Bubble sort) i=4 i=5 j=6 Phương pháp sắp xếp nhanh (Quick sort) 1. Ý tưởng 2. Giải thuật 3. Cài đặt 4. Ví dụ 5. Nhận xét 1. Ý tưởng
Phân hoạch dãy a1 a2 an thành 3 thành phần : - Dãy con 1 : Gồm các phần tử a1 ai có giá trị không lớn hơn x.(<x) - Dãy con 2 : Gồm các phần tử aj an có giá trị không nhỏ hơn x.(>x) - Dãy con thứ 3: ai,..aj=x
Với x là giá trị của một phần tử tuỳ ý trong dãy ban đầu.
Sau khi phân hoạch, dãy ban đầu được chia làm 3 phần :  ak < x, vớI k=1..i  ak = x, vớI k=i..j  ak > x, vớI k=j..N 2. Giải thuật
Giải thuật để sắp xếp một dãy alar
Bước 1 : Phân hoạch dãy alar thành các dãy con :  Dãy con 1 : alaj < x  Dãy con 2 : aj+1ai-1 = x  Dãy con 3 : aiar > x
Bước 2 :  Nếu (l<j) Phân hoạch dãy alaj  Nếu (i<r) Phân hoạch dãy aiar 2. Giải thuật
Giải thuật để phân hoạch một dãy alar thành 2 dãy con: Bước 1 : Chọn tuỳ ý a[k] làm giá trị mốc l<=k<=r X = a[k]; i=l, j=r Bước 2 : Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ: Bước 2a : Trong khi a[i] <x i++; Bước 2b : Trong khi a[j]>x j--; Bước 2c : Nếu i<j Hoán vị (a[i],a[j]) Bước 3 : Nếu i<j : Lặp lại bước 2. Nếu i>=j : dừng. 3. Cài đặt void QuickSort (int a[], int l, int r) { int i,j,x; x=a[(l+r)/2]; i=l; j=r; do { while (a[i]<x) i++; while (a[j]>x) j--; if (i<=j) { HoanVi(a[i],a[j]); i++; j--; } } while (i<j); if (l<j) QuickSort(a,l,j); if (i<r) QuickSort(a,i,r); } 8x 357394 Cho dãy số a: 4 9 3 7 5 3 8 l r i ji j ij Đoạn l = 0, r =3, x = a[1] = 3 534 3 Đoạn l = 4, r =6, x = a[5] = 9 87 9 Kết quả 9875433 4. Ví dụ