Bài giảng 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=0 => j = 1 -> 7 và vtmin = 4 => Hoán đổ i a[0] và a[4] 0 i=1 => j = 2 -> 7 và vtmin = 1 => Không hoán đổ i 1 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) i=6 => j = 7 -> 7 và vtmin = 6 => Không hoán đổ i This image cannot currently be displayed. 6 => d ừng thu ật toán Vậy dãy đã sắp xếp là: a = 1 2 4 5 6 8 12 15 Phương pháp chèn (Insertion sort) 1. Ý tưởng ° Gi ả sử có dãy a0, a 1,,a i-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 a1a i-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,a 1 đã đượ c sắp xếp, ti ếp tục thêm a2 vào đượ c a0, a 1, a 2 đã sắp xếpti ếp tục để thêm an vào để đượ c a0,a 1,,a n đã 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) 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 1 i=2 => Cần chèn ph ần t ử a[2] vào dãy a[0],a[1] => pos=1 2 Phương pháp chèn (Insertion sort) i=3 => Cần chèn ph ần t ử a[3] vào dãy a[0],a[1],a[2] => pos = 1 3 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 i=6 => Cần chèn ph ần t ử a[6] vào dãy 5 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) i=0 j=1 j=2,3 => Các c ặp bình th ườ ng, j=4 c ần điều ch ỉnh 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) i=1 j=4 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) i=2 j=3 i=2 j=4 Phương pháp đổi chỗ (Interchange sort) i=2 j=6 Phương pháp đổi chỗ (Interchange sort) i=3 => So sánh ph ần t ừ a[3] v ới các ph ần t ử a[j] (j=>4..7) i=3 j=4 i=3 j=5 Phương pháp đổi chỗ (Interchange sort) i=3 j=6 Phương pháp đổi chỗ (Interchange sort) i=4 => So sánh ph ần t ừ a[4] v ới các ph ần t ử a[j] (j=>5..7) i=4 j=5 i=4 j=6 Phương pháp đổi chỗ (Interchange sort) i=5 => So sánh ph ần t ừ a[5] v ới các ph ần t ử a[j] (j=>6..7) i=5 j=6 Phương pháp đổi chỗ (Interchange sort) i=6 => So sánh ph ần t ừ a[6] v ới các ph ần t ử a[j] (j=>7..7) i=6 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) 2 12 i=0 j=6 i=0 j=4 i=0 j=3 i=0 j=2 i=0 j=1 Phương pháp nổi bọt (Bubble sort) i=1 j=5 i=1 j=4 i=1 j=3 Phương pháp nổi bọt (Bubble sort) i=2 j=5 i=2 j=4 Phương pháp nổi bọt (Bubble sort) i=3 j=6 i=3 j=5 Phương pháp nổi bọt (Bubble sort) i=4 j=6 i=5 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 a 1 a2 a n 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ử a j a n có giá trị không nhỏ hơn x.(>x) - Dãy con thứ 3: a i,..a j= 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); } 4. Ví dụ Cho dãy số a: 4 9 3 7 5 3 8 j i i j ji 4 9 3 7 5 3 8 l x r Đoạn l = 0, r =3, x = a[1] = 3 4 3 3 5 Đoạn l = 4, r =6, x = a[5] = 9 7 9 8 Kết quả 3 3 4 5 7 8 9