Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 5: Sắp xếp

Chương 5

Sắp xếp (Sorting)

Heap Sort

Quick Sort

William A. Martin, Sorting. ACM Computing Surveys, Vol. 3, Nr 4, Dec 1971, pp. 147-174.

" ...The bibliography appearing at the end of this article lists 37 sorting algorithms

and 100 books and papers on sorting published in the last 20 years...

Suggestions are made for choosing the algorithm best suited to a given situation."

D. Knuth: 40% thời gian hoạt động của các máy tính là dành cho sắp xếp!

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

NỘI DUNG

5.1. Bài toán sắp xếp

5.2. Ba thuật toán sắp xếp cơ bản

5.3. Sắp xếp trộn (Merge Sort)

5.4. Sắp xếp nhanh (Quick Sort)

5.5. Sắp xếp vun đống (Heap Sort)

5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp

5.7. Các phương pháp sắp xếp đặc biệt

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

2

5.1. Bài toán sắp xếp

• 5.1.1. Bài toán sắp xếp

• 5.1.2. Giới thiệu sơ lược về các thuật toán sắp xếp

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

3

5.1.1. Bài toán sắp xếp

• Sắp xếp (Sorting)

– Là quá trình tổ chức lại họ các dữ liệu theo thứ tự giảm dần

hoặc tăng dần (ascending or descending order)

• Dữ liệu cần sắp xếp có thể là

– Số nguyên (Integers)

– Xâu ký tự (Character strings)

– Đối tượng (Objects)

• Khoá sắp xếp (Sort key)

– Là bộ phận của bản ghi xác định thứ tự sắp xếp của bản ghi

trong họ các bản ghi.

– Ta cần sắp xếp các bản ghi theo thứ tự của các khoá.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

4

5.1.1. Bài toán sắp xếp

• Chú ý:

• Việc sắp xếp tiến hành trực tiếp trên bản ghi đòi hỏi di chuyển

vị trí bản ghi, có thể là thao tác rất tốn kém.

• Vì vậy, người ta thường xây dựng bảng khoá gồm các bản ghi

chỉ có hai trường là (khoá, con trỏ)

– trường "khoá" chứa giá trị khoá,

– trường "con trỏ" để ghi địa chỉ của bản ghi tương ứng.

• Việc sắp xếp theo khoá trên bảng khoá không làm thay đổi

bảng chính, nhưng trình tự các bản ghi trong bảng khoá cho

phép xác định trình tự các bản ghi trong bảng chính.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

5

5.1.1. Bài toán sắp xếp

Ta có thể hạn chế xét bài toán sắp xếp dưới dạng sau đây:

Input: Dãy n số A = (a₁, a₂, …, a_n)

Output: Một hoán vị (sắp xếp lại) (a'₁,…, a’_n) của dãy số đã cho

thoả mãn

a’₁≤ … ≤ a’_n

• Ứng dụng của sắp xếp:

– Quản trị cơ sở dữ liệu (Database management);

– Khoa học và kỹ thuật (Science and engineering);

– Các thuật toán lập lịch (Scheduling algorithms),

• ví dụ thiết kế chương trình dịch, truyền thông,... (compiler design,

telecommunication);

– Máy tìm kiếm web (Web search engine);

– và nhiều ứng dụng khác…

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

6

5.1.1. Bài toán sắp xếp

• Các loại thuật toán sắp xếp

– Sắp xếp trong (internal sort)

• Đòi hỏi họ dữ liệu được đưa toàn bộ vào bộ nhớ trong của máy tính

– Sắp xếp ngoài (external sort)

• Họ dữ liệu không thể cùng lúc đưa toàn bộ vào bộ nhớ trong,

nhưng có thể đọc vào từng bộ phận từ bộ nhớ ngoài

• Các đặc trưng của một thuật toán sắp xếp:

– Tại chỗ (in place): nếu không gian nhớ phụ mà thuật toán đòi hỏi là

O(1), nghĩa là bị chặn bởi hằng số không phụ thuộc vào độ dài của dãy

cần sắp xếp.

– Ổn định (stable): Nếu các phần tử có cùng giá trị vẫn giữ nguyên thứ tự

tương đối của chúng như trước khi sắp xếp.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

7

5.1.1. Bài toán sắp xếp

• Có hai phép toán cơ bản mà thuật toán sắp xếp thường phải sử dụng:

– Đổi chỗ (Swap): Thời gian thực hiện là O(1)

void swap( datatype &a, datatype &b){

datatype temp = a; //datatype-kiểu dữ liệu của phần tử

a = b;

b = temp;

}

– So sánh: Compare(a, b) trả lại true nếu a đi trước b trong thứ tự cần

sắp xếp và false nếu trái lại.

• Các thuật toán chỉ sử dụng phép toán so sánh để xác định thứ tự giữa

hai phần tử được gọi là thuật toán sử dụng phép so sánh

(Comparison-based sorting algorithm)

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

8

5.1.2. Giới thiệu sơ lược về các thuật toán sắp xếp

Simple

algorithms:

O(n²)

Fancier

algorithms:

O(n log n)

Comparison

lower bound:

(n log n)

Specialized

algorithms:

O(n)

Handling

huge data

sets

Insertion sort

Selection sort

Bubble sort

Shell sort

Heap sort

Bucket sort

Radix sort

External

sorting

Merge sort

Quick sort

…

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

9

Các thuật toán sắp xếp dựa trên phép so sánh

Name

Bubble sort

Average

—

Worst

O(n²)

Memory

O(1)

O(n)

Stable

Yes

No

Method

Exchanging

Selection

Cocktail sort

Comb sort

—

O(n²)

O(n log n)

—

O(n log n)

O(n²)

Gnome sort

Selection sort

Insertion sort

Shell sort

Yes

No

O(n²)

O(n + d)

—

O(n²)

Yes

No

Insertion

O(n log² n)

O(n log n)

O(n²)

Insertion

Binary tree sort

Library sort

Merge sort

O(n log n)

Yes

Insertion

O(n log n)

Merging

In-place merge sort

O(n log n)

O(1)

Yes

Merging

Heapsort

O(n log n)

—

O(n log n)

O(n²)

O(1)

No

Selection

Partitioning

Hybrid

Smoothsort

Quicksort

O(n log n)

—

O(log n)

O(n)

Introsort

O(n log n)

O(n²)

Patience sorting

Insertion

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

10

Các thuật toán sắp xếp không dựa trên phép so sánh

Name

Average

O(n+2^k)

O(n·k)

Worst

O(n+2^k)

O(n²·k)

O(n+2^k)

O(n·k/s)

Memory Stable n << 2^k?

Pigeonhole sort

Bucket sort

O(2^k)

O(n·k)

O(n+2^k)

O(n)

Yes

No

Yes

No

Counting sort

LSD Radix sort

O(n+2^k)

O(n·k/s)

MSD Radix sort

Spreadsort

O(n·k/s)

O(n·(k/s)·2^s) O((k/s)·2^s)

No

O(n·(k-log(n))^0.5)

O(n·k/log(n))

O(n)

Các thông số trong bảng

n - số phần tử cần sắp xếp

k - kích thước mỗi phần tử

s - kích thước bộ phận được sử dụng khi cài đặt.

Nhiều thuật toán được xây dựng dựa trên giả thiết là n << 2^k.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

11

NỘI DUNG

5.1. Bài toán sắp xếp

5.2. Ba thuật toán sắp xếp cơ bản

5.3. Sắp xếp trộn (Merge Sort)

5.4. Sắp xếp nhanh (Quick Sort)

5.5. Sắp xếp vun đống (Heap Sort)

5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp

5.7. Các phương pháp sắp xếp đặc biệt

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

12

5.2. Ba thuật toán sắp xếp cơ bản

• 5.2.1. Sắp xếp chèn (Insertion Sort)

• 5.2.2. Sắp xếp lựa chọn (Selection Sort)

• 5.2.3. Sắp xếp nổi bọt (Bubble Sort)

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

13

5.2.1. Sắp xếp chèn (Insertion Sort)

Phỏng theo cách làm của người

chơi bài khi cần "chèn" thêm một

con bài vào bộ bài đã được sắp

xếp trên tay.

Để chèn 12, ta cần tạo chỗ cho

nó bởi việc dịch chuyển đầu tiên

là 36 và sau đó là 24.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

14

Sắp xếp chèn (Insertion Sort)

Phỏng theo cách làm của người

chơi bài khi cần "chèn" thêm một

con bài vào bộ bài đã được sắp

xếp trên tay.

Để chèn 12, ta cần tạo chỗ cho

nó bởi việc dịch chuyển đầu tiên

là 36 và sau đó là 24.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

15

Sắp xếp chèn (Insertion Sort)

Phỏng theo cách làm của người

chơi bài khi cần "chèn" thêm một

con bài vào bộ bài đã được sắp

xếp trên tay.

Để chèn 12, ta cần tạo chỗ cho

nó bởi việc dịch chuyển đầu tiên

là 36 và sau đó là 24.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

16

Sắp xếp chèn (Insertion Sort)

Phỏng theo cách làm của người

chơi bài khi cần "chèn" thêm một

con bài vào bộ bài đã được sắp

xếp trên tay.

Để chèn 12, ta cần tạo chỗ cho

nó bởi việc dịch chuyển đầu tiên

là 36 và sau đó là 24.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

17

Don’t start coding

You must design a working algorithm first.

18

5.2.1. Sắp xếp chèn (Insertion Sort)

• Thuật toán:

– Tại bước k = 1, 2, ..., n, đưa phần tử thứ k trong mảng đã cho vào đúng

vị trí trong dãy gồm k phần tử đầu tiên.

– Kết quả là sau bước k, k phần tử đầu tiên là được sắp thứ tự.

void insertionSort(int a[], int array_size) {

int i, j, last;

Giải thích:

for (i=1; i < array_size; i++) {

• Ở đầu lần lặp i của vòng

last = a[i];

"for" ngoài, dữ liệu từ a[0]

đến a[i-1] là được sắp xếp.

• Vòng lặp "while" tìm vị trí

cho phần tử tiếp theo (last

j = i;

while ((j > 0) && (a[j-1] > last)) {

a[j] = a[j-1];

j = j - 1; }

a[j] = last;

} // end for

=a[i]) trong dãy gồm i phần

tử đầu tiên.

} // end of isort

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

19

Ví dụ Insertion sort (1)

1

2

3

8

7

8

9

10 12 23 18 15 16 17 14

10 12 18 23 15 16 17 14

10 12 18 15 23 16 17 14

1

2

3

7

8

9

10 12 15 18 23 16 17 14

10 12 15 18 16 23 17 14

10 12 15 16 18 23 17 14

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

20

Ví dụ Insertion sort (1)

1

2

3

7

8

9

10 12 15 16 18 17 23 14

10 12 15 16 17 18 23 14

10 12 15 16 17 18 14 23

10 12 15 16 17 14 18 23

1

2

3

7

8

9

10 12 15 16 14 17 18 23

10 12 15 14 16 17 18 23

10 12 14 15 16 17 18 23

13 phép đổi chỗ:

20 phé p so sá nh:

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

21

Ví dụ: Insertion Sort (2)

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

22

Các đặc tính của Insertion Sort

• Sắp xếp chèn là tại chỗ và ổn định (In place and Stable)

• Phân tích thời gian tính của thuật toán

– Best Case: 0 hoán đổi, n-1 so sánh (khi dãy đầu vào là đã được sắp)

– Worst Case: n²/2 hoán đổi và so sánh (khi dãy đầu vào có thứ tự

ngược lại với thứ tự cần sắp xếp)

– Average Case: n²/4 hoán đổi và so sánh

• Thuật toán này có thời gian tính trong tình huống tốt nhất là

tốt nhất

• Là thuật toán sắp xếp tốt đối với dãy đã gần được sắp xếp

– Nghĩa là mỗi phần tử đã đứng ở vị trí rất gần vị trí trong thứ tự cần

sắp xếp

23

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

Thử nghiệm insertion sort

#include <stdlib.h>

#include <stdio.h>

void insertionSort(int a[], int array_size);

int a[1000];

int main() {

int i, N;

printf("\nGive n = "); scanf("%i", &N);

//seed random number generator

srand(getpid());

//fill array with random integers

for (i = 0; i < N; i++)

a[i] = rand();

//perform insertion sort on array

insertionSort(a, N);

printf("\nOrdered sequence:\n");

for (i = 0; i < N; i++)

printf("%8i", a[i]);

getch();

}

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

24

5.2.2. Sắp xếp chọn (Selection Sort)

• Thuật toán

void swap(int &a,int &b)

{

– Tìm phần tử nhỏ nhất đưa vào vị trí 1

– Tìm phần tử nhỏ tiếp theo đưa vào vị trí 2

– Tìm phần tử nhỏ tiếp theo đưa vào vị trí 3

int temp = a;

a = b;

b = temp;

}

– …

void selectionSort(int a[], int n){

int i, j, min, temp;

for (i = 0; i < n-1; i++) {

min = i;

for (j = i+1; j < n; j++){

if (a[j] < a[min]) min = j;

}

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

}

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

25

Selection Sort

template <class Elem, class Comp>

void selection_sort(Elem A[], int n) {

for (int i=0; i<n-1; i++) {

int lowindex = i; // Remember its index

for (int j=n-1; j>i; j--) // Find least

if (Comp::lt(A[j], A[lowindex]))

lowindex = j; // Put it in place

swap(A, i, lowindex);

}

• Best case: 0 đổi chỗ (n-1 như trong đoạn mã), n²/2 so sánh.

• Worst case: n - 1 đổi chỗ và n²/2 so sánh.

• Average case: O(n) đổi chỗ và n²/2 so sánh.

• Ưu điểm nổi bật của sắp xếp chọn là số phép đổi chỗ là ít. Điều này là có ý

nghĩa nếu như việc đổi chỗ là tốn kém.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

26

Ví dụ: Selection Sort

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

27

5.2.3. Sắp xếp nổi bọt - Bubble Sort

• Bubble sort là phương pháp sắp xếp đơn giản thường được sử dụng

như ví dụ minh hoạ cho các giáo trình nhập môn lập trình.

• Bắt đầu từ đầu dãy, thuật toán tiến hành so sánh mỗi phần tử với

phần tử đi sau nó và thực hiện đổi chỗ, nếu chúng không theo đúng

thứ tự. Quá trình này sẽ được lặp lại cho đến khi gặp lần duyệt từ

đầu dãy đến cuối dãy mà không phải thực hiện đổi chỗ (tức là tất cả

các phần tử đã đứng đúng vị trí). Cách làm này đã đẩy phần tử lớn

nhất xuống cuối dãy, trong khi đó những phần tử có giá trị nhỏ hơn

được dịch chuyển về đầu dãy.

• Mặc dù thuật toán này là đơn giản, nhưng nó là thuật toán kém hiệu

quả nhất trong ba thuật toán cơ bản trình bày trong mục này. Vì thế

ngoài mục đích giảng dạy, Sắp xếp nổi bọt rất ít khi được sử dụng.

• Giáo sư Owen Astrachan (Computer Science Department, Duke

University) còn đề nghị là không nên giảng dạy về thuật toán này.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

28

5.2.3. Sắp xếp nổi bọt - Bubble Sort

void swap(int &a,int &b)

{

void bubbleSort(int a[], int n){

int temp = a;

a = b;

b = temp;

int i, j;

for (i = (n-1); i >= 0; i--) {

}

for (j = 1; j <= i; j++){

if (a[j-1] > a[j])

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

}

• Best case: 0 đổi chỗ, n²/2 so sánh.

• Worst case: n²/2 đổi chỗ và so sánh.

• Average case: n²/4 đổi chỗ và n²/2 so sánh.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

29

Ví dụ: Bubble Sort

7

4

7

1

7

9

2

4

1

4

7

2

7

9

1

4

2

4

7

9

4

1

7

2

9

i = 3

i = 2

i = 4

Chú ý:

– Các phần tử được đánh chỉ số bắt đầu từ 0.

– n=5

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

30

So sánh ba thuật toán cơ bản

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

31

Tổng kết 3 thuật toán sắp xếp cơ bản

Insertion Bubble Selection

Comparisons:

Best Case

Average Case

Worst Case

(n)

(n²)

Swaps

Best Case

Average Case

Worst Case

0

(n)

(n²)

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

32

NỘI DUNG

5.1. Bài toán sắp xếp

5.2. Ba thuật toán sắp xếp cơ bản

5.3. Sắp xếp trộn (Merge Sort)

5.4. Sắp xếp nhanh (Quick Sort)

5.5. Sắp xếp vun đống (Heap Sort)

5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp

5.7. Các phương pháp sắp xếp đặc biệt

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

33

Sắp xếp trộn (Merge Sort)

Hoà nhập hai dòng xe theo Khoá

[độ liều lĩnh của lái xe].

Lái xe liều lĩnh hơn sẽ vào trước!

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

34

Sắp xếp trộn (Merge Sort)

• Bài toá n: Cần sắp xếp mảng A[1 .. n]:

• Chia (Divide)

– Chia dãy gồm n phần tử cần sắp xếp ra thành 2 dãy, mỗi dãy có n/2

phần tử

• Trị (Conquer)

– Sắp xếp mỗi dãy con một cách đệ qui sử dụng sắp xếp trộn

– Khi dãy chỉ còn một phần tử thì trả lại phần tử này

• Tổ hợp (Combine)

– Trộn (Merge) hai dãy con được sắp xếp để thu được dãy được sắp xếp

gồm tất cả các phần tử của cả hai dãy con

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

35

Merge Sort

r

p

q

1

2

3

4

5

6

7

8

MERGE-SORT(A, p, r)

5

2 4 7 1 3 2 6

if p < r

Kiểm tra điều kiện neo

then q ← (p + r)/2

MERGE-SORT(A, p, q)

MERGE-SORT(A, q + 1, r)

MERGE(A, p, q, r)

endif

Chia (Divide)

Trị (Conquer)

Tổ hợp (Combine)

• Lệnh gọi thực hiện thuật toán: MERGE-SORT(A, 1, n)

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

36

Trộn (Merge) - Pseudocode

MERGE(A, p, q, r)

r

p

q

1. Tính n₁và n₂

1

2

3

4

5

6

7

8

2. Sao n₁phần tử đầu tiên vào L[1 . . n₁] và n₂

2

4 5 7 1 2 3 6

phần tử tiếp theo vào R[1 . . n₂]

3. L[n₁+ 1] ← ; R[n₂+ 1] ← 

4. i ← 1; j ← 1

n₂

n₁

5. for k ← p to r do

p

q

6.

if L[ i ] ≤ R[ j ]

then A[k] ← L[ i ]

i ←i + 1

else A[k] ← R[ j ]

j ← j + 1

2 4 5 7



L

7.

q + 1

r

8.

1 2 3 6 

R

9.

10.

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

37

Thời gian tính của trộn

• Khởi tạo (tạo hai mảng con tạm thời L và R):

– (n₁+ n₂) = (n)

• Đưa các phần tử vào mảng kết quả (vòng lặp for cuối cùng):

– n lần lặp, mỗi lần đòi hởi thời gian hằng số  (n)

• Tổng cộng thời gian của trộn là:

– (n)

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

38

Thời gian tính của sắp xếp trộn

MERGE-SORT Running Time

• Chia:

– tính q như là giá trị trung bình của p và r: D(n) = (1)

• Trị:

– giải đệ qui 2 bài toán con, mỗi bài toán kích thước n/2  2T (n/2)

• Tổ hợp:

– TRỘN (MERGE) trên các mảng con cỡ n phần tử đòi hỏi thời gian (n)

 C(n) = (n)

(1)

2T(n/2) + (n)

nếu n =1

nếu n > 1

T(n) =

– Suy ra theo định lý thợ: T(n) = (n log n)

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

39

Ví dụ: Sắp xếp trộn

1

2

3

4

5

6

7

8

8 2 9 4 5 3 1 6

1

2

3

4

5

6

7

8

Divide

5 3 1 6

8 2 9 4

5

6

7

8

1

2

3

4

5 3

1 6

8 2

9 4

5

6

7

8

3

4

1

2

5

3

1

7

6

1 phần tử

Merge

9

4

8

2

6

8

1

2

3

4

3 5

1 6

8

2 8

4 9

1

2

3

4

5

6

7

Merge

1 3 5 6

2 4 8 9

1

2

3

4

5

6

7

8

Kết quả:

1 2 3 4 5 6 8 9

NGUYỄN ĐỨC NGHĨA

Bộ môn KHMT - ĐHBKHN

40

Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 5: Sắp xếp - Nguyễn Đức Nghĩa