WikiGalaxy

Personalize

Recursion in Sorting Algorithms

Understanding Recursion in Sorting

Introduction to Recursion:

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. It is widely used in sorting algorithms to break down complex problems into simpler sub-problems.

Common Recursive Sorting Algorithms:

Some of the most common recursive sorting algorithms include Quick Sort, Merge Sort, and Heap Sort.

        Step 1: Divide the array into sub-arrays.
        Step 2: Recursively sort the sub-arrays.
        Step 3: Merge the sorted sub-arrays to produce the final sorted array.

Example 1: Quick Sort

Quick Sort Overview:

Quick Sort is a divide-and-conquer algorithm that selects a 'pivot' element and partitions the array around the pivot, recursively sorting the partitions.

        Step 1: Choose a pivot element from the array.
        Step 2: Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
        Step 3: Recursively apply the above steps to the sub-arrays.


public class QuickSort {
    int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    void sort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }

    public static void main(String args[]) {
        int arr[] = {10, 7, 8, 9, 1, 5};
        int n = arr.length;
        QuickSort ob = new QuickSort();
        ob.sort(arr, 0, n - 1);
        System.out.println("Sorted array: ");
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
    }
}

Example 2: Merge Sort

Merge Sort Overview:

Merge Sort is a stable, divide-and-conquer algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves.

        Step 1: Divide the unsorted list into n sublists, each containing one element.
        Step 2: Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining.


public class MergeSort {
    void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[n2];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    void sort(int arr[], int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: ");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
    }
}

Example 3: Heap Sort

Heap Sort Overview:

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It involves building a heap from the input data and then repeatedly removing the largest element from the heap.

        Step 1: Build a max heap from the input data.
        Step 2: Swap the root of the heap with the last element of the heap.
        Step 3: Reduce the heap size by one and heapify the root.
        Step 4: Repeat the process until the heap is reduced to one element.


public class HeapSort {
    public void sort(int arr[]) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    void heapify(int arr[], int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < n && arr[l] > arr[largest])
            largest = l;
        if (r < n && arr[r] > arr[largest])
            largest = r;
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }

    public static void main(String args[]) {
        int arr[] = {4, 10, 3, 5, 1};
        HeapSort ob = new HeapSort();
        ob.sort(arr);
        System.out.println("Sorted array: ");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

Example 4: Recursive Insertion Sort

Insertion Sort Overview:

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

        Step 1: If the array has only one element, it is already sorted.
        Step 2: Recursively sort the sub-array with one less element.
        Step 3: Insert the last element into the sorted sub-array.


public class RecursiveInsertionSort {
    static void insertionSortRecursive(int arr[], int n) {
        if (n <= 1)
            return;
        insertionSortRecursive(arr, n - 1);
        int last = arr[n - 1];
        int j = n - 2;
        while (j >= 0 && arr[j] > last) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = last;
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6};
        insertionSortRecursive(arr, arr.length);
        System.out.println("Sorted array: ");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

Example 5: Recursive Bubble Sort

Bubble Sort Overview:

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

        Step 1: Traverse the array from start to end.
        Step 2: If the current element is greater than the next element, swap them.
        Step 3: Recursively call the function for the rest of the array.


public class RecursiveBubbleSort {
    static void bubbleSort(int arr[], int n) {
        if (n == 1)
            return;
        for (int i = 0; i < n - 1; i++)
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        bubbleSort(arr, n - 1);
    }

    public static void main(String args[]) {
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr, arr.length);
        System.out.println("Sorted array: ");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

Example 6: Recursive Selection Sort

Selection Sort Overview:

Selection Sort is an in-place comparison sorting algorithm that divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items.

        Step 1: Find the minimum element in the unsorted array.
        Step 2: Swap it with the element at the beginning.
        Step 3: Recursively call the function for the rest of the array.


public class RecursiveSelectionSort {
    static void selectionSort(int arr[], int n, int index) {
        if (index == n)
            return;
        int minIndex = index;
        for (int i = index + 1; i < n; i++)
            if (arr[i] < arr[minIndex])
                minIndex = i;
        int temp = arr[minIndex];
        arr[minIndex] = arr[index];
        arr[index] = temp;
        selectionSort(arr, n, index + 1);
    }

    public static void main(String args[]) {
        int arr[] = {64, 25, 12, 22, 11};
        selectionSort(arr, arr.length, 0);
        System.out.println("Sorted array: ");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

Example 7: Recursive Shell Sort

Shell Sort Overview:

Shell Sort is a generalization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, taking every hth element produces a sorted list.

        Step 1: Start with a large gap and reduce the gap until it becomes 1.
        Step 2: Perform a gapped insertion sort for the current gap size.
        Step 3: Recursively sort the sub-arrays created by the gaps.


public class RecursiveShellSort {
    static void shellSort(int arr[], int n, int gap) {
        if (gap == 0)
            return;
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
        shellSort(arr, n, gap / 2);
    }

    public static void main(String args[]) {
        int arr[] = {12, 34, 54, 2, 3};
        int n = arr.length;
        shellSort(arr, n, n / 2);
        System.out.println("Sorted array: ");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}

Example 8: Recursive Radix Sort

Radix Sort Overview:

Radix Sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.

        Step 1: Find the maximum number to know the number of digits.
        Step 2: Do counting sort for every digit. The digit is extracted using division and modulus operations.
        Step 3: Recursively sort the array based on the digits.


public class RecursiveRadixSort {
    static int getMax(int arr[], int n) {
        int mx = arr[0];
        for (int i = 1; i < n; i++)
            if (arr[i] > mx)
                mx = arr[i];
        return mx;
    }

    static void countSort(int arr[], int n, int exp) {
        int output[] = new int[n];
        int count[] = new int[10];
        for (int i = 0; i < n; i++)
            count[(arr[i] / exp) % 10]++;
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        for (int i = 0; i < n; i++)
            arr[i] = output[i];
    }

    static void radixSort(int arr[], int n) {
        int m = getMax(arr, n);
        for (int exp = 1; m / exp > 0; exp *= 10)
            countSort(arr, n, exp);
    }

    public static void main(String args[]) {
        int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
        int n = arr.length;
        radixSort(arr, n);
        System.out.println("Sorted array: ");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}