Sắp xếp lựa chọn đệ quy trong C ++

Selection Sort là một trong những thuật toán sắp xếp được sử dụng để sắp xếp dữ liệu bằng cách lặp lại một mảng từ đầu và thay thế từng phần tử bằng phần tử nhỏ nhất trong danh sách. Khi chúng ta di chuyển về phía trước, mảng bên trái được sắp xếp và mảng bên phải không được sắp xếp. Mỗi bước di chuyển sẽ đặt vị trí nhỏ nhất tiếp theo vào vị trí hiện tại của chỉ mục bằng cách hoán đổi.

Thuật toán sắp xếp lựa chọn

int arr [5] ={5,4,2,1,3};
int i, j;
Chuyển từ chỉ mục i =0 sang i
- Chuyển từ chỉ mục j =i + 1 sang kích thước mảng - 1
- tìm nhỏ nhất và lưu trữ index.pos của nó
Hoán đổi phần tử tại vị trí chỉ mục tìm thấy với arr [i]
Kết thúc

Sắp xếp lựa chọn đệ quy

Tìm chỉ số của phần tử tối thiểu
Nếu chỉ số phần tử nhỏ nhất được tìm thấy bằng kích thước mảng thì trả về.
Nếu không, hoán đổi phần tử hiện tại với phần tử nhỏ nhất
Thực hiện đệ quy các bước trên cho phần còn lại của mảng không bao gồm các phần tử đã sắp xếp

Ví dụ

Đầu vào - Arr [] ={5,7,2,3,1,4}; chiều dài =6

Đầu ra - Mảng đã sắp xếp:1 2 3 4 5 7

Giải thích -

First Pass :-
5 7 2 3 1 4 → swap → 1 2 7 3 5 4
1 2 7 3 5 4 → no swap
1 2 7 3 5 4 → swap → 1 2 3 7 5 4
1 2 3 7 5 4 → swap → 1 2 3 4 5 7
1 2 3 4 5 7 → no swap

Đầ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 → no swap
1 2 3 2 3 → no swap
1 2 3 2 3 → swap → 1 2 2 3 3
1 2 2 3 3 → no swap

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Trong cách tiếp cận đệ quy của sắp xếp Lựa chọn, trường hợp cơ sở là chỉ số tối thiểu =kích thước mảng-1. Nếu không, hãy tìm giá trị tối thiểu từ hoán đổi mảng với chỉ mục hiện tại và sắp xếp đệ quy bên phải mảng chưa được sắp xếp.

Lấy mảng đầu vào Arr [] và độ dài là số phần tử trong đó.
Hàm findMin (int arr [], int i, int j) nhận mảng và các chỉ mục của nó và trả về chỉ số của phần tử tối thiểu giữa arr [i + 1] đến arr [j].
Thực hiện một số minpos có thể thay đổi.
Nếu cả i và j đều giống nhau, thì trả về i là chỉ số của phần tử tối thiểu vì cả hai đều giống nhau.
Nếu không, recursivley tìm kiếm vị trí từ i + 1 đến j bằng cách sử dụng minpos =findMin (arr, i + 1, j).
if (arr [i]
Hàm recurselectSort (int arr1 [], int len1, int pos1) nhận mảng đầu vào và sắp xếp nó theo thứ tự tăng dần bằng cách sử dụng đệ quy trong sắp xếp lựa chọn.
Nếu pos1 ==len1 thì không tìm thấy giá trị tối thiểu nào, sau đó trả về.
Tập hợp khác minpos1 =findMin (arr1, pos1, len1-1)
Nếu chỉ mục pos1 hiện tại và chỉ mục phần tử tối thiểu minpos1 không giống nhau, thì hoán đổi các phần tử trong các chỉ mục này bằng cách sử dụng tạm thời.
Đệ quy cho phần còn lại của mảng bằng recurselectSort (arr1, len1, pos1 + 1).
Khi kết thúc tất cả các lệnh gọi, khi len trở thành 1, chúng ta sẽ thoát ra khỏi đệ quy và mảng sẽ được sắp xếp.
In mảng đã sắp xếp bên trong main.

Ví dụ

#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<<"Sorted Array using recursive Selection sort: "<<endl;
   for (int i = 0; i<length ; i++){
      cout << Arr[i] << " ";
   }
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

Sorted Array using recursive Selection sort:
0 1 3 3 5 5 9