Cài đặt mô phỏng thuật toán sắp xếp chọn trực tiếp và đổi chỗ trực tiếp
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.55 MB, 53 trang )
BÁO CÁO
ĐỒ ÁN MÔN HỌC
ĐỀ TÀI
Giảng viên hướng dẫn : Đào Minh Châu
Sinh viên thực hiện : Nguyễn Anh Tài - 2033183007
Phan Thị Kim Ngân - 2033188001
NỘI DUNG BÁO CÁO
1. Tổng quan và khái niệm về các thuật tốn sắp xếp và tìm kiếm .
2. Mơ phỏng giải thuật đổi chỗ trực tiếp InterChange Sort.
3. Mô phỏng giải thuật sắp xếp chọn trực tiếp Selection Sort.
4. Mô phỏng giải thuật sắp xếp nhanh Quick Sort.
5. Mô phỏng giải thuật tìm kiếm tuyến tính Linear Search.
6. Mơ phỏng giải thuật tìm kiếm nhị phân Binary Search.
TỔNG QT VÀ KHÁI NIỆM
THUẬT TỐN SẮP XẾP VÀ TÌM KIẾM
1. Thuật tốn là gì ?
- Thuật tốn là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự
xác định sao cho sau khi thực hiện một dãy các thao tác ấy, từ Input của bài
toán, ta nhận được Output cần tìm, giải quyết được yêu cầu bài tốn đặt ra.
2. Sắp xếp và tìm kiếm :
- Sắp xếp là quá trình xử lý các phần tử trong một danh sách nhằm để đặt lại chúng
theo một thứ tự nhất định để thoả mãn điều kiện nào đó dựa trên thơng tin của
chúng.
- Tìm kiếm là q trình tìm một phần tử nằm trong một tập hợp nhiều phần
tử dựa vào một miêu tả (điều kiện) nào đó.
GIẢI THUẬT THƠNG DỤNG
• Các giải thuật sắp xếp
1. Đổi chỗ trực tiếp – Interchange Sort
2. Sắp xếp chọn – Selection Sort
3. Sắp xếp nhanh – Quick Sort
• Các giải thuật tìm kiếm
1. Tìm kiếm tuyến tính
2. Tìm kiếm nhị phân
Bài Tốn Sắp Xếp
• Cho danh sách có N phần tử A0, A1, A2…, An-1.
• Sắp xếp danh sách (dãy) có N phần tử A(0), A(1), ..., A(n-1) là
q trình xử lý các phần tử trong danh sách để đặt chúng theo
một thứ tự thỏa mãn một số yêu cầu nào đó dựa trên thơng tin
lưu tại mỗi phần tử. Ví dụ :
Sắp xếp danh sách sinh viên tăng theo điểm trung bình.
Sắp xếp danh sách giáo viên tăng theo tên.
• Để đơn giản ta dùng mảng 1 chiều A để lưu danh sách trên
trong bộ nhớ chính.
Bài Tốn Sắp Xếp
• a: là dãy các phần tử dữ liệu
• Để sắp xếp dãy a theo thứ tự (giả sử theo thứ tự tăng), ta tiến
hành triệt tiêu tất cả các cặp nghịch thế trong a.
Nghịch thế:
• Cho dãy có n phần tử a0, a1,…,an-1
• Nếu i<j và ai >aj
20
3
4
8
a[0], a[1] là cặp nghịch thế
• Đánh giá độ phức tạp của giải thuật, ta tính :
Css: Số lượng phép so sánh cần thực hiện
CHV: Số lượng phép hoán vị cần thực hiện
Các Thuật Toán Sắp Xếp
1. Đổi chỗ trực tiếp – Interchange Sort
2. Sắp xếp chọn – Selection Sort
3. Sắp xếp nhanh - Quick Sort
4. Shaker Sort
5. Chèn trực tiếp – Insertion Sort
6. Chèn nhị phân – Binary Insertion Sort
7. Shell Sort
8. Heap Sort
9. Nổi bọt – Bubble Sort
10. Merge Sort
Các Thuật Toán Sắp Xếp
1. Đổi chỗ trực tiếp – Interchange Sort
2. Chọn trực tiếp – Selection Sort
3. Sắp xếp nhanh – Quick Sort
Interchange sort - Giải thuật :
• Bước 1: Khởi tạo: i = 0; // bắt đầu từ đầu dãy
• Bước 2: Khởi tạo : j = i+1; //phần tử tiếp theo
• Bước 3:
Vịng lặp với ĐK: j < n thực hiện :
So sánh: a[j]
j = j+1; // tăng biến j để tìm nghịch thế mới
• Bước 4: Tăng biến : i = i+1;
So sánh: i < n-1: Quay lại Bước 2.
Ngược lại: Dừng.
Interchange Sort – Cài đặt :
void InterchangeSort(int a[], int n )
{ for ( int i = 0 ; i
if(a[j ]< a[i])
// cặp nghịch thế
{ int temp = a[i];
a[i] = a[j];
a[j] = temp; }
}
Interchange Sort – Minh họa :
j
1
1
2
0
2
8
5
1
6
4
1
2
3
4
5
6
i
void InterchangeSort(int a[], int n )
{
for ( int i = 0 ; i
if(a[j ]< a[i])
{ int temp = a[i];
a[i] = a[j];
}
a[j] = temp; }
// cặp nghịch thế
1
5
7
Interchange Sort – Minh họa :
j
1
0
i
0
2
1
2
1
8
5
2
6
4
2
3
4
5
6
void InterchangeSort(int a[], int n )
{
for ( int i = 0 ; i
if(a[j ]< a[i])
{ int temp = a[i];
a[i] = a[j];
}
a[j] = temp; }
// cặp nghịch thế
1
5
7
Interchange Sort – Minh họa :
j
1
2
0
1
i
0
4
1
2
2
void InterchangeSort(int a[], int n )
{
for ( int i = 0 ; i
if(a[j ]< a[i])
{ int temp = a[i];
a[i] = a[j];
}
a[j] = temp; }
8
5
6
4
3
4
5
6
// cặp nghịch thế
1
5
7
Interchange Sort – Minh họa :
j
1
2
4
0
1
2
i
0
void InterchangeSort(int a[], int n )
{
for ( int i = 0 ; i
if(a[j ]< a[i])
{ int temp = a[i];
a[i] = a[j];
}
a[j] = temp; }
5
1
2
3
8
6
5
4
5
6
// cặp nghịch thế
1
5
7
Interchange Sort – Minh họa :
1
2
3
4
5
6
7
8
1
2
4
5
6
8
1
2
1
5
Các Thuật Toán Sắp Xếp
1. Đổi chỗ trực tiếp – Interchange Sort
2. Chọn trực tiếp – Selection Sort
3. Sắp xếp nhanh – Quick sort
Selection sort - Giải thuật :
• Bước 1: Khởi tạo i = 0;
• 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-1]
+ Bước 2.1: Gán biến min = i; //Giả sử phần tử A[i] có GTNN
+ Bước 2.2: Tìm giá trị nhỏ nhất trong đoạn [i + 1, n - 1].
• Khởi tạo biến j với: j = i + 1;
• Vịng lặp với điều kiện (j < n - 1) thì thực hiện:
So sánh (A[j] < A[min]) thì gán min = j; //vị trí min mới
• Bước 3 : Hốn vị : a[min] và a[i]
• Bước 4 : Nếu (i < n-1) thì :
i = i+1; Lặp lại Bước 2;
Ngược lại: Dừng.
Selection Sort – Cài đặt :
void SelectionSort(int a[],int n )
{
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i
min = i;
for(j = i+1; j
min = j; // lưu vtrí phần tử hiện nhỏ nhất
}
}
if (min != i)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
Selection Sort – Minh họa :
Vị trí nhỏ nhất(0,7)
Hoanvi(a[0], a[4])
min
1
2
0
2
8
5
1
6
4
1
2
3
4
5
6
i
void SelectionSort(int a[],int n )
{
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i
for(j = i+1; j
min = j; // lưu vtrí phần tử hiện nhỏ nhất
if (min != i)
{ int temp = a[i];
a[i] = a[j];
a[j] = temp;
}}}
1
5
7
Selection Sort – Minh họa :
Hoanvi(a[1],
a[1])
Vị trí nhỏ nhất(1,7)
min
1
2
8
5
0
1
2
3
1
2
4
i
void SelectionSort(int a[],int n )
{
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i
for(j = i+1; j
min = j; // lưu vtrí phần tử hiện nhỏ nhất
if (min != i)
{ int temp = a[i];
a[i] = a[j];
a[j] = temp;
}}}
6
4
5
6
1
5
7
Selection Sort – Minh họa :
Vị trí nhỏ nhất(2,7)
Hoanvi(a[2], a[6])
min
1
2
8
5
0
1
2
3
1
2
4
i
void SelectionSort(int a[],int n )
{
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i
for(j = i+1; j
min = j; // lưu vtrí phần tử hiện nhỏ nhất
if (min != i)
{ int temp = a[i];
a[i] = a[j];
a[j] = temp;
}}}
6
4
5
6
1
5
7
Selection Sort – Minh họa :
Hoanvi(a[3],
a[3])
Vị trí nhỏ nhất(3,
7)
min
1
2
4
5
0
1
2
3
1
2
4
i
void SelectionSort(int a[],int n )
{
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i
for(j = i+1; j
min = j; // lưu vtrí phần tử hiện nhỏ nhất
if (min != i)
{ int temp = a[i];
a[i] = a[j];
a[j] = temp;
}}}
6
8
5
6
1
5
7
Selection Sort – Minh họa :
Vị trí nhỏ nhất(4,
7)
1
2
4
5
0
1
2
3
Swap(a[4], a[5])
min
i
void SelectionSort(int a[],int n )
{
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i
for(j = i+1; j
min = j; // lưu vtrí phần tử hiện nhỏ nhất
if (min != i)
{ int temp = a[i];
a[i] = a[j];
a[j] = temp;
}}}
1
2
4
6
8
5
6
1
5
7
Selection Sort – Minh họa :
Hoanvi(a[5],
a[6])
min
Vị trí nhỏ
nhất(5,7)
1
2
4
5
6
0
1
2
3
4
i
void SelectionSort(int a[],int n )
{
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i
for(j = i+1; j
min = j; // lưu vtrí phần tử hiện nhỏ nhất
if (min != i)
{ int temp = a[i];
a[i] = a[j];
a[j] = temp;
}}}
1
2
5
8
6
1
5
7
Selection Sort – Minh họa :
Vị trí nhỏ nhất(6,
7)
min
1
2
4
5
6
8
0
1
2
3
4
5
i
void SelectionSort(int a[],int n )
{
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i
for(j = i+1; j
min = j; // lưu vtrí phần tử hiện nhỏ nhất
if (min != i)
{ int temp = a[i];
a[i] = a[j];
a[j] = temp;
}}}
1
2
6
1
5
7
