Sắp xếp chọn là thuật toán sắp xếp bằng cách lặp qua mảng từ đầu, thay thế mỗi phần tử bằng phần tử nhỏ nhất trong phần còn lại. Phần bên trái đã sắp xếp, bên phải chưa. Mỗi bước đặt phần tử nhỏ nhất tiếp theo vào vị trí hiện tại bằng hoán đổi.
Thuật toán Selection Sort
int arr[5] = {5,4,2,1,3};
int i, j;
Duyệt i=0 đến size-1
Duyệt j=i+1 đến size-1
Tìm nhỏ nhất, lưu chỉ số pos.
Hoán đổi arr[pos] với arr[i].
Kết thúc.
Selection Sort đệ quy
Tìm chỉ số phần tử nhỏ nhất.
Nếu chỉ số nhỏ nhất = size mảng thì trả về.
Ngược lại hoán đổi phần tử hiện tại với nhỏ nhất.
Đệ quy cho phần mảng còn lại (loại phần đã sắp xếp).
Ví dụ
Đầu vào - Arr[] = {5,7,2,3,1,4}, length=6
Đầu ra - Mảng đã sắp xếp: 1 2 3 4 5 7
Giải thích -
Lần 1: 5 7 2 3 1 4 → hoán đổi → 1 2 7 3 5 4 Lần 2: 1 2 7 3 5 4 → không hoán đổi Lần 3: 1 2 7 3 5 4 → hoán đổi → 1 2 3 7 5 4 Lần 4: 1 2 3 7 5 4 → hoán đổi → 1 2 3 4 5 7 Lần 5: 1 2 3 4 5 7 → không hoán đổi
Đầu vào - Arr[] = {1, 2, 3, 3, 2}
Đầu ra - Mảng đã sắp xếp: 1 2 2 3 3
Giải thích -
1 2 3 3 2 → không hoán đổi 1 2 3 2 3 → không hoán đổi 1 2 3 2 3 → hoán đổi → 1 2 2 3 3 1 2 2 3 3 → không hoán đổi
Phương pháp sử dụng trong chương trình dưới đây
Trong đệ quy Selection Sort, điều kiện dừng là chỉ số nhỏ nhất = size-1. Ngược lại tìm nhỏ nhất từ mảng, hoán đổi với chỉ số hiện tại, đệ quy sắp xếp phần mảng chưa sắp xếp bên phải.
Nhập mảng Arr[] và length số phần tử.
Hàm findMin(int arr[], int i, int j) trả về chỉ số phần tử nhỏ nhất giữa arr[i+1] đến arr[j].
Biến minpos.
Nếu i == j trả về i.
Ngược lại đệ quy tìm minpos = findMin(arr, i+1, j).
Nếu arr[i] < arr[minpos] thì minpos = i. Trả về minpos.
Hàm recurselectSort(int arr1[], int len1, int pos1) sắp xếp mảng tăng dần bằng đệ quy Selection Sort.
Nếu pos1 == len1 trả về.
Ngược lại minpos1 = findMin(arr1, pos1, len1-1).
Nếu minpos1 != pos1 thì hoán đổi arr1[pos1] và arr1[minpos1] bằng biến temp.
Đệ quy cho phần còn lại: recurselectSort(arr1, len1, pos1+1).
Khi len = 1 thoát đệ quy, mảng đã sắp xếp.
In mảng đã sắp xếp trong main.
Ví dụ mã
#include <iostream> using namespace std; int findMin(int arr[], int i, int j){ int minpos; if (i == j){ return i; } minpos = findMin(arr, i + 1, j); if(arr[i]<arr[minpos]){ minpos=i; } return (minpos); } void recurselectSort(int arr1[], int len1, int pos1){ int temp; int minpos1; if (pos1 == len1){ return; } minpos1 = findMin(arr1, pos1, len1-1); if (minpos1 != pos1){ temp=arr1[pos1]; arr1[pos1]=arr1[minpos1]; arr1[minpos1]=temp; } recurselectSort(arr1, len1, pos1 + 1); } int main(){ int Arr[] = {1,5,3,0,9,3,5}; int length = sizeof(Arr)/sizeof(Arr[0]); recurselectSort(Arr,length,0); cout<<"Mảng sắp xếp bằng Selection Sort đệ quy: "<<endl; for (int i = 0; i<length ; i++){ cout << Arr[i] << " "; } return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Mảng sắp xếp bằng Selection Sort đệ quy: 0 1 3 3 5 5 9