Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
Chương 6:
Sắp xếp
Giảng viên: Ths. Nguyễn Thị Khiêm Hòa
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
2
Nội dung
 Các phương pháp sắp xếp cơ bản
 Đánh giá các phương pháp
 Quick_Sort
 Heap_Sort
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
3
Mục tiêu
 Trình bày các thuật toán thông dụng cho việc sắp xếp
trong (sắp xếp trên bộ nhớ trong - RAM)
 Minh họa các thuật toán
 Đánh giá thuật toán
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
4
Đặt vấn đề
 Trong công việc hàng ngày cũng như các bài toán quản lý
kinh tế cần tìm kiếm dữ liệu
 Dễ dàng
 Nhanh chóng
 Ví dụ: danh sách sinh viên, từ điển …
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
5
Sắp xếp (Sorting)
 Định nghĩa
 Sắp xếp là quá trình tổ chức lại một tập hợp k đối

.
 Sau n lượt ta có dãy A được sắp thứ tự
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
8
 Ví dụ:
Cho dãy số:
Phương pháp sắp xếp kiểu lựa chọn
(Selection Sort)
i = 1
i = 2
i = 3
i = 4
i = 5
i = 6i = 7
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
9
Phương pháp sắp xếp kiểu lựa chọn
(Selection Sort)
public void SelectionSort()
{
int min,vt;
for (int i = 0; i < idx-1; i++)
{
min = A[i];
vt = i;
for (int j = i + 1; j < idx; j++)
{
if (A[j] < min)
{
min = A[j];

A
2
đã được sắp.
 Thêm A
3
vào A
1
A
2
sẽ có đoạn A
1
A
2
A
3
đã được sắp.
 Tiếp tục cho đến khi thêm xong A
n
vào đoạn
A
1
,A
2
,…,A
n-1
sẽ có dãy A
1
,A
2
,…,A

Phương pháp sắp xếp chèn (Insertion Sort)
i = 8
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
18
Phương pháp sắp xếp chèn (Insertion Sort)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
19
Phương pháp sắp xếp chèn (Insertion Sort)
public void Insertion_Sort()
{
for (int i = 1; i < idx; i++)
{
int x = A[i];
int j = i - 1;
while ((j >= 0)&&(A[j] > x))
{
A[j + 1] = A[j];
j ;
}
A[j + 1] = x;
}
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
20
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
 Ý tưởng:
 Xét từ cuối dãy ngược về vị trí i
 Nếu hai phần tử kế cận ngược thứ tự thì đổi chỗ
cho nhau
 Thực hiện đến khi không còn phần tử để xét.

Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
23
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
i = 2
j = 6
j = 5
j = 3
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
24
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
i = 3
j = 6j = 4
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
25
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
i = 4
j = 7j = 5