TRƯỜNG ĐẠI HỌC GIAO THƠNG VẬN TẢI TP. HỒ CHÍ MINH
KHOA CƠNG NGHỆ THƠNG TIN

BÁO CÁO BÀI TẬP NHĨM
PHÂN TÍCH THIẾT KẾ GIẢI THUẬT
Đề tài: Phân tích độ phức tạp của giải thuật sắp xếp Quick sort

Ngành:

CÔNG NGHỆ THÔNG TIN

Chuyên ngành: CÔNG NGHỆ THÔNG TIN

Giảng viên hướng dẫn :

Trần Anh Tuấn

Mơn học:

Phân tích thiết kế giải thuật

Mã học phần:

010112400301

Nhóm:

01


TP. Hồ Chí Minh, 2021

DANH SÁCH THÀNH VIÊN:
1.
2.
3.
MỤC LỤC:
I.
II.

III.
IV.
V.
VI.

TRẦN KIM PHƯỚC
NGUYỄN VIẾT PHÚ
LÊ THÀNH TRUNG
Tổng quan về đề tài

Cơ sở lý thuyết
1.
Quick sort l
2.
Thuật toán p
3.
Ý tưởng thu
4.
Cách chọn p
5.
Phương phá
6.

Giải thuật Q
Minh họa chương trình và phân tí
Kết luận
Câu hỏi củng cố
Tài liệu tham khảo


Tổng quan về đề tài
Bài toán sắp xếp chắc chắn khơng cịn xa lạ gì với mỗi chúng ta, nó là một trong
những bài toán được bắt gặp nhiều nhất trong thực tế. Ví dụ như sắp xếp danh sách
lớp học, sắp xếp quyển sách, sắp xếp tiền… Vậy thì bài tốn sắp xếp là gì? Bài
tốn sắp xếp là chúng ta sẽ sắp xếp lại các phần tử của một danh sách theo chiều
tăng hoặc giảm dần theo một tiêu chí nào đó của phần tử trong danh sách.Ví dụ
như bạn sắp xếp danh sách lớp học theo điểm trung bình từ cao đến thấp, sắp
những quyển sách theo kích cỡ từ nhỏ đến lớn, sắp xếp những tờ tiền theo mệnh
giá từ thấp đến cao… Mục đích của việc sắp xếp chính là giúp ta có cái nhìn tổng
quan hơn về những dữ liệu mà ta có, dễ dàng tìm kiếm những phần tử đứng nhất
về một tiêu chí nào đó. Trong lập trình, sắp xếp khơng chỉ đơn giản là để tìm một
hoặc nhiều phần tử đứng đầu về một tiêu chí nào đó hay để có cái nhìn tổng quan
về dữ liệu, sắp xếp cịn làm cơ sở cho các giải thuật nâng cao với hiệu suất cao
hơn. Có rất nhiều thuật tốn sắp xếp được sử dụng như: Merge sort, Selection sort,
Quick sort, Bubble sort,... Trong khn khổ đề tài được giao, nhóm chúng em xin
được nghiên cứu và trình bày về giải thuật sắp xếp Quick sort, một thuật tốn có
khà năng sắp xếp với tốc độ cao hơn hẳn so với các thuật toán Insertion sort,
Selection sort hay Bubble sort.
I.

3



Cơ sở lý thuyết:
1.
Quick sort là gì?
Sắp xếp nhanh (Quick sort) hay sắp xếp phân đoạn (Partition) là là thuật toán sắp
xếp dựa trên kỹ thuật chia để trị, cụ thể ý tưởng là: chọn một điểm làm chốt (gọi là
pivot), sắp xếp mọi phần tử bên trái chốt đều nhỏ hơn chốt và mọi phần tử bên phải
đều lớn hơn chốt, sau khi xong ta được 2 dãy con bên trái và bên phải, áp dụng
tương tự cách sắp xếp này cho 2 dãy con vừa tìm được cho đến khi dãy con chỉ còn
1 phần tử.
AI.

Phần tử được chọn làm chốt rất quan trọng, nó quyết định thời gian thực thi của
thuật toán. Phần tử được chọn làm chốt tối ưu nhất là phần tử trung vị, phần tử này
làm cho số phần tử nhỏ hơn trong dãy bằng hoặc sấp xỉ số phần tử lớn hơn trong
dãy. Tuy nhiên, việc tìm phần tử này rất tốn kém, phải có thuật tốn tìm riêng, từ
đó
NHẬN XÉT CỦA GIÁO VIÊN:


làm giảm hiệu suất của thuật tốn tìm kiếm nhanh, do đó, để đơn giản, người
ta thường sử dụng phần tử chính giữa làm chốt.
Thuật tốn phân đoạn (Partition)
Đặt pivot là phần tử cuối cùng của dãy số Arr. Chúng ta bắt đầu từ phần tử trái
nhất của dãy số có chỉ số là left, và phần tử phải nhất của dãy số có chỉ số là right
- 1 (bỏ qua phần tử pivot). Khi nào left < right mà arr[left] > pivot và arr[right] <
pivot thì đổi chỗ hai phần tử left và right. Sau cùng, ta đổi chỗ hai phần tử left và
pivot cho nhau. Khi đó, phần tử left đã đứng đúng vị trí và chia dãy số làm đơi
(bên trái và bên phải).
3.
Ý tưởng thuật tốn

● Chọn một giá trị khóa v làm chốt (pivot).
● Phân hoạch dãy A[0]…A[n-1] thành hai mảng con “bên trái” và “bên phải”.
Mảng con “bên trái” bao gồm các phần tử có khóa nhỏ hơn chốt, mảng con
“bên phải” bao gồm các phần tử có khóa lớn hơn oặc bằng chốt.
● Sắp xếp mảng con “bên trái” và mảng con “bên phải”.
● Sau khi đã sắp xếp được mảng con “bên trái” và mảng con “bên phải”
thì mảng đã cho sẽ được sắp xếp bởi vì tất cả các khóa trong mảng con
“bên trái” đều nhỏ hơn các khóa trong mảng con “bên phải”.
● Việc sắp xếp các mảng con “bên trái” và “bên phải” cũng được tiến hành
bằng phương pháp nói trên.
● Một mảng chỉ gồm một phần tử hoặc gồm nhiều phần tử có khóa bằng
nhau thì dã có thứ tự.
2.

4.
●
●
●
●
●
●
5.

Cách chọn phần tử làm pivot
Chọn giá trị khóa lớn nhất trong hai phần tử có khóa khác nhau đầu tiên
kể từ trái qua.
Nếu mảng chỉ gồm một phần tử hay gồm nhiều phần tử có khóa bằng
nhau thì khơng có chốt.
Chọn phần tử bên trái ngồi cùng (phần tử đầu tiên của mảng)
Chọn phần tử bên phải ngoài cùng (phần tử cuối cùng của mảng)

Ngẫu nhiên một phần tử (sử dụng hàm random mà ngơn ngữ lập trình cung
cấp)
Phần tử chính giữa của mảng.
Phương pháp phân hoạch

5


●
●
●
●
●
●
6.
●

●

Để phân hoạch mảng, ta dùng hai “con nháy” L và R trong đó L từ bên trái
và R từ bên phải.
Ta cho L chạy sang phải cho tới khi gặp phần tử có khóa lớn hơn hoặc bằng
chốt.
Cho R chạy sang trái cho tới khi gặp phần tử có khóa nhỏ hơn chốt.
Tại chỗ dừng của L và R nếu L < R thì hốn vị A[L], A[R].
Lặp lại quá trình dịch sang phải, sang trái của hai “con nháy” L và R cho đến
khi L > R.
Khi đó L sẽ là điểm phân hoạch, cụ thể là A[L] là phần tử đầu tiên của mảng
con “bên phải”.
Giải thuật Quick sort

Để sắp xếp mảng A[i]…A[j] ta làm các bước sau:
− Xác định chốt trong mảng A[i]…A[j].
− Phân hoạch mảng A[i]…A[j] đã cho thành hai mảng con A[i]…A[k1] và A[k]…A[j].
− Sắp xếp mảng A[i]…A[k-1] bằng đệ quy.
− Sắp xếp mảng A[k]…A[j] bằng đệ quy.
Đệ quy sẽ dừng khi khơng cịn tìm thấy chốt.

6


BI.

-

Minh họa chương trình và phân tích độ phức tạp của thuật tốn
1. Minh họa chương trình

Hàm phân hoạch

int partition (int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);

}

for (int j = low; j <= high- 1; j++)
{
if (arr[j] <= pivot)
{

i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);

- Hàm Quick sort
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

- Toàn bộ source code chương trình
#include <iostream>
using namespace std;
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition (int arr[], int low, int high)
{


7


int pivot = arr[high];
int i = (low - 1);

}

for (int j = low; j <= high- 1; j++)
{
if (arr[j] <= pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);

void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)

{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int n;
cout << "Nhap so phan tu: " ;
cin >> n;
int a[n];
cout << "Nhap vao gia tri moi phan tu cua mang: " << endl;
for (int i=0;i{
cout <<"a["<< i<<"]" << " = ";
cin >> a[i];
}
quickSort(a, 0, n-1);
cout << "Mang sau khi duoc sap xep: " << endl;
printArray(a, n);
system("pause");
return 0;
}

8


2.
-

Đánh giá độ phức tạp của thuật toán

Trường hợp xấu nhất

Trong trường hợp xấu nhất, phân hoạch bị lệch. Nghĩa là mảng có n phần tử phân
hoạch thành hai mảng con. Mảng con “bên trái” gồm n-1 phần tử và mảng con bên
phải chỉ gồm 1 phần tử.
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

T(n) = T(n-1) + T(1) + n
=

T(n-1) + n + 1

=

T(n-2) + (n-1) + n + 2

=

T(n-3) + (n-2) + (n-1) + n +3

…

-

=

T(1) +(2 + 3+ 4 +…+ n) + n - 1

=

1 + 2 + 3 +…+ n + n - 1 =

n(n +1)
+ n – 1 O(n2)
2

Trường hợp tốt nhất

Trong trường hợp tốt nhất khi ta chọn được chốt sao cho hai mảng con có kích
thước bằng nhau và bằng n/2. Khi đó ta có độ phức tạp của thuật toán như sau
quickSort(int arr[], int low, int high)
{
if (low < high)

9


{
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);

}
}

T(n) = 2T(

n
2) + n

=

n
n
2[2T( 2 2 ) + 2] + n

=

n
n
22[2T(2 3 ) + 2 2 ] + 2n

=

23[2T(2

n
4

)+ 2

n
3

] + 3n

…
=

n
2kT(2 k ) + kn

=

2kT(1) + kn = n.1 + n.logn O(n.logn)

10


IV.

Kết luận

Quick Sort là một thuật toán sắp xếp hiệu quả dựa trên việc phân chia mảng dữ
liệu thành các nhóm phần tử nhỏ hơn. Giải thuật sắp xếp nhanh chia mảng thành
hai phần bằng cách so sánh từng phần tử của mảng với một phần tử được gọi là
phần tử chốt. Một mảng bao gồm các phần tử nhỏ hơn hoặc bằng phần tử chốt và
một mảng gồm các phần tử lớn hơn phần tử chốt.
Quá trình phân chia này diễn ra cho đến khi độ dài của các mảng con đều bằng 1.

Với phương pháp đệ quy ta có thể sắp xếp nhanh các mảng con sau khi kết thúc
chương trình ta được một mảng đã sắp xếp hoàn chỉnh. Giải thuật sắp xếp nhanh tỏ
ra khá hiệu quả với các tập dữ liệu lớn khi mà độ phức tạp là O(nlogn).

11


V.
1.

Câu hỏi củng cố
Khi nào thì độ phức tạp của thuật toán là lớn nhất và khi nào là
nhỏ nhất?

Trả lời: Độ phức tạp của thuật toán là lớn nhất khi mảng bị phân hoạch lệch. Nghĩa
là sau khi phân hoạch mảng đã cho gồm n phần tử sẽ được chia thành hai mảng
con. Mảng con bên trái gồm n-1 phần tử và mảng con bên phải chỉ có một phần tử
duy nhất. Khi đó độ phức tạp của thuật toán sẽ là O(n 2). Độ phức tạp của thuật
toán là nhỏ nhất khi ta chọn được chốt sao cho hai mảng con có kích thước bằng
nhau và bằng n/2. Khi đó độ phức tạp của thuật tốn là O(n.logn).

2. Cho mảng sau:
2

6

1

9

7

4

3

Hãy nêu cách chọn pivot sao cho khi sắp xếp mảng trên ta được độ phức tạp
của thuật toán là nhỏ nhất.
Trả lời:
Đầu tiên, ta chọn 4 là pivot. Khi đó mảng sẽ được chia thành hai mảng con. Mảng
con bên trái gồm các phần tử nhỏ hơn 4
2

3

1

Và mảng con bên phải sẽ gồm các phần tử lớn hơn 4
7

9

6

Ở mảng con bên trái, ta chọn 2 là pivot. Khi đó mảng sẽ được sắp xếp thành
1

2

3

Ở mảng con bên phải, ta chọn 6 là pivot. Khi đó mảng sẽ được sắp xếp thành
6

7

9

Kết thúc thuật tốn, mảng đã cho được sắp xếp theo đúng thứ tự với độ phức tạp là
O(n.logn)
1

23

4

6

7

9

12


3. Dùng giải thuật Quick Sort để sắp xếp mảng sau theo đúng thứ tự tăng
dần.
2
6
3

7
4
5
1
Trong ví dụ ta ln chọn phần tử pivot là phần tử đứng giữa danh sách
Do ngẫu nhiên, phần tử chốt a[4]=7 là phần tử lớn nhất trong dãy, ta tìm từ
trái sang phải khơng có phần tử nào lớn hơn phần tử chốt, do đó ta đổi phần tử
chốt với phần tử cuối cùng, danh sách được chia thành hai danh sách con

Việc phân chia tiếp tục với danh sách con a[1..6]. Phần tử pivot được chọn
là a[4]=1. Từ trái sang phải tìm được phần tử đầu tiên lớn hơn a[4]=1 là
a[1]=2, từ phải sang phần tử đầu tiên <=1 là chính a[4]. Đổi chố hai phần tử
này
1
6
3
2
4
5
-7
Đi tiếp sang phải ta được a[2]>1 ở phía ngược lại đi tiếp sang trái tìm được
phần tử nhỏ hơn hoặc bằng chốt là chính a[1]=1nhưng lúc này hai đường đã
chạm nhau nên ta không đổi nữa. Do vậy a[1..6] được phân chia thành hai

Tiếp tục phân chia a[2..6] với phần tử chốt {\displaystyle a[4]= 2 ta được
Tiếp tục phân chia a[3..6] với phần tử chốt a[5]=4 ta được
1
Tiếp tục phân chia a[3..4] với phần tử chốt a[4]=4 và a[5..6] với phần tử chốt
a[6]=5 ta được
1

--2

--

3

--

4

--

5

--

6

--

7

13


VI.
1.
2.
3.

4.
5.
6.

Tài liệu tham khảo
/> /> /> /> /> />7. />fbclid=IwAR0pBWN3sUaoGkzOh6PRwid7BDnLfc5EZrKfo2iWoNtaJUHwxHK5EIAfhQ

14


7.

15


16