Đề tài Công nghệ thông tin: Các thuật toán sắp xếp cơ bản

CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN

Thành viên nhóm:
1. Nguyễn Chánh Đại
2. Mai Phước Vinh
3. Tất Huỳnh Anh Khôi

CẦN THƠ, 2015

MỤC LỤC
1. SẮP XẾP CHỌN (SELECTION SORT) ....................................................................................................... 1
2. SẮP XẾP CHÈN (INSERTION SORT)........................................................................................................ 1
3. SẮP XẾP NỔI BỌT (BUBBLE SORT) ........................................................................................................ 2
4. SẮP XẾP NHANH (QUICK SORT) .............................................................................................................. 3

CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN

1. Sắp xếp chọn (Selection Sort)
a. Ý tưởng: Xuất phát từ cuối (hoặc đầ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ử đó về vị trí đúng đầu (cuối) dãy hiện hành,
sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ 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.
b. Giải thuật:
 Bước 1: i = 1
 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]
 Bước 3: Hoán vị a[Min] và a[i]
 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ì
c. Độ phức tạp: O(n2)
d. Code tham khảo:
void selectionSort(int a[], int n) {
for (int i = 0; i key){
a[x+1] = a[x];
--x;
}
a[x+1] = key;
}
}

3. Sắp xếp nổi bọt (Bubble Sort)
a. Ý tưởng: Xuất phát từ cuối (hoặc đầ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ử đó về vị trí đúng đầu (cuối) dãy hiện hành,
sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ 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.
NGUYỄN CHÁNH ĐẠI – MAI PHƯỚC VINH – TẤT HUỲNH ANH KHÔI

TRANG 2

CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN

b. Giải thuật:
 Bước 1: i = 0
 Bước 2: Lần lượt so sánh và đổi chổ (nếu cần) từ phải sang trái đối với các phần
từ từ a[n] đến a[i]
 Bước 3: i = i + 1
 Bước 4: Nếu i < n thì quay lại Bước 2, ngược lại dừng.
c. Độ phức tạp: O(n2)
d. Code tham khảo
void BubbleSort(int a[], int n){
for (int i = 0; i < n-1; ++i){
for (int j = i+1; j < n; ++j) {
if (a[i] > a[j]) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
}
}

4. Sắp xếp nhanh (Quick Sort)
a. Ý tưởng: Tìm cách chia đôi dãy ban đầu bằng cách chọn ra một phần tử là chốt
(pivot). Từ dãy ban đầu, tất cả phần tử nhỏ hơn phần tử chốt thì đưa về bên trái
dãy, tất cả các phần tử lớn hơn hoặc bằng phần tử chốt thì đưa về bên phải dãy. Sau
bước này ta có phần tử chốt là đứng đúng vị trí. Dãy ban đầu phân chia làm hai dãy
con nằm hai bên chốt. Tiếp tục phân chia các dãy con theo cách tương tự đến khi
mọi dãy con đều có độ dài bằng 1. Có thể lựa chọn phần tử chốt nằm đầu, cuối hay
giữa dãy. Ở đây ta sẽ lựa chọn phần tử chốt nằm gần giữa dãy nhất.
b. Giải thuật:
NGUYỄN CHÁNH ĐẠI – MAI PHƯỚC VINH – TẤT HUỲNH ANH KHÔI

TRANG 3