# Quicksort using stack

Here given code implementation process.

``````import java.util.Stack;
/*
Java program for
Quicksort using stack
*/
class Boundary
{
public int s;
public int e;
public Boundary(int s, int e)
{
this.s = s;
this.e = e;
}
}
public class Sorting
{
// Swap the array element
public void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public int partition(int[] arr, int low, int high)
{
// Set the high index element to its proper sorted position
int pv = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j)
{
if (arr[j] < pv)
{
i++;
swap(arr, i, j);
}
}
// set the high index value to its sorted position
swap(arr, i + 1, high);
// returns the next sorting  element location
return i + 1;
}
public void quickSort(int[] arr, int n)
{
Stack < Boundary > record = new Stack < Boundary > ();
int s = 0;
int e = n - 1;
// Add first boundary location of given array
record.push(new Boundary(s, e));

while (record.isEmpty() == false)
{
s = record.peek().s;
e = record.peek().e;
// Remove the top element of stack
record.pop();

// Get pivot and arrange elements
int pv = partition(arr, s, e);

if (pv - 1 > s)
{
// Add the subarray of boundary position
// from s to pv-1
record.push(new Boundary(s, pv - 1));
}
if (pv + 1 < e)
{
// Add the subarray of boundary position
// from pv + 1 to e
record.push(new Boundary(pv + 1, e));
}
}
}
//Display array elements
public void displayArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print("  " + arr[i]);
}
System.out.print("\n");
}
public static void main(String[] args)
{
int[] arr = {
3 , 7 , 1 , -2 , 5 , 7 , 6 , 2 , 1 , 6 , 6 , 2 , 9 , 8
};
// Get the number of elements in array
int n = arr.length;
}
}``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9``````
``````// Include header file
#include <iostream>
#include <stack>
using namespace std;
/*
C++ program for
Quicksort using stack
*/
class Boundary
{
public:
int s;
int e;
Boundary(int s, int e)
{
this->s = s;
this->e = e;
}
};
class Sorting
{
public:
// Swap the array element
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int partition(int arr[], int low, int high)
{
// Set the high index element to its proper sorted position
int pv = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j)
{
if (arr[j] < pv)
{
i++;
this->swap(arr, i, j);
}
}
// set the high index value to its sorted position
this->swap(arr, i + 1, high);
// returns the next sorting  element location
return i + 1;
}
void quickSort(int arr[], int n)
{
stack < Boundary *> record;
int s = 0;
int e = n - 1;
// Add first boundary location of given array
record.push(new Boundary(s, e));
while (record.empty() == false)
{
s = record.top()->s;
e = record.top()->e;
// Remove the top element of stack
record.pop();
// Get pivot and arrange elements
int pv = this->partition(arr, s, e);
if (pv - 1 > s)
{
// Add the subarray of boundary position
// from s to pv-1
record.push(new Boundary(s, pv - 1));
}
if (pv + 1 < e)
{
// Add the subarray of boundary position
// from pv + 1 to e
record.push(new Boundary(pv + 1, e));
}
}
}
//Display array elements
void displayArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << "  " << arr[i];
}
cout << "\n";
}
};
int main()
{
int arr[] = {
3 , 7 , 1 , -2 , 5 , 7 , 6 , 2 , 1 , 6 , 6 , 2 , 9 , 8
};
// Get the number of elements in array
int n = sizeof(arr) / sizeof(arr[0]);
return 0;
}``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program for
Quicksort using stack
*/
public class Boundary
{
public int s;
public int e;
public Boundary(int s, int e)
{
this.s = s;
this.e = e;
}
}
public class Sorting
{
// Swap the array element
public void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public int partition(int[] arr, int low, int high)
{
// Set the high index element to its proper sorted position
int pv = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j)
{
if (arr[j] < pv)
{
i++;
this.swap(arr, i, j);
}
}
// set the high index value to its sorted position
this.swap(arr, i + 1, high);
// returns the next sorting  element location
return i + 1;
}
public void quickSort(int[] arr, int n)
{
Stack < Boundary > record = new Stack < Boundary > ();
int s = 0;
int e = n - 1;
// Add first boundary location of given array
record.Push(new Boundary(s, e));
while ((record.Count == 0) == false)
{
s = record.Peek().s;
e = record.Peek().e;
// Remove the top element of stack
record.Pop();
// Get pivot and arrange elements
int pv = this.partition(arr, s, e);
if (pv - 1 > s)
{
// Add the subarray of boundary position
// from s to pv-1
record.Push(new Boundary(s, pv - 1));
}
if (pv + 1 < e)
{
// Add the subarray of boundary position
// from pv + 1 to e
record.Push(new Boundary(pv + 1, e));
}
}
}
//Display array elements
public void displayArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write("  " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args)
{
int[] arr = {
3 , 7 , 1 , -2 , 5 , 7 , 6 , 2 , 1 , 6 , 6 , 2 , 9 , 8
};
// Get the number of elements in array
int n = arr.Length;
}
}``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9``````
``````<?php
/*
Php program for
Quicksort using stack
*/
class Boundary
{
public \$s;
public \$e;
public	function __construct(\$s, \$e)
{
\$this->s = \$s;
\$this->e = \$e;
}
}
class Sorting
{
// Swap the array element
public	function swap(&\$arr, \$i, \$j)
{
\$temp = \$arr[\$i];
\$arr[\$i] = \$arr[\$j];
\$arr[\$j] = \$temp;
}
public	function partition(&\$arr, \$low, \$high)
{
// Set the high index element to its proper sorted position
\$pv = \$arr[\$high];
\$i = \$low - 1;
for (\$j = \$low; \$j < \$high; ++\$j)
{
if (\$arr[\$j] < \$pv)
{
\$i++;
\$this->swap(\$arr, \$i, \$j);
}
}
// set the high index value to its sorted position
\$this->swap(\$arr, \$i + 1, \$high);
// returns the next sorting  element location
return \$i + 1;
}
public	function quickSort(&\$arr, \$n)
{
\$record = array();
\$s = 0;
\$e = \$n - 1;
// Add first boundary location of given array
array_push(\$record, new Boundary(\$s, \$e));
while (empty(\$record) == false)
{
\$s = end(\$record)->s;
\$e = end(\$record)->e;
// Remove the top element of stack
array_pop(\$record);
// Get pivot and arrange elements
\$pv = \$this->partition(\$arr, \$s, \$e);
if (\$pv - 1 > \$s)
{
// Add the subarray of boundary position
// from s to pv-1
array_push(\$record, new Boundary(\$s, \$pv - 1));
}
if (\$pv + 1 < \$e)
{
// Add the subarray of boundary position
// from pv + 1 to e
array_push(\$record, new Boundary(\$pv + 1, \$e));
}
}
}
//Display array elements
public	function displayArray(\$arr, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
echo("  ".\$arr[\$i]);
}
echo("\n");
}
}

function main()
{
\$arr = array(3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8);
// Get the number of elements in array
\$n = count(\$arr);
}
main();``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9``````
``````package main
import "fmt"
/*
Go program for
Quicksort using stack
*/
type Boundary struct {
s int
e int
}
func getBoundary(s int, e int) * Boundary {
var me *Boundary = &Boundary {}
me.s = s
me.e = e
return me
}
type Sorting struct {}
func getSorting() * Sorting {
var me *Sorting = &Sorting {}
return me
}
// Swap the array element
func(this *Sorting) swap(arr[] int, i int, j int) {
var temp int = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
func(this *Sorting) partition(arr[] int, low int, high int) int {
// Set the high index element to its proper sorted position
var pv int = arr[high]
var i int = low - 1
for j := low ; j < high ; j++ {
if arr[j] < pv {
i++
this.swap(arr, i, j)
}
}
// set the high index value to its sorted position
this.swap(arr, i + 1, high)
// returns the next sorting  element location
return i + 1
}
func(this *Sorting) quickSort(arr[] int, n int) {
var record = make([] *Boundary,0)
var s int = 0
var e int = n - 1
// Add first boundary location of given array
record = append(record, getBoundary(s, e))
for (len(record) > 0) {
s = record[len(record) - 1].s
e = record[len(record) - 1].e
// Remove the top element of stack
record = record[: len(record) - 1]
// Get pivot and arrange elements
var pv int = this.partition(arr, s, e)
if pv - 1 > s {
// Add the subarray of boundary position
// from s to pv-1
record = append(record, getBoundary(s, pv - 1))
}
if pv + 1 < e {
// Add the subarray of boundary position
// from pv + 1 to e
record = append(record, getBoundary(pv + 1, e))
}
}
}
//Display array elements
func(this Sorting) displayArray(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print("  ", arr[i])
}
fmt.Print("\n")
}
func main() {
var task * Sorting = getSorting()
var arr = [] int {3 , 7 , 1 , -2 , 5 , 7 , 6 , 2 , 1 , 6 , 6 , 2 , 9 , 8}
// Get the number of elements in array
var n int = len(arr)
}``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9``````
``````/*
Node JS program for
Quicksort using stack
*/
class Boundary
{
constructor(s, e)
{
this.s = s;
this.e = e;
}
}
class Sorting
{
// Swap the array element
swap(arr, i, j)
{
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
partition(arr, low, high)
{
// Set the high index element to its proper sorted position
var pv = arr[high];
var i = low - 1;
for (var j = low; j < high; ++j)
{
if (arr[j] < pv)
{
i++;
this.swap(arr, i, j);
}
}
// set the high index value to its sorted position
this.swap(arr, i + 1, high);
// returns the next sorting  element location
return i + 1;
}
quickSort(arr, n)
{
var record = [];
var s = 0;
var e = n - 1;
// Add first boundary location of given array
record.push(new Boundary(s, e));
while ((record.length != 0))
{
s = record[record.length - 1].s;
e = record[record.length - 1].e;
// Remove the top element of stack
record.pop();
// Get pivot and arrange elements
var pv = this.partition(arr, s, e);
if (pv - 1 > s)
{
// Add the subarray of boundary position
// from s to pv-1
record.push(new Boundary(s, pv - 1));
}
if (pv + 1 < e)
{
// Add the subarray of boundary position
// from pv + 1 to e
record.push(new Boundary(pv + 1, e));
}
}
}
//Display array elements
displayArray(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write("  " + arr[i]);
}
process.stdout.write("\n");
}
}

function main()
{
var arr = [3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8];
// Get the number of elements in array
var n = arr.length;
}
main();``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9``````
``````#    Python 3 program for
#    Quicksort using stack
class Boundary :
def __init__(self, s, e) :
self.s = s
self.e = e

class Sorting :
#  Swap the array element
def swap(self, arr, i, j) :
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp

def partition(self, arr, low, high) :
#  Set the high index element to its proper sorted position
pv = arr[high]
i = low - 1
j = low
while (j < high) :
if (arr[j] < pv) :
i += 1
self.swap(arr, i, j)

j += 1

#  set the high index value to its sorted position
self.swap(arr, i + 1, high)
#  returns the next sorting  element location
return i + 1

def quickSort(self, arr, n) :
record = []
s = 0
e = n - 1
#  Add first boundary location of given list
record.append(Boundary(s, e))
while ((len(record) != 0)) :
s = record[-1].s
e = record[-1].e
#  Remove the top element of stack
record.pop()
#  Get pivot and arrange elements
pv = self.partition(arr, s, e)
if (pv - 1 > s) :
#  Add the sublist of boundary position
#  from s to pv-1
record.append(Boundary(s, pv - 1))

if (pv + 1 < e) :
#  Add the sublist of boundary position
#  from pv + 1 to e
record.append(Boundary(pv + 1, e))

# Display list elements
def displayArray(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1

print(end = "\n")

def main() :
arr = [3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8]
#  Get the number of elements in list
n = len(arr)

if __name__ == "__main__": main()``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9``````
``````#    Ruby program for
#    Quicksort using stack
class Boundary
# Define the accessor and reader of class Boundary
attr_accessor :s, :e
def initialize(s, e)
self.s = s
self.e = e
end

end

class Sorting
#  Swap the array element
def swap(arr, i, j)
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
end

def partition(arr, low, high)
#  Set the high index element to its proper sorted position
pv = arr[high]
i = low - 1
j = low
while (j < high)
if (arr[j] < pv)
i += 1
self.swap(arr, i, j)
end

j += 1
end

#  set the high index value to its sorted position
self.swap(arr, i + 1, high)
#  returns the next sorting  element location
return i + 1
end

def quickSort(arr, n)
record = []
s = 0
e = n - 1
#  Add first boundary location of given array
record.push(Boundary.new(s, e))
while ((record.length == 0) == false)
s = record.last.s
e = record.last.e
#  Remove the top element of stack
record.pop()
#  Get pivot and arrange elements
pv = self.partition(arr, s, e)
if (pv - 1 > s)
#  Add the subarray of boundary position
#  from s to pv-1
record.push(Boundary.new(s, pv - 1))
end

if (pv + 1 < e)
#  Add the subarray of boundary position
#  from pv + 1 to e
record.push(Boundary.new(pv + 1, e))
end

end

end

# Display array elements
def displayArray(arr, n)
i = 0
while (i < n)
print("  ", arr[i])
i += 1
end

print("\n")
end

end

def main()
arr = [3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8]
#  Get the number of elements in array
n = arr.length
end

main()``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9
``````
``````import scala.collection.mutable._;
/*
Scala program for
Quicksort using stack
*/
class Boundary(var s: Int,var e: Int);
class Sorting()
{
// Swap the array element
def swap(arr: Array[Int], i: Int, j: Int): Unit = {
var temp: Int = arr(i);
arr(i) = arr(j);
arr(j) = temp;
}
def partition(arr: Array[Int], low: Int, high: Int): Int = {
// Set the high index element to its proper sorted position
var pv: Int = arr(high);
var i: Int = low - 1;
var j: Int = low;
while (j < high)
{
if (arr(j) < pv)
{
i += 1;
swap(arr, i, j);
}
j += 1;
}
// set the high index value to its sorted position
swap(arr, i + 1, high);
// returns the next sorting  element location
return i + 1;
}
def quickSort(arr: Array[Int], n: Int): Unit = {
var record: Stack[Boundary] = new Stack[Boundary]();
var s: Int = 0;
var e: Int = n - 1;
// Add first boundary location of given array
record.push(new Boundary(s, e));
while (record.isEmpty == false)
{
s = record.top.s;
e = record.top.e;
// Remove the top element of stack
record.pop;
// Get pivot and arrange elements
var pv: Int = partition(arr, s, e);
if (pv - 1 > s)
{
// Add the subarray of boundary position
// from s to pv-1
record.push(new Boundary(s, pv - 1));
}
if (pv + 1 < e)
{
// Add the subarray of boundary position
// from pv + 1 to e
record.push(new Boundary(pv + 1, e));
}
}
}
//Display array elements
def displayArray(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print("  " + arr(i));
i += 1;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Sorting = new Sorting();
var arr: Array[Int] = Array(
3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8
);
// Get the number of elements in array
var n: Int = arr.length;
}
}``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9``````
``````import Foundation;
/*
Swift 4 program for
Quicksort using stack
*/
class Boundary
{
var s: Int;
var e: Int;
init(_ s: Int, _ e: Int)
{
self.s = s;
self.e = e;
}
}
struct Stack
{
private
var items: [Boundary] = []
func peek()->Boundary
{
if (self.isEmpty()==false)
{
return items.first!
}
else
{
fatalError("This stack is empty.")
}
}
func isEmpty()->Bool
{
return items.count == 0
}
mutating func pop()->Boundary
{
return items.removeFirst()
}
mutating func push(_ data: Boundary)
{
items.insert(data, at: 0)
}
}
class Sorting
{
// Swap the array element
func swap(_ arr: inout[Int], _ i: Int, _ j: Int)
{
let temp: Int = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
func partition(_ arr: inout[Int], _ low: Int, _ high: Int) -> Int
{
// Set the high index element to its proper sorted position
let pv: Int = arr[high];
var i: Int = low - 1;
var j: Int = low;
while (j < high)
{
if (arr[j] < pv)
{
i += 1;
self.swap(&arr, i, j);
}
j += 1;
}
// set the high index value to its sorted position
self.swap(&arr, i + 1, high);
// returns the next sorting  element location
return i + 1;
}
func quickSort(_ arr: inout[Int], _ n: Int)
{
var record = Stack();
var s: Int = 0;
var e: Int = n - 1;
// Add first boundary location of given array
record.push(Boundary(s, e));
while (record.isEmpty() == false)
{
s = record.peek().s;
e = record.peek().e;
// Remove the top element of stack
let _ = record.pop();
// Get pivot and arrange elements
let pv: Int = self.partition(&arr, s, e);
if (pv - 1 > s)
{
// Add the subarray of boundary position
// from s to pv-1
record.push(Boundary(s, pv - 1));
}
if (pv + 1 < e)
{
// Add the subarray of boundary position
// from pv + 1 to e
record.push(Boundary(pv + 1, e));
}
}
}
//Display array elements
func displayArray(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
}
func main()
{
var arr: [Int] = [3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8];
// Get the number of elements in array
let n: Int = arr.count;
}
main();``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9``````
``````import java.util.Stack;
/*
Kotlin program for
Quicksort using stack
*/
class Boundary
{
var s: Int;
var e: Int;
constructor(s: Int, e: Int)
{
this.s = s;
this.e = e;
}
}
class Sorting
{
// Swap the array element
fun swap(arr: Array < Int > , i: Int, j: Int): Unit
{
val temp: Int = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
fun partition(arr: Array < Int > , low: Int, high: Int): Int
{
// Set the high index element to its proper sorted position
val pv: Int = arr[high];
var i: Int = low - 1;
var j: Int = low;
while (j < high)
{
if (arr[j] < pv)
{
i += 1;
this.swap(arr, i, j);
}
j += 1;
}
// set the high index value to its sorted position
this.swap(arr, i + 1, high);
// returns the next sorting  element location
return i + 1;
}
fun quickSort(arr: Array < Int > , n: Int): Unit
{
var record = Stack < Boundary > ();
var s: Int = 0;
var e: Int = n - 1;
// Add first boundary location of given array
record.push(Boundary(s, e));
while (record.empty() == false)
{
s = record.peek().s;
e = record.peek().e;
// Remove the top element of stack
record.pop();
// Get pivot and arrange elements
val pv: Int = this.partition(arr, s, e);
if (pv - 1 > s)
{
// Add the subarray of boundary position
// from s to pv-1
record.push(Boundary(s, pv - 1));
}
if (pv + 1 < e)
{
// Add the subarray of boundary position
// from pv + 1 to e
record.push(Boundary(pv + 1, e));
}
}
}
//Display array elements
fun displayArray(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print("  " + arr[i]);
i += 1;
}
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
var arr: Array < Int > = arrayOf(
3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8
);
// Get the number of elements in array
val n: Int = arr.count();
}``````

#### Output

``````  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
-2  1  1  2  2  3  5  6  6  6  7  7  8  9``````

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.