Trong bài viết này Blog tuicocach.com sẽ giới thiệu tới các bạn thuật toán sắp xếp chọn. Đây là một trong các thuật toán sắp xếp căn bản thường dùng.
DANH SÁCH BÀI VIẾT Thuật toán sắp xếp nhanh (Quick Sort) Thuật toán sắp xếp trộn (Merge Sort) Thuật toán sắp xếp đổi chỗ trực tiếp (Interchange Sort) Thuật toán sắp xếp nổi bọt (Bubble Sort) Thuật toán sắp xếp chọn(Selection Sort) Thuật toán sắp xếp chèn (Insertion sort)
Ý tưởng của thuật toán selection sort
Thuật toán selection sort chia mảng ra làm 2 mảng con, mảng bên trái đã được sắp xếp và bên phải chưa được sắp xếp. Thuật toán selection sort sắp xếp một mảng bằng cách đi tìm phần tử có giá trị nhỏ nhất(sắp xếp mảng tăng dần) trong đoạn đoạn chưa được sắp xếp và đổi chỗ phần tử nhỏ nhất đó với phần tử ở đầu đoạn chưa được sắp xếp(không phải đầu mảng).
Ví dụ: Sử dụng thuật toán SelectionSort sắp xếp dãy {3,2,6,9,1,4,7,10,8,5} theo thứ tự tăng dần ta sẽ thấy các bước thực hiện như sau
Cài đặt thuật toán trên ngôn ngữ C/C++
#include <stdio.h>
//Hàm đổi chỗ 2 số nguyên a, b
void swap(int &a, int &b)
{
int temp = a;
a=b;
b=temp;
}
//Hàm sắp xếp chọn (selection Sort)
void selectionSort(int arr[], int n)
{
for (int i = 0; i < n-1; i++)
{
int min_index = i;
for (int j = i+1; j < n; j++)
{
//Tìm vị trí phần tử nhỏ nhất
if(arr[min_index] > arr[j])
min_index = j;
}
// Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên
swap(arr[i], arr[min_index]);
}
}
//Hàm xuất mảng
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {3,2,6,9,1,4,7,10,8,5};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Kết quả chạy chương trình trên
Đánh giá thuật toán sắp xếp chèn
Độ phức tạp thuật toán: O(n^2)
Cảm ơn đã theo dõi bài viết, nếu có bất kỳ thắc mắc hay góp ý comment bên dưới nhé.
