CTDL và giải thuật - Sắp xếp chọn (Selection Sort).
Nhập vào số nguyên dương n
, tiếp theo là n
số nguyên của dãy số a
.
Hãy sắp xếp dãy số a
thành dãy không giảm (số sau không bé hơn số trước) và in dãy đó ra màn hình, sau mỗi phần tử có đúng một khoảng trắng.
Ví dụ:
- Test mẫu 1:
Input Output 6
1 3 2 5 2 -2-2 1 2 2 3 5
Vớia = [1, 3, 2, 5, 2]
thì kết quả mong muốn là:
"1 2 2 3 5 ".
- Test mẫu 2:
Input Output 4
3 2 1 41 2 3 4
Vớia = [3, 2, 1, 4
] thì kết quả mong muốn là:
"1 2 3 4 ".
Lý thuyết.
Giới thiệu giải thuật sắp xếp chọn (Selection Sort).
Giải thuật sắp xếp chọn (Selection Sort) là một giải thuật đơn giản. Giải thuật sắp xếp này là một giải thuật dựa trên việc so sánh in-place, trong đó danh sách được chia thành hai phần, phần được sắp xếp (sorted list) ở bên trái và phần chưa được sắp xếp (unsorted list) ở bên phải. Ban đầu, phần được sắp xếp là trống và phần chưa được sắp xếp là toàn bộ danh sách ban đầu.
Phần tử nhỏ nhất được lựa chọn từ mảng chưa được sắp xếp và được tráo đổi với phần bên trái nhất và phần tử đó trở thành phần tử của mảng được sắp xếp. Tiến trình này tiếp tục cho tới khi toàn bộ từng phần tử trong mảng chưa được sắp xếp đều được di chuyển sang mảng đã được sắp xếp.
Giải thuật này không phù hợp với tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là O(n2) với n
là số phần tử.
Cách hoạt động của Selection Sort:
Ví dụ như bài toán sắp xếp dãy a thành dãy không giảm với:
a = [4, 3, 1, 5, 7, 9, 6, 2]
Để minh họa chúng ta sẽ dùng những phần tử màu xanh để chỉ những phần tử đã được sắp xếp đúng vị trí. phần tử màu nâu đề chỉ phần tử đang nhỏ nhất trong đoạn còn lại.
Ban đầu ta sẽ khởi tạo dãy con bằng a[0], đương nhiên với dãy con một phần tử thì nó đã được sắp xếp.
Ta bắt đầu xét từ phần tử có chỉ số 0
đến n-1
.
Đầu tiên ta tìm phần tử nhỏ nhất trong dãy trong khoảng từ 0
đến 7
. Sau đó hoán đổi cho phần tử a[0]
.
Tiếp theo tìm phần tử nhỏ nhất trong dãy trong khoảng từ 1
đến 7
. Sau đó hoán đổi cho phần tử a[1]
.
Tiếp theo tìm phần tử nhỏ nhất trong dãy trong khoảng từ 2
đến 7
. Sau đó hoán đổi cho phần tử a[2]
.
Tiếp theo tìm phần tử nhỏ nhất trong dãy trong khoảng từ 3
đến 7
. Sau đó hoán đổi cho phần tử a[3]
.
Tiếp theo tìm phần tử nhỏ nhất trong dãy trong khoảng từ 4
đến 7
. Sau đó hoán đổi cho phần tử a[4]
.
Tiếp theo tìm phần tử nhỏ nhất trong dãy trong khoảng từ 5
đến 7
. Sau đó hoán đổi cho phần tử a[5]
.
Tiếp theo tìm phần tử nhỏ nhất trong dãy trong khoảng từ 6
đến 7
. Sau đó hoán đổi cho phần tử a[6]
.
Còn 1
phần tử cuối cùng chắc chắn đã ở vị trí đúng.
Code C++ mẫu:
void selectionSort(int a[], int n){
int indexMin;
for (int i = 0; i < n-1; i++){
indexMin = i;
for (int j = i+1; j < n; j++){
if (a[indexMin] > a[j]){
indexMin = j;
}
}
if (i != indexMin){
int temp = a[i];
a[i] = a[indexMin];
a[indexMin] = temp;
}
}
}
Hướng dẫn bài tập.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
void printArray(int a[], int n){
for (int i = 0; i < n; i++){
cout << a[i] << " ";
}
}
void selectionSort(int a[], int n){
int indexMin;
for (int i = 0; i < n-1; i++){
indexMin = i;
for (int j = i+1; j < n; j++){
if (a[indexMin] > a[j]){
indexMin = j;
}
}
if (i != indexMin){
int temp = a[i];
a[i] = a[indexMin];
a[indexMin] = temp;
}
}
}
int a[100001];
int main(){
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
selectionSort(a, n);
printArray(a, n);
return 0;
}