Day 7 of 100 Days of DSA Challenge: Sorting with Recursion

Greetings fellow coding enthusiasts! Today marked a thrilling journey as I explored the world of sorting algorithms—Selection Sort and Insertion Sort—utilizing the power of recursion. Let's dive into the code and unravel the magic of sorting through recursion.

1. Selection Sort using Recursion

The objective was to implement the Selection Sort algorithm using recursion. The code snippet I worked on looks like this:

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

void Selection_sort(int arr[], int size, int i) {
    if (size == 0 || size == 1 || i > size - 1) {
        return;
    }

    int min_indx = i;
    for (int j = i + 1; j <= size - 1; j++) {
        if (arr[j] < arr[min_indx]) {
            min_indx = j;
        }
    }
    if (min_indx != i) {
        swap(arr[min_indx], arr[i]);
    }
    Selection_sort(arr, size, i + 1);
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int size = sizeof(arr) / sizeof(int);
    Selection_sort(arr, size, 0);
    for (auto it : arr) {
        cout << it << " ";
    }
}

In this code, I utilized the idea of recursion to perform the Selection Sort algorithm. The function repeatedly finds the minimum element from the unsorted part of the array and places it at the beginning, gradually reducing the unsorted portion of the array.

2. Insertion Sort using Recursion

Next, I implemented the Insertion Sort algorithm using recursion. Here's the code snippet for that:

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

void Insertion_sort(int arr[], int size) {
    if (size <= 1) {
        return;
    }
    Insertion_sort(arr, size - 1);
    int end = arr[size - 1];
    int j = size - 2;
    while (j >= 0 && arr[j] > end) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = end;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int size = sizeof(arr) / sizeof(int);
    Insertion_sort(arr, size);
    for (auto it : arr) {
        cout << it << " ";
    }
}

This code employs recursion to perform the Insertion Sort algorithm. It sorts an array by shifting elements one by one and inserting the current element at its correct position.

These algorithms showcase the beauty and elegance of recursion in sorting arrays, demonstrating the efficiency and simplicity of implementing sorting techniques through recursive approaches.

The journey into recursive sorting algorithms has been exhilarating, unlocking new perspectives in problem-solving using recursion. Stay tuned for more exciting updates in the upcoming days as I continue to explore the world of Data Structures and Algorithms!

Keep Coding! ✨🚀