Posted on by Kalkicode
Code Stack

# 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.

## 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.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post