Selection Sort Recursive Algorithm O(N^2)

selection_sort_rec.cpp

#include <iostream>
#include <vector>
#include <algorithm>    // for swap()
#include <climits>      // for INT_MIN
using namespace std;

void select_sort_rec(vector<int> &ar, vector<int> &swaps_eles, int n, int max_ele = INT_MIN, int max_idx = -1) {
    // Base Case
    if(n == 1) return;
    
    for(int j = 0; j < n; ++j) 
        if(max_ele < ar[j]) {
            max_ele = ar[j];
            max_idx = j;
        }
    swap(ar[max_idx], ar[n-1]);
    
    swaps_eles.push_back(max_idx);
    select_sort_rec(ar, swaps_eles, n-1);
}

int main() {
    int t;  cin >> t;
    while(t--) {
        int n;  cin >> n;
        
        vector<int> ar(n);
        for(int i = 0; i < n; ++i)
            cin >> ar[i];
        
        vector<int> swaps_eles;
        select_sort_rec(ar, swaps_eles, ar.size());
        // for(auto x: ar) cout << x << " ";   // sorted array
        for(auto x: swaps_eles) cout << x << " ";   // the indices where the swaps occured
        cout << "\n";
    }
    return 0;
}