CÁC GIẢI THUẬT SẮP XẾP

G V : L Ê T H Ị N G Ọ C H Ạ N H

1

9/4/2015 Data structure & Algorithms

GIỚI THIỆU BÀI TOÁN SẮP XẾP

 Bài toán sắp xếp: Là quá trình xử lý một danh sách

các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử.

 Lưu ý: Thứ tự đề cập ở đây là một thứ tự tổng quát.  Ví dụ:

Danh sách trước khi sắp xếp: {1, 25, 6, 5, 2, 37, 40} Danh sách sau khi sắp xếp: {1, 2, 5, 6, 25, 37, 40}

9/4/2015 Data structure & Algorithms 2

GIỚI THIỆU BÀI TOÁN SẮP XẾP

 Khái niệm “Nghịch thế” Xét một mảng các số a0, a1, …, an Nếu có iaj thì ta gọi đó là một nghịch thế. Mảng chưa sắp xếp sẽ có nghịch thế Mảng đã có thứ tự sẽ không chứa nghịch thế

9/4/2015 Data structure & Algorithms 3

CÁC PHƯƠNG PHÁP SẮP XẾP

 Quick sort  Merge sort  Radix sort Shaker sort  Radix sort  …

 Selection sort  Insertion sort  Interchange sort  Bubble sort  Shaker sort  Binary Insertion sort  …

9/4/2015 Data structure & Algorithms 4

ĐỔI CHỖ TRỰC TIẾP – INTERCHANGE SORT

 Ý tưởng: Xuất phát 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 tử này với phần tử tương ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử tiếp theo trong dãy.

9/4/2015 Data structure & Algorithms 5

INTERCHANGE SORT – THUẬT TOÁN

Nếu a[j]

j=j+1;

Nếu i

Bước 1: Khởi tạo i=0 // bắt đầu từ đầu dãy Bước 2: j = i+1; //tìm các cặp a[j]I Bước 3: Trong khi j

9/4/2015 Data structure & Algorithms 6

INTERCHANGE SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 7

INTERCHANGE SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 8

INTERCHANGE SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 9

INTERCHANGE SORT – CÀI ĐẶT

int i, j; for(i = 0 ; i

for(j = i+1;j

if(a[j]< a[i])//nếu có

Swap(a[i],a[j]);

Void InterchangeSort(int a[], int n) { nghịch thế thì đổi chỗ }

9/4/2015 Data structure & Algorithms 10

INTERCHANGE SORT – ĐÁNH GIÁ

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. Số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh

9/4/2015 Data structure & Algorithms 11

SẮP XẾP CHỌN – SELECTION SORT

9/4/2015 Data structure & Algorithms 12

SELECTION SORT – Ý TƯỞNG

 Chọn phần tử nhỏ nhất đặt vào vị trí đầu tiên  Chọn phần tử nhỏ nhất trong số n-1 phần tử

còn lại đặt vào vị trí thứ 2.

 Lặp lại quá trình cho đến khi mảng chỉ còn 1

phần tử.

9/4/2015 Data structure & Algorithms 13

SELECTION SORT – THUẬT TOÁN

 Bước 1: Khởi tạo i = 0.  Bước 2: Khởi đầu min = i, j = i+1  Bước 3: Nếu a[j]

sang bước 4

 Bước 4: Tăng j thêm 1 đơn vị.  Bước 5: Nếu j

bước 6

 Bước 6: Đổi chỗ a[min] và a[i], tăng i lên 1 đơn vị  Bước 7: Nếu i

kết thúc.

9/4/2015 Data structure & Algorithms 14

SELECTION SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 15

SELECTION SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 16

SELECTION SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 17

SELECTION SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 18

SELECTION SORT – CÀI ĐẶT

min = j; // ghi nhận vị trí phần tử nhỏ nhất

min = i; for(int j = i+1; j < n ; j++) if (a[j] < a[min]) if(min != i)

hoanvi(a[min],a[i]);

int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành for(int i=0; i

void SelectionSort(int a[],int n) { }

9/4/2015 Data structure & Algorithms 19

SELECTION SORT – ĐÁNH GIÁ

Số phép so sánh:  Tại lượt i bao giờ cũng cần (n-i-1) số lần so sánh  Không phụ thuộc vào tình trạng dãy số ban đầu  Số phép so sánh:

9/4/2015 Data structure & Algorithms 20

SELECTION SORT – ĐÁNH GIÁ

Số phép gán:  Tốt nhất:  Xấu nhất:

9/4/2015 Data structure & Algorithms 21

CHÈN TRỰC TIẾP – INSERTION SORT

9/4/2015 Data structure & Algorithms 22

CHÈN TRỰC TIẾP – Ý TƯỞNG

- Tại bước thứ i thì các phần tử từ a[0] đến a[i-1]đều có thứ tự tăng dần. - Đầu tiên ta bắt đầu với i=1(a[0] không cần sắp) - Tìm vị trí thích hợp để chèn a[1] vào đoạn a[0]…a[1] Kế tiếp, tìm vị trí thích hợp để chèn a[2] vào đoạn a[0]…a[2] Làm tiếp tục cho đến khi sắp được phần tử cuối cùng.

9/4/2015 Data structure & Algorithms 23

INSERTION SORT – THUẬT TOÁN

Bước 1: khởi tạo i=1 Bước 2: pos= i-1, x=a[i] Bước 3: Nếu x=0 thì quay lại bước 3, nếu không sang bước 6. Bước 6: Gán a[pos+1]=x, tăng i thêm 1 đơn vị Bước 7: Nếu i

9/4/2015 Data structure & Algorithms 24

INSERTION SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 25

INSERTION SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 26

INSERTION SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 27

INSERTION SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 28

INSERTION SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 29

INSERTION SORT – CÀI ĐẶT

int pos; int x; //lưu trữa[i] tránh bị ghi đè khi dời

x = a[i]; for(pos=i;(pos>0)&&(a[pos-1]>x);pos--) a[pos] = a[pos-1]; a[pos] = x; // chèn x vào dãy

for(int i=1;i

void InsertionSort(int a[],int n) { chỗ các phần tử. } 9/4/2015

Data structure & Algorithms 30

INSERTION SORT – ĐÁNH GIÁ

 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  dời chỗ phần tử a[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 trong trường hợp sau:

9/4/2015 Data structure & Algorithms 31

SẮP XẾP NỔI BỌT – BUBBLE SORT

9/4/2015 Data structure & Algorithms 32

BUBBLE SORT – Ý TƯỞNG

- Đưa dần các phần tử có khóa (giá trị) nhỏ về phía trước. - Xuất phát từ cuối (đầ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ử đó 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ó ở bước tiếp theo. - Ở lần xử lý thứ i 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.

9/4/2015 Data structure & Algorithms 33

BUBBLE SORT – THUẬT TOÁN

 Bước 1: khởi tạo i=0  Bước 2: j=n-1; //duyệt từ cuối dãy ngược về vị

trí i

Nếu a[j]

 Bước 3: trong khi j>i thực hiện  Bước 4: i=i+1; //lần xử lý kế tiếp

Nếu i=n-1: dừng. //hết dãy Ngược lại: Lặp lại bước 2.

9/4/2015 Data structure & Algorithms 34

BUBBLE SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 35

BUBBLE SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 36

BUBBLE SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 37

BUBBLE SORT – VÍ DỤ

9/4/2015 Data structure & Algorithms 38

BUBBLE SORT – CÀI ĐẶT

int i, j; for (i = 0 ; i

for (j = n-1; j>i ; j --) if(a[j]< a[j-1])

swap(a[j], a[j-1]);

void BubbleSort(int a[], int n) { }

9/4/2015 Data structure & Algorithms 39

BUBBLE SORT – ĐÁNH GIÁ

 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.  Số lượng phép hoán vị thực hiện tùy thuộc

vào kết quả so sánh.

9/4/2015 Data structure & Algorithms 40