Recursion, Recursion, Recursion, ...

Day 8 of the 100-Day DSA challenge. I know you guys are tired of hearing this same word over the last few days, but it's exciting too, don't you agree. I hope you are also enjoying and are continuing with my journey. Today again we'll be talking about recursion and solving two more types of sorting with the help of recursion.

Selection Sort = In this type of sorting, we assume the first member of the data structure to be the minimum element and then start comparing it with other elements of that particular data structure till we find the next smaller element than the current element. Repeating this we can sort our data structure with the help of selection sort.

#include<bits/stdc++.h>
using namespace std;

void SelectionSort(int arr[], int start, int size){
    if(start >= size){
        return;
    }
        int min_pos = start;
        for(int i = start; i < size-1; i++){
            if(arr[i] < arr[min_pos]){
                min_pos = i;
            }
        }

        swap(arr[min_pos], arr[start]);

        SelectionSort(arr, start+1, size);
}

int main(){
    int n;
    cout << "Enter the size of array : ";
    cin >> n;

    int arr[n];
    cout << "Enter the elements of array : ";
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    SelectionSort(arr, 0, n);

    cout << "Array after sorting...\n";
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    return 0;
}

• Insertion Sort = In this type of sorting, we assume the first element of the data structure as the sorted member and start comparing this element with the other data members of that particular data structure and repeating this step we arrange the elements at their specific position.

    #include<bits/stdc++.h>
    using namespace std;
  
    void InsertionSort(int arr[], int start, int size){
        if(start >= size){
            return;
        }
  
        int index = start;
        for (int i = 0; i < size; i++)
        {
            if (arr[index] < arr[i])
            {
                swap(arr[index], arr[i]);
            }
  
        }
  
        InsertionSort(arr, start+1, size);
    }
  
    int main(){
        int n;
        cout << "Enter the size of array : ";
        cin >> n;
  
        int arr[n];
        cout << "Enter the elements of array : ";
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
        }
  
        InsertionSort(arr, 0, n);
  
        cout << "Array after sorting...\n";
        for (int i = 0; i < n; i++)
        {
            cout << arr[i] << " ";
        }
        return 0;
    }