Quicksort using stack

The problem is to implement the Quicksort algorithm using a stack instead of recursion. Quicksort is an efficient sorting algorithm that uses the divide-and-conquer approach to sort an array or list. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays based on whether they are less than or greater than the pivot. The process is then recursively applied to the two sub-arrays until the entire array is sorted.

Problem Statement

Given an array of integers, we need to implement the Quicksort algorithm to sort the array using a stack instead of recursion.

Example

Consider the following example:

Input: [3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8]

Output: [-2, 1, 1, 2, 2, 3, 5, 6, 6, 6, 7, 7, 8, 9]

Idea to Solve the Problem

The Quicksort algorithm can be implemented using a stack to mimic recursion. The idea is to push the initial boundaries (start and end indices) of the array onto the stack. Then, in each iteration, pop the top boundary from the stack and partition the array around a pivot element. After partitioning, push the boundaries of the two sub-arrays (left and right of the pivot) onto the stack. Repeat this process until the stack becomes empty.

Pseudocode

Function swap(arr, i, j):
    // Swap the array elements at positions i and j
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

Function partition(arr, low, high):
    // Choose pivot as the last element of the array
    pivot = arr[high]
    i = low - 1
    for j from low to high - 1:
        if arr[j] < pivot:
            i = i + 1
            swap(arr, i, j)
    swap(arr, i + 1, high)
    return i + 1

Function quickSort(arr, n):
    // Create an empty stack called record
    Create an empty stack record
    push (0, n - 1) onto record

    while record is not empty:
        (s, e) = pop from record
        pv = partition(arr, s, e)
        if pv - 1 > s:
            push (s, pv - 1) onto record
        if pv + 1 < e:
            push (pv + 1, e) onto record

Algorithm

1. Create a class called Sorting.
2. Define a function called swap that takes an array arr and two indices i and j as input and swaps the elements at positions i and j in the array.
3. Define a function called partition that takes an array arr, a low index low, and a high index high as input and performs the partitioning step of the Quicksort algorithm. Choose the pivot as the last element of the array. Initialize a variable i to low - 1. a. Iterate through the elements from low to high - 1 using a loop with index j. b. If the element at arr[j] is less than the pivot, increment i and swap the elements at positions i and j. c. After the loop, swap the pivot element with the element at position i + 1. d. Return the index i + 1.
4. Define a function called quickSort that takes an array arr and its size n as input and implements the Quicksort algorithm using a stack. a. Create an empty stack called record to store the boundaries of sub-arrays. b. Push the initial boundary (0, n - 1) onto the stack. c. While the stack record is not empty, do the following:
   • Pop the top boundary (s, e) from the stack.
   • Call the partition function with arr, s, and e as arguments to find the pivot index pv.
   • If pv - 1 > s, push the boundary (s, pv - 1) onto the stack to sort the left sub-array.
   • If pv + 1 < e, push the boundary (pv + 1, e) onto the stack to sort the right sub-array.
5. In the main function, create an instance of the Sorting class.
6. Define an array arr with the test elements to be sorted.
7. Get the number of elements in the array n.
8. Display the array arr before sorting using the displayArray function.
9. Call the quickSort function to sort the array.
10. Display the array arr after sorting using the displayArray function.

Code Solution

1) Quicksort using stack in c 2) Quicksort using stack in java 3) Quicksort using stack in c++ 4) Quicksort using stack in golang 5) Quicksort using stack in c# 6) Quicksort using stack in vb.net 7) Quicksort using stack in php 8) Quicksort using stack in node js 9) Quicksort using stack in python 10) Quicksort using stack in ruby 11) Quicksort using stack in scala 12) Quicksort using stack in swift 13) Quicksort using stack in kotlin 14) Quicksort using stack in typescript

Time Complexity

The time complexity of the Quicksort algorithm in the worst case is O(n^2), but on average, it is O(n log n). Using a stack for the Quicksort implementation does not change the time complexity, but it eliminates the overhead of recursion, making it more space-efficient.