If you have completed your basic Computer Science Chapter, you are going to face the Data Structures & Algorithm in the upcoming phase. In that particular topic, you are going to familiarize yourself with the “Sorting Algorithms with Recursive Function”.
Sorting Algorithms are the main pillar by which you can sort all the elements of any Unsorted Array & convert it to a Sorted Array. When the complete process can be done with a Recursive Function Call, the complete process takes a new look.
This article is intended to focus on the Sorting Algorithms that can be completed with Recursive Calls. So, let us start our discussion.
Summary or Key Highlights:
Recursion is the simple process where a function calls itself to reduce the work on any code.
When the Recursion process is used to make any array in the sorted form, the process is known as the Recursive Sorted Algo.
All the Sorting Methods don’t follow the Recursive Way to get the result.
Only the Merge Sort, Quick Sort & Bubble Sort follow the recursion method.
Before working on the Recursive Sort Method, the Function Call Process should be cleared.
What Is Recursive Function In Sorting Algorithms?
Now, the Sorting Algorithm & Function Recursive Call are two completely different things. You can understand the Sorting Algorithm as the process where some unsorted random numbers are converted into a Sorted Array with the least operation made.
The Recursion works well to make a Simple Sorting Algorithm. When any function calls the same function, the process is known as the Recursion. The process is known as the Recursive Approach. The main objective of Recursive Implementation is to make a complex problem a simple one.
The Recursion divides a difficult problem into smaller problems & solves them first. When any Ending Condition in Recursion is satisfied, the Recursion gets terminated. You are going to understand Recursively Sort further when we implement it on Efficient Sorting Algorithms to get a Sorted Array.
Which Sorting Algorithms Are Recursive?
Before moving ahead, you have to take note that All The Sorting Algorithms Not Use The Recursion Method. There are five highly important Sort Algorithms present some use search techniques like Binary Search as the main operation.
The list of different Sort Algorithms is the following.
Merge Sort
Quick Sort
Bubble Sort
Selection Sort
Insertion Sort
Among all of these, the Insertion Sort & Selection sort doesn’t follow the Recursive Order. All other Sorting Algorithms follow the Recursive Manner. Along with them, we can implement Iterative Bubble Sort along with Recursion Bubble Sort.
So, let us start with the Merge Sort, Quick Sort & Bubble Sort leaving behind the Insertion Sort & Selection Sort as they don’t use Recursion.
How To Implement Common Recursive Algorithms To Get Sorted Array?
At this point, we are going to discuss each Sort Algorithm one by one along with its implementation in different programming languages. Some Code will be implemented in Java Language & some will be in the C++ Language.
Not only the implementation of codes, rather we will also discuss the Theory of Each Algorithm that will clarify the concept in a better way. So, let us get a push on the Merge Sort Concept first.
How To Implement Merge Sort Using Recursion?
First, we are going to discuss the Merge Sort Algorithm Concept. The Merge Sort Technique Divide And Conquer Algorithm. That means a large dataset will be divided into smaller parts.
And in the smaller parts, the Adjacent Elements will be sorted. Lastly, all the values will be placed in the correct position.
Let us have an example of the concept!
Suppose, we have taken an array with a natural number as the {4,3,2,1}. This given array needs to be sorted in the right order. So, the array will be divided into two parts. In one part, there will be {4,3} & in another part, there will be {2,1}.
Now, it can be further divided into smaller parts or the swapping of elements to the correct position can be done there. When the stopping point is reached, all the small elements of two halves or more will be added to get the correct sorted order of the natural number.
Java Code To Demonstrate Merge Sort With Recursive Technique:
public class Main {
public static void mg(int[] arr, int l, int m, int r) { // Method To Merge Two Sorted Subarrays
int n1 = m - l + 1; // Size Of The Left Subarray
int n2 = r - m; // Size Of The Right Subarray
// Creating Temporary Arrays
int[] left = new int[n1];
int[] right = new int[n2];
for (int i = 0; i < n1; i++) {
left[i] = arr[l + i];
}
for (int i = 0; i < n2; i++) {
right[i] = arr[m + 1 + i];
}
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) { // Merging Arrays
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < n1) { // Copy Any Remaining Left Elements
arr[k] = left[i];
i++;
k++;
}
while (j < n2) { // Copy Any Remaining Right Elements
arr[k] = right[j];
j++;
k++;
}
}
public static void mSort(int[] arr, int l, int r) { // Recursively Method For Merge Sort
if (l < r) { // Base Case Ending Condition
int m = l + (r - l) / 2; // Getting The Middle index
// Recursively Calling Two Parts
mSort(arr, l, m);
mSort(arr, m + 1, r);
mg(arr, l, m, r); // Merging Two Parts
}
}
public static void main(String[] args) {
int[] arr = {37, 25, 42, 2, 8, 79, 12}; // Simple Array As Input
mSort(arr, 0, arr.length - 1); // Sort the array using merge sort
for (int num : arr) { // Printing The Unsorted Array
System.out.print(num + " ");
}
System.out.println(); // Printing New line
}
}
Steps Of The Program:
In the Main Method, the Array of Integers will be taken & the length of the array will be determined.
Now, the Merge Sort Method will be called from the Main Function.
In that Function, we will mark the Middle Point of the Array & break the Array into two parts.
Each Part will be Recursively Called to get the End Point on the execution.
At last, the merge condition will be called to merge different parts in the correct order.
In the Merge Function, a different temporary array will be declared to get the complete new array.
At last, the inner loop of the Main Function will start the first iteration to get each printed data.
Output:
From the above output, we can see that the Merge Algorithm works completely well to change the Wrong Order. The Smallest Element is at the beginning & the largest element is the last element of the current array. So, the example works fine & demonstrates the implementation of Merge Sort in Java.
How To Implement Quick Sort Using Recursion?
Now, it is time to discuss the Quick Sort Algorithm. The Quick Sort is quite different from the Merge Sort. Here, the concept of Pivot Point works. You can choose the last element or first element of the array as the Pivot Point.
Based on the Pivot Point, the comparison of the two elements will be done. All the elements or values less than the Point Value will be kept on the left side. All the values greater than the Pivot Value will be present on the right side.
Also, if you’re interested in knowing about the implementation process of Quick Sort for programming languages like Python, then you can check out our article on Quick Sort in Python.
Let us have an example of the concept!
Suppose, there is an array as the {3,4,1,2}. Now, among every element, the last value Number 2 is taken as the Pivot Value. As the Number 2 is the Pivot Element, the lower values will be kept at the left side. Here, Number 1 is only the Lower Element.
Every higher element will be kept on the Right Side. Here, the Number 3 & Number 4 will be placed in the same order. As these numbers are already sorted, we will join two arrays directly. Now, all the data is put in a sorted manner. Check the following code to get more details.
Java Code To Demonstrate Quick Sort With Recursive Technique:
public class Main {
public static int part(int[] arr, int l, int h) { // Method To Partition The Array
int p = arr[h]; // Choose Element As Pivot
int i = l - 1;
for (int j = l; j < h; j++) { // Loop From low To High-1
if (arr[j] < p) { // If Element Is Smaller
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp; // Swapping The Elements
}
}
// Place The Pivot Correctly
int temp = arr[i + 1];
arr[i + 1] = arr[h];
arr[h] = temp;
return i + 1; // Returning The Index
}
public static void qSort(int[] arr, int l, int h) { // Recursively Method For Quick Sort
if (l < h) { // Base Case End Condition
int p = part(arr, l, h); // Getting The Partition Index
qSort(arr, l, p - 1); // Sort The left Part
qSort(arr, p + 1, h); // Sort The Right Part
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5}; // Simple Array Sample
qSort(arr, 0, arr.length - 1); // Caling The Quick Sort
for (int num : arr) { // Printing The Sorted Array
System.out.print(num + " ");
}
System.out.println(); // Printing New line
}
}
Steps Of The Program:
In the main function, the array is declared with different data in an unsorted manner.
Now, we will call the Quick Sort Function & directly perform all the operations there.
Now, we will find out the Partition Index for the certain array & based on it, we will divide the array into two elements.
The left side will be from the beginning to the pivot data & the right side will be from the Pivot Data to the End Element.
In the Partition Function, the Largest Element will always be considered as the Pivot Data.
A new array will be declared, where all the lower elements will be kept on the left side & all higher elements will kept on the right side.
Once the End Case is achieved, the array will be printed in the main function. For that, we have declared one loop.
Output:
From the above output, we can see that the idea of the Quick Sort Algorithm works completely fine. Here, the largest element is placed at the top right-most side. That is the indication that the Quick Sort Idea was implemented correctly in the Code.
If you encounter any challenges while going through this code and require help with your Java Assignment, you have the option to enlist the services of skilled programmers at CodingZap.
How To Implement Bubble Sort Using Recursion?
Last but not least one is the Bubble Sort Process. The Bubble Sort is the process that can be implemented either by using Recursion or by using an Iterative Manner. Here, we will show the Recursive Manner of Bubble Sort Algorithm in C++ which is also highly popular.
In the Bubble Sort, an imaginary bubble is developed on two adjacent values. Based on those values under the bubble, the minimum one goes to the left side & the maximum one comes to the right side using more than two loops.
Let us have an example of the concept!
Suppose, there is an array with the elements like {20, 10, 40, 30}. Now, a bubble will be developed between 20 & 10. And as the Number 10 will be the minimum the place will be swapped. So, now the array will become like {10, 20, 40, 30}.
Now, again another bubble will be developed on Number 20 & 40. But as Number 20 is the minimum, no swapping will be done. Next, the bubble will be developed on the 40 & 30. Here, the Swapping will happen & the complete array will be sorted.
C++ Code To Demonstrate Bubble Sort With Recursive Technique:
#include <bits/stdc++.h>
using namespace std;
void bSort(int arr[], int n) // Method To Implement Bubble Sort
{
if (n == 1) // Base Case End Condition
return;
for (int i = 0; i < n - 1; i++) // Finding Minimum & Swapping
if (arr[i] > arr[i + 1])
swap(arr[i], arr[i + 1]);
bSort(arr, n - 1);
}
void print(int arr[], int s){ // Function To Print The Array
int i;
for (i = 0; i < s; i++)
cout << arr[i] << " ";
cout << endl;}
int main()
{
int arr[] = { 9, 1, 2, 3, 11}; // Declaration Of The Array
int N = sizeof(arr) / sizeof(arr[0]); // Gettings Size Of Array
bSort(arr, N); // Calling Bubble Sort Function
print(arr, N); // Printing Sorted Array
return 0;
}
Steps Of The Program:
At first in the code, in the Main Function, the Array will be taken with some integers.
Later, we are going to find out the size of the Array to call the Bubble Sort Function.
In the Bubble Sort Function, we will check the lower & higher values using two nested For Loop.
At the end, we will use the Print Method to print the new values in the array.
Output:
From the above output, we can see that the Bubble Sort is efficient in reshuffling the element in any array in a particular sorted manner. You can see that the Minimum value is kept on the Left Side whereas the Maximum value is present on the right side.
Did you face any difficulty understanding the code? Don’t worry, you can get help from reliable C++ programming homework experts and clear all your doubts.
What Are The Time Complexity & Space Complexity For Each Recursive Sorting Algorithm?
Before completely ending the discussion, we want to shed some light on the Space & Time Complexity of each recursively Sorting Algo. With the help of these complexities, you can find out which algorithms are best to work on. Let us discuss the Time Complexity first.
Time Complexity Of Different Recursive Sorting Techniques:
The Merge Sort takes the O(N Log N) as the best complexity time.
The Quick Sort takes the O(N Log N) as the best complexity time.
The Bubble Sort takes the O(N^2) instead of O(N Log N) as the best complexity time.
Space Complexity Of Different Recursive Sorting Techniques:
The Merge Sort takes the O(N) as the best complexity.
The Quick Sort also takes the O(N) as the best complexity.
The Bubble Sort takes the O(1) as the best complexity.
Can I Implement Selection & Insertion Sort Using Recursion?
Generally, the Selection & Insertion Sort is implemented in the Iterative Manner which is the most popular. The Selection & Insertion Sort is developed using iteration because it uses less Time & Space in that case. And for every developer, the main goal is to reduce time.
However, there is no meaning that the Selection & Insertion Sort can’t be even developed in the Recursive Manner. You have to just develop the logic behind it. As the Selection & Insertion Sort doesn’t fall under the recursive method, we are not moving deeper into it.
You can take it as a practice or exercise to develop Selection & Insertion Sort using the Recursive Method. But one thing, we want to again clarify is that the Selection & Insertion Sort in a Recursive manner will increase the Space & Time Consumption of the code.
Conclusion:
In the end, we can say that the “Sorting Algorithms with Recursive Function” are worthful to be noted.
However, we strongly recommend clearing the foundation of Function Calls & Declarations of any programming language. As then only, you can move ahead for the Sorting Methods where the use of Recursion is inevitable. It will help to grasp the concept more easily.
Takeaways:
If any function including the Main Function calls itself, the process is known as the Recursive Way.
Recursion is the key process of any Sorting Method in the Data Structure.
Not all the Sorting Methods are executed with the help of the Recursion as Time Complexity matters.
The Selection and Insertion Sort are those that can’t be generally implemented using Recursion.
The Merge Sort, Quick Sort & Bubble Sort can be implemented using the Recursive method.
The Merge Sort works on a simple Divide-And-Conquer Process.
The Quick Sort works on the development of Pivot Element.
The Bubble Sort defines imaginary bubbles on the elements & sorts them.
Most of the Sorting Methods take O(N Log N) as the best complexity time.
