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
- Create a class called
Sorting
. - Define a function called
swap
that takes an arrayarr
and two indicesi
andj
as input and swaps the elements at positionsi
andj
in the array. - Define a function called
partition
that takes an arrayarr
, a low indexlow
, and a high indexhigh
as input and performs the partitioning step of the Quicksort algorithm. Choose the pivot as the last element of the array. Initialize a variablei
tolow - 1
. a. Iterate through the elements fromlow
tohigh - 1
using a loop with indexj
. b. If the element atarr[j]
is less than the pivot, incrementi
and swap the elements at positionsi
andj
. c. After the loop, swap the pivot element with the element at positioni + 1
. d. Return the indexi + 1
. - Define a function called
quickSort
that takes an arrayarr
and its sizen
as input and implements the Quicksort algorithm using a stack. a. Create an empty stack calledrecord
to store the boundaries of sub-arrays. b. Push the initial boundary(0, n - 1)
onto the stack. c. While the stackrecord
is not empty, do the following:- Pop the top boundary
(s, e)
from the stack. - Call the
partition
function witharr
,s
, ande
as arguments to find the pivot indexpv
. - 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.
- Pop the top boundary
- In the
main
function, create an instance of theSorting
class. - Define an array
arr
with the test elements to be sorted. - Get the number of elements in the array
n
. - Display the array
arr
before sorting using thedisplayArray
function. - Call the
quickSort
function to sort the array. - Display the array
arr
after sorting using thedisplayArray
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.
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.
New Comment