Cấu trúc dữ liệu và giải thuật

Thuật toán Selection Sort - Ý tưởng: thuật toán sap xép Selection Sort 14 mot thuật toán sắp xếp các mảng bằng cách đi tìm phân tử có giá trị nhỏ nhất trong đoạn và thay đổi chúng với ph

or KHO4

«+ ® DAI HOC QUOC GIA THANH PHO HO CHi MINH

" Ss TRUONG DAI HOC KHOA HOC TU NHIEN

TP HO CHI MINH

NGUYEN VAN TRI - 21120345

BAO CAO

VE CAC THUAT TOAN

SẮP XÉP

MON HOC: CAU TRUC DU LIEU VA GIAI THUAT GIANG VIEN:NGUYEN TRAN DUY MINH

Thành phố Hỗ Chí Minh - 2022

MỤC LỤC

I0 9800 1 —— ồỒồỒ 1

I VỀ CÁC THUẬT TOÁN VÀ ĐỘ PHỨC TẠP CỦA CHÚNG 52 2255 2ccccsccec 2 1.1 Thuật toán Selection SOT 2 - 2 St TY TT HT HT TH Hà TH Hà TT KH TT 2 1.2 Thuat 0 ch 2

AI ` 0 nha 3

' AI ha 4

AI na 5

' TÀI 0C nha 7

1.7 Thuat toan Quick Sort nh 9 1.8 Thuat toan Radix Sort cece eee ceeeee cs eese cece cneeaecossaesecneesesnenaecassaesesnavsesaetesganees 10

IL = THUC NGHTEM CAC THUAT TOAN 0 eccccssssssssssssssssesssessssecssecesscssnesssessscssecasecessceatecessceas 13

1 Doi Voi cdc mang sAp XEp MAU MIN ccc ccc csesccssessecsseesscesecsecssecsseeseessessseeseeeseeseeaseess 13

2 _ Đối với thuật ton gan nhu dugc sap xép mg AN ccccccccscsstessecstessecsseesecesecsecsseesseenes 14

3 Đối với máng đã được sắp xếp tăng dần - St St re 15

4 Đối với máng được sắp xếp giảm dẫn - c2 n2 tr ertrrrrrerrrrrrrrrree 16

I VẺ CÁC THUẬT TOÁN VÀ ĐỘ PHỨC TẠP CỦA

CHÚNG

1.1 Thuật toán Selection Sort

- Ý tưởng: thuật toán sap xép Selection Sort 14 mot thuật toán sắp xếp các mảng

bằng cách đi tìm phân tử có giá trị nhỏ nhất trong đoạn và thay đổi chúng với phần

tử ở đoạn đầu đoạn chưa được sắp xép Tại mỗi bước lặp của thuật toán, phân tử nhỏ nhất của mang con chưa được sắp xếp sẽ được di chuyển về đoạn đã được sap xép

- Về code (hàm Swap mặc định đã được sử dụng và chèn vào mã nguồn):

(si SelectionSort(int a[], int n){

/foién min_idx 1A bién dùng để chỉ phần tử nhỏ nhất của mảng

int i, j, min_idx;

/Isử dụng vòng lặp đê chuyển phần tử nhỏ nhất về máng đã sắp xếp for (i =0; i<n-1; i++) {

//Gán min_idx bằng ¡, sau đó chạy vòng lặp với j=i+l

min_idx=1;

for=I+l;j<n;j++)

/mễu như phần tử thứ j nhỏ hơn phần tử thứ min_idx thì gán

min idx = j và đổi chỗ phần tử nhỏ nhất với

phần tử đầu tiên

1 (a[J]< a[min_1dx]) min_1dx=j;

if( min_idx!=i) Swap(a[min_idx],a[i]);

a

° Thời gian: vì thuật toán Selection Sort có hai phép lặp lòng vào nhau

với mỗi phép lặp là n bước nên về độ phức tạp về thời gian là:O(n*n) = O(n8)

° Không gian: vì các mảng là như nhau sau mỗi bước nên độ phức tạp

về không gian là O(1)

1.2 Thuật toán Insertion Sort

- Ý tưởng: Thuật toán Insertion Sort là 1 trong những thuật toán dễ thực hiện nhất và phù hợp với các đữ liệu có độ lớn nhỏ Về thuật toán, chúng ta xem nó như việc sắp xếp một bộ bài tây, đầu tiên ta cho lá bài đầu tiên làm gốc, đánh dấu lá bài

thứ 2 và so sánh độ lớn với lá bài thứ nhất, nếu nhỏ hơn thì ta sẽ thay đổi vị trí 2 lá

bài, nếu không thì ta giữ nguyên và chuyên dấu cho lá bài tiếp theo cho đến lá cuỗi

củng Cũng như vậy, thuật toán Insertion Sort cũng duyệt

//tao vong lap duyệt mảng và cho phân tử thứ 2 làm gốc

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

int key=a[i];

j=i-1,//j 1a biến duyệt qua các máng đã được sắp xếp

/IDi chuyên mảng a[0, i- 1], lớn hơn phần tử key lùi về phía trước phân tử của chúng I đơn vị

whileG>=0 && a[j]>a[key]{

a[j+l]Eall]:

j-=1;//duyệt các phần tử đã được sắp xếp

}

a[j+1]=key;

}

vo

° Thời gian: tương tự nhự Selection Sort là O(n?)

° Không gian: tương tự như Selection Sort la O(1)

1.3 Thuật toán Bubble Sort

- Ý tưởng: Thuật toán Bubble Sort hoạt động như việc chính đôn hang ngũ

trong hang, ta so sánh chiều cao của 2 cá nhân trong hàng, nếu bạn bên phái thấp

hơn thì ta đôi chỗ 2 bạn cho nhau và tiếp tục như thế Trong lập trình, ta duyệt 1

mang va dua các số lớn nhất dần về phía dưới bằng cách so sánh 2 phân tử từng cặp

với nhau, nếu phần tử bên phải nhỏ hơn phân tử bên trái thì ta tiếp tục đôi chỗ hoặc

không đôi chỗ nếu chúng đã theo thứ tự và tiếp tục xét tiếp cặp tiếp theo,như thé,

2

phần tử nhỏ hơn sẽ "nổi" lên, còn phân tử lớn hơn sẽ "chìm" dần và về bên phải, đó

là lý do vì sao thuật toán tên là Bubble Sort Cứ tiếp tục cho đến khi phần tử lớn nhất được đưa về cuối và ta xét tiếp vòng thứ hai, thứ ba cho đến khi mảng đã được sắp

xếp hoàn toàn

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

int temp;

/ta duyệt vào máng với vị trí đầu tiên là 0

for (nt1 = Ô; 1 < n; ++){

//ta duyệt mảng lần thứ 2 để bắt cặp với phần tử đầu tiên đề so sánh và đối chỗ với hàm Swap

for Gnt j =i+1;j <n; j++)

if (alj] > a[j+1]) Swap(a[j].a[j+1]) /⁄4a đối chỗ 2 phần tử nếu bên phải < bên trái

}

}

- Độ phúc tap:

e©_ Thời gian:tương tự như 2 thuật toán trên là O(n?)

e Không gian:tương tự nhự 2 thuật toán trên là O(1)

1.4 Thuật toán Shell Sort

- Y tưởng: Shell Sort cũng có ý tưởng hoạt động tương tự như thuật toán

Insertion Sort, thậm chí còn là bản nâng cấp của Insertion Sort nhằm tránh việc tráo

đôi vị trí của 2 phan tử cách xa nhau bằng cách so sánh các phan tir 6 các khoáng(gap hay interval) với các khoảng nhận giá trị là n/2, n⁄4, n/8, cho đến khi các khoảng bằng I Giải thuật khá hiệu quả với các dữ liệu có độ lớn trung bình và có độ phức tạp trung bình nhỏ hơn rất nhiều so với thuật toán Insertion Sort

- Vé code:

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

//tao vong lặp với biến interval dé chia mang ra thanh cdc khoang dé

so sánh

for(int interval = n/2 ; interval >0; interval/=2){

//tao vong lap cho bién i chạy trong khoáng đã được chia để tiễn hành Insertion Sort cho khoảng

for(int i= interval; i<n;i++){

temp =a[i];//luu các giá tị trong khoảng vào biến tạm để lưu giá trị vào vị trí chuẩn khi sắp xếp

/Icho biến j chạy trong khoáng dé tìm vị trí chính xác cho giá trị a[ï] for (int j=1, j>=interval && a[j-interval] > temp; J-=interval){

a[j]=alj-gap];//khi tim duoc vi tri chinh xac thì vòng lặp dừng lại a[j]=temp;//gan a[j] bang giá trị của ali] khi tìm được vị trí chính xác

}

} }

}

Thời gian: độ phức tạp của thuật toán Shell Sort phụ thuộc vào việc khoảng

chia của bạn cho thuật toán như thế nào Nếu trong trường hợp tốt nhất, khi

mà mảng đã được sắp xếp thì tổng độ chia của thuật toán bằng đúng dữ liệu

của mảng, độ phức tạp của Shell Sort là O(n#log›(n)) còn trong trường hợp xấu nhắt, thuật toán Shell Sort sẽ có độ phức tạp tương tự như Insertion Sort

là O(n’), và trung bình thuật toán nhận độ phức tạp là O(n*logs(n)?) Không gian: Ô(1)

1.5 Thuật toán Heap Sort

- Ý tưởng: Thuật toán Heap Sort là thuật toán được dựa trên cấu trúc đữ liệu

cây nhị phân Binary Heap Thuật toán giúp sắp xếp các phần tử lớn nhất trong danh

sách về cuối đữ liệu với tốc độ chạy nhanh và cài đặt không quá phức tạp Thuật

toán Heap Sort thường sẽ sử dụng câu trúc đữ liệu Max heap là chủ yếu với phần tử

lớn nhất sẽ luôn là nút còn các phần tử nhỏ nhất sẽ là lá, điều này giúp cho việc sắp xếp các phần tử lớn nhất về cuối

- Vé code, ching ta sé chia ra lam 2 ham, la ham Heapify dung để tạo ra kiêu

dữ liệu Binary Max Heap và hàm thứ 2 là Heap Sort dùng đề sắp xếp:

void Heapify( int a[], int n, int i){

int largest = i;

int left = 2*i+1;//xét vi tri node bên trái

int right=2*i+2;//xét vi tri node bên phải

//Néu nhw cay con bên trái lớn hơn gốc thì ta sẽ cho gốc là node bén trái

if(left<n && a[left]>a[largest])

largest=left;

//Tuong ty như cây cơn bên phải

1f(right<n && a[right]>a[largest |)

largest=right;

//Nếu như phần tử lớn nhất không phải là gốc thi ta sé thay đổi vị trí của

node đó với rễ sao cho phân tử lớn nhất luôn là gốc

1f(largest!=I)

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

//Ta tiếp tục đệ quy tiến trình trên với các node ở hàng dưới cho đến khi ra một cây đệ quy lớn nhất hoàn chỉnh

Heapify(a,n,largest);

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

// cho i chay tir gitra mang dé tạo thành một cây nhị phân

for(int i=n/2-1;i>=0;i )

Heapify(a,n,i);

//Đỗi chỗ giữa gốc của cây(thành phần lớn nhất) và vị trí cuối cùng

của mảng, sau đó cho tạo lại cây mới sau khi cắt mắt phần sốc để rút

gọn cây lại cho đến khi không còn phần tử nào trong cây thì mảng đã được sắp xẾp

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

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

Heapify(a,i,0);

}

Về độ phức tạp:

Dai hoc Khoa

1.6

trỊ” có

° Về thời gian: vi độ dài của một cây nhị phân khi có n phân tử là log(n),

kế cả là trường hợp xấu nhất khi ta phải di chuyên gốc tới phần node xa nhất thì vẫn là log(n) Và vì khi sắp xếp ta cần phải duyệt qua mảng n lần nên độ phức tạp lúc này sẽ là O(n*logz(n))

° Về không gian: O(1)

Thuật toán Merge Sort

Ý tưởng: Thuật toán Merge Sort là thuật toán áp dụng phương pháp “Chia để

độ phức tạp khi cài đặt ở mức trung bình và tốc độ khá nhanh trong các thuật

toán sắp xếp Ở thuật toán, ta sẽ chia mảng chính thành 2 mảng con, sau đây tiếp tục

chia 2 máng con thành 4 máng con khác nhau, tiếp tục cho đến khi máng tiếp theo chỉ còn I phân tử thì ta sẽ so sánh và đôi chỗ phân tử của các mảng khác nhau Cuôi cùng ta trộn các mảng lại theo quy tắc:

° So sánh các phần tử đứng đầu, nêu chúng nhỏ hơn thì cho vào danh sách mới, cho đến khi 1 trong 2 mảng là rỗng

° Cuối cùng, khi 1 trong 2 mang là rỗng thì ta lấy phần còn lại của máng cho vào mảng mới, ta được một mảng mới đã được sắp xếp

Vé code, sé chia ra lam 2 ham 1a ham Merge va ham MergeSort:

void Merge(int a[], int const low, int const mid, ins const high){

//tao ra 2 bién hang al, a2(vi bién động khi đặt làm độ lớn của máng

sẽ cho ra lỗi)

auto const al=mid-low+1;//biễn al lưu độ lớn của mang dau

auto const a2=high-mid;//biến a2 lưu độ lớn của máng thứ hai auto * lowArray = new int[al],//tao biến con trỏ mảng lowArray vào mảng có độ lớn al

auto * highArray = new Int|a2]; /tương tư như trên với độ lớn a2 /Ichia các máng ra đề sắp xếp theo 2 mảng

for (auto 1 = 031 < al; i++)

lowArray[i] = a[low + i];

for (auto j = 0; j < a2; j+4+)

highArray[j] = a[mid + 1 + j];

int k = low;//cho bién k bat đầu từ đầu mang

/Icho biến I và j đê so sánh giữa các máng với nhau, mục đích để hợp

nhất các mảng lại với nhau

while (auto i < al && auto j < a2) {

if dowArray[i] <= highArray[j]) {

/nễu như máng bên 1 nhỏ hơn mảng bên thứ 2 thì vị tr

đầu tiên là ở mảng 1

a[k] = lowArray [i];

i++;//tiép tuc cho dén khi giá trị máng 1 lớn hơn mảng

2

}

else { //txong tu nhu 6 trén trong truong hop mang 2 nhoé hon mang 1

a[k] = highArray [j];

j++:

} k++;//k chạy để tiếp tục hợp các mang lai với nhau }

//tiép tục chạy vòng lặp như trên để đưa các thanh phan còn lại của máng đã chia vào mảng

while (i < al) {

a[k] = lowArray[i];

i++;

k++;

}

while (j < a2) {

a[k] = highArray[]];

j++;

k++;

//sau khi da hop nhat xong, ta cân xóa các mảng tạm đê giải phóng bộ nhớ

vị các máng tạm là kiêu đữ liệu con trỏ để giái phóng bộ nhớ

delete[] lowArray;

delete[] highArray;

void MergeSort(int a[], int const low, int const high){

if(low>=high) return;//diéu kién dé thoát khỏi vòng lặp đệ quy

auto mid=low-+(high-low)/2;//lay giá trị trung vị của mảng

/Ichay dé quy cho mang nhằm tạo ra 2 mảng và cuối cùng là hợp nhất 2

mảng đó lại và tiếp tục chạy đệ quy cho đến khi xảy ra điều kiện trên

MergeSort(a, low, mid);

MergeSort(a, mid + 1, high);

Merge(a, low, mid, high);

1.7

}

Về độ phức tap:

° Thời gian: vì thuật toán luôn chia máng ra làm 2 phần từng đôi một nên thuật toán có thể được tính dựa trên phương trình sau:

T(n)=2T(n/2)+0(n)

có thê được tính là O(n*logs(n)) và luôn có độ phức tạp như vậy trong mọi trường hợp nên Merge Sort rất được ưa chuộng bởi vì tính ôn định về thời gian của thuật toán

Thuat toan Quick Sort ;

Vệ ý tưởng: thuật toán Quick Sort cũng sử dụng về ý tưởng “Chia đề tr” tương tự như Merge Sort Thế nhưng thay vì như Merge Sort chia các mảng ra thành 2 máng khác nhau rồi tiếp tục chia 2 cho đến khi đơn giản thì Quick Sort sẽ chia mảng ra thành các mảng dựa trên phan tử thường được gọi là pivot(phan tử chốt) Thường phản tử chốt được chọn

sẽ là phan tử trung vi(phân tử nằm ở giữa máng), lúc này thuật toán sẽ có độ phức tạp nhỏ hơn so voi khi ta chon pivot nằm ở phan tử đầu hoặc cuối

Về code:

void QuickSort(int a[], int low, int high){

if(low>=high) return;//diéu kiện để thoát khỏi đệ quy

int l0=low;

int hO=high;

int pivot=a[low+(high-low)/2]//lấy pivot nằm ở giá trị trung vị của mảng

while(10<h0){

while(a[10]<pivot) 10++;//tim cdc gid tri duoc sap xếp ở bên trái

while(a[h0]>pivot) h0 ;//tương tự như ở bên phải

I0<h0){ /khi các giá trị chưa được sắp xếp ở 2 bên thì ta đổi chỗ

các giá trị ây

Swap(a[]0],a[h0]);

10++;

h0 ;

}

1 (low<=l0) QuickSort(a,low,h0);⁄/ đệ quy cho các mảng ở bên trái đề sắp

xếp;

ifthigh>=h0) QuickSort(a,l0,hiegh);//tương tự đệ quy ở bên phải

}

- Về độ phức tạp:

° Thời gian: vì pivot của chúng ta khi cải đặt là trung vị của mảng, nên độ

phức tạp của thuật toán luôn là O(n#loga(n)), điều này khác với việc lấy pivot nam

ở giữa máng vì lúc này khi ta chia mang ra thì sẽ có thể dính vào trường hợp pivot

là giá trị lớn nhất hoặc nhỏ nhát, độ phức tạp lúc này sẽ là O(n?) Vì thế nên pivot

thường được lấy ở vị trí trung vi

1.8 Thuật toán Radix Sort

- Ý tưởng: Thuật toán Radix Sort hay còn gọi là Postmans Sort là một trong những

thuật toán phổ biến dung để sắp xép.Điểm khác biệt của Radix Sort so với các thuật toán sắp xếp khác chính là việc thay vì so sánh các số với nhau để sắp xếp chúng theo các chiều

tang dan hoac giam dan, thi Radix Sort su dung việc phân chia các chữ số thành từng chữ

số khác nhau và chia chúng ra thành từng bucket theo hang don vi, hang chục, hàng trăm,

của chữ số và tiếp tục như thế cho đến khi mảng đã được sắp xếp