Sort array using stack
The problem is to sort an array using a stack data structure. The goal is to implement a sorting algorithm that utilizes a stack to sort the array in non-decreasing order.
Problem Statement
Given an array of integers, we need to sort the array using a stack data structure.
Explanation with Suitable Example
Let's consider the following unsorted array:
int arr[] = {6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21};
The goal is to sort this array in non-decreasing order.
Idea to Solve the Problem
The main idea behind sorting an array using a stack is to mimic the process of insertion sort. We can use a stack to store the elements in a partially sorted order. While iterating through the array, we compare the current array element with the top element of the stack. If the array element is greater than or equal to the top of the stack, we push it onto the stack. Otherwise, we pop elements from the stack until we find the right position for the current element and insert it accordingly.
Pseudocode
The following pseudocode outlines the steps to sort an array using a stack:
function sort_array(arr[], size)
if size <= 0, return
create an empty stack
for i from 0 to size-1
if stack is empty or arr[i] >= top of stack
push arr[i] onto the stack
else
initialize temp to arr[i]
initialize j to i
while stack is not empty and top of stack > temp
arr[j] = pop top of stack
decrement j
arr[j] = temp
push arr[j] onto the stack
for i from size-1 to 0
arr[i] = pop top of stack
Algorithm Explanation
- Check if the size of the array is non-positive (size <= 0), if so, return as there is nothing to sort.
- Create an empty stack to store the elements in a partially sorted order.
- Use a loop to iterate through the array from index 0 to size-1.
- If the stack is empty or the current array element is greater than or equal to the top of the stack, push the current array element onto the stack.
- Otherwise, initialize a temporary variable (temp) with the current array element and a variable j with i.
- While the stack is not empty and the top of the stack is greater than the temp value, pop the top of the stack and assign it to arr[j]. Decrement j.
- Finally, assign the temp value to arr[j] and push arr[j] onto the stack.
- Use another loop to iterate through the array from index size-1 to 0.
- Pop the top of the stack and assign it to arr[i].
Code Solution
//C Program
//Sort array using stack
#include <stdio.h>
#include <stdlib.h> //for malloc function
//create structure of stack Node
struct Node
{
int data;
struct Node *next;
};
//insert Stack element
void push(int value, struct Node **top)
{
//Create dynamic node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
node->data = value;
node->next = *top;*top = node;
}
}
//pop Stack element
int pop(struct Node **top)
{
int value = 0;
if ( *top == NULL)
{
printf("Empty Stack\n");
}
else
{
struct Node *temp = *top;
value = temp->data;*top = temp->next;
free(temp);
temp = NULL;
}
return value;
}
//Get value of top element
int peek(struct Node *top)
{
if (top != NULL)
{
return top->data;
}
else
{
return -1;
}
}
//Sort array element by using stack
void sort_array(int arr[], int size)
{
if (size <= 0)
{
return;
}
struct Node *top = NULL;
int temp = 0, j = 0;
for (int i = 0; i < size; ++i)
{
if (top == NULL || peek(top) <= arr[i])
{
//Add array element into stack when stack is empty,
//or array element is greater than equal to top of stack
push(arr[i], & top);
}
else
{
j = i;
temp = arr[j];
//When array element is less than stack top element
//Then insert new element in its proper position
while (top != NULL && peek(top) > temp)
{
//use array space and assign the stack element
//until stack top is not null or its value
//is less than current array element
arr[j] = pop( & top);
j--;
}
//assign current element
arr[j] = temp;
//After that array elements between given index is add to stack
for (j; j <= i; j++)
{
push(arr[j], & top);
}
}
}
//Assign the sorted value in actual array
for (int i = size - 1; i >= 0; --i)
{
arr[i] = pop( & top);
}
}
//Display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
//Define the element of unsorted array
int arr[] = {6,1,0,5,-2,8,2,3,6,-3,62,21};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
display(arr, size);
sort_array(arr, size);
display(arr, size);
return 0;
}
Output
6 1 0 5 -2 8 2 3 6 -3 62 21
-3 -2 0 1 2 3 5 6 6 8 21 62
/*
Java Program
Sort array using stack
*/
//Stack Node
class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
class MyStack
{
public Node top;
public MyStack()
{
top = null;
}
public void display()
{
if (top != null)
{
Node temp = top;
while (temp != null)
{
System.out.print(" " + temp.data);
temp = temp.next;
}
}
System.out.print("\n");
}
//Add a new element in stack
public void push(int data)
{
//Make a new stack node
Node new_node = new Node(data);
if (new_node != null)
{
new_node.next = top;
top = new_node;
}
else
{
System.out.print("Memory overflow\n");
}
}
//Add a top element in stack
//When stack is empty it returns -1
public int pop()
{
int temp = -1;
if (top != null)
{
temp = top.data;
top = top.next;
}
return temp;
}
public boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
public int peek()
{
if (top != null)
{
return top.data;
}
else
{
return -1;
}
}
//Sort array element by using stack
public void sort_array(int[] arr, int size)
{
if (size <= 0)
{
return;
}
int temp = 0, j = 0, k = 0;
for (int i = 0; i < size; ++i)
{
if (this.is_empty() || this.peek() <= arr[i])
{
//Add array element into stack when stack is empty,
//or array element is greater than equal to top of stack
this.push(arr[i]);
}
else
{
j = i;
temp = arr[j];
//When array element is less than stack top element
//Then insert new element in its proper position
while (!this.is_empty() && this.peek() > temp)
{
//use array space and assign the stack element
//until stack top is not null or its value
//is less than current array element
arr[j] = this.pop();
j--;
}
//assign current element
arr[j] = temp;
//After that array elements between given index is add to stack
for (k = j; k <= i; k++)
{
this.push(arr[k]);
}
}
}
//Assign the sorted value in actual array
for (int i = size - 1; i >= 0; --i)
{
arr[i] = this.pop();
}
}
//Display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
public static void main(String[] args)
{
MyStack obj = new MyStack();
//Define the element of unsorted array
int[] arr = {6,1,0,5,-2,8,2,3,6,-3,62,21};
//Get the size of array
int size = arr.length;
obj.display(arr, size);
obj.sort_array(arr, size);
obj.display(arr, size);
}
}
Output
6 1 0 5 -2 8 2 3 6 -3 62 21
-3 -2 0 1 2 3 5 6 6 8 21 62
/*
C++ Program
Sort array using stack
*/
//Stack Node
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node * next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
class MyStack
{
public:
Node * top;
MyStack()
{
this->top = NULL;
}
void display()
{
if (this->top != NULL)
{
Node * temp = this->top;
while (temp != NULL)
{
cout << " " << temp->data;
temp = temp->next;
}
}
cout << "\n";
}
//Add a new element in stack
void push(int data)
{
//Make a new stack node
Node * new_node = new Node(data);
if (new_node != NULL)
{
new_node->next = this->top;
this->top = new_node;
}
else
{
cout << "Memory overflow\n";
}
}
//Add a top element in stack
//When stack is empty it returns -1
int pop()
{
int temp = -1;
if (this->top != NULL)
{
temp = this->top->data;
this->top = this->top->next;
}
return temp;
}
bool is_empty()
{
if (this->top != NULL)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
int peek()
{
if (this->top != NULL)
{
return this->top->data;
}
else
{
return -1;
}
}
//Sort array element by using stack
void sort_array(int arr[], int size)
{
if (size <= 0)
{
return;
}
int temp = 0, j = 0, k = 0;
for (int i = 0; i < size; ++i)
{
if (this->is_empty() || this->peek() <= arr[i])
{
//Add array element into stack when stack is empty,
//or array element is greater than equal to top of stack
this->push(arr[i]);
}
else
{
j = i;
temp = arr[j];
//When array element is less than stack top element
//Then insert new element in its proper position
while (!this->is_empty() && this->peek() > temp)
{
//use array space and assign the stack element
//until stack top is not null or its value
//is less than current array element
arr[j] = this->pop();
j--;
}
//assign current element
arr[j] = temp;
//After that array elements between given index is add to stack
for (k = j; k <= i; k++)
{
this->push(arr[k]);
}
}
}
//Assign the sorted value in actual array
for (int i = size - 1; i >= 0; --i)
{
arr[i] = this->pop();
}
}
//Display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
};
int main()
{
MyStack obj = MyStack();
int arr[] = {
6,
1,
0,
5,
-2,
8,
2,
3,
6,
-3,
62,
21
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.display(arr, size);
obj.sort_array(arr, size);
obj.display(arr, size);
return 0;
}
Output
6 1 0 5 -2 8 2 3 6 -3 62 21
-3 -2 0 1 2 3 5 6 6 8 21 62
/*
C# Program
Sort array using stack
*/
//Stack Node
using System;
class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
class MyStack
{
public Node top;
public MyStack()
{
top = null;
}
public void display()
{
if (top != null)
{
Node temp = top;
while (temp != null)
{
Console.Write(" " + temp.data);
temp = temp.next;
}
}
Console.Write("\n");
}
//Add a new element in stack
public void push(int data)
{
//Make a new stack node
Node new_node = new Node(data);
if (new_node != null)
{
new_node.next = top;
top = new_node;
}
else
{
Console.Write("Memory overflow\n");
}
}
//Add a top element in stack
//When stack is empty it returns -1
public int pop()
{
int temp = -1;
if (top != null)
{
temp = top.data;
top = top.next;
}
return temp;
}
public Boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
public int peek()
{
if (top != null)
{
return top.data;
}
else
{
return -1;
}
}
//Sort array element by using stack
public void sort_array(int[] arr, int size)
{
if (size <= 0)
{
return;
}
int temp = 0, j = 0, k = 0;
for (int i = 0; i < size; i++)
{
if (this.is_empty() || this.peek() <= arr[i])
{
//Add array element into stack when stack is empty,
//or array element is greater than equal to top of stack
this.push(arr[i]);
}
else
{
j = i;
temp = arr[j];
//When array element is less than stack top element
//Then insert new element in its proper position
while (!this.is_empty() && this.peek() > temp)
{
//use array space and assign the stack element
//until stack top is not null or its value
//is less than current array element
arr[j] = this.pop();
j--;
}
//assign current element
arr[j] = temp;
//After that array elements between given index is add to stack
for (k = j; k <= i; k++)
{
this.push(arr[k]);
}
}
}
//Assign the sorted value in actual array
for (int i = size - 1; i >= 0; i--)
{
arr[i] = this.pop();
}
}
//Display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; i++)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args)
{
MyStack obj = new MyStack();
int[] arr = {
6,
1,
0,
5,
-2,
8,
2,
3,
6,
-3,
62,
21
};
//Get the size of array
int size = arr.Length;
obj.display(arr, size);
obj.sort_array(arr, size);
obj.display(arr, size);
}
}
Output
6 1 0 5 -2 8 2 3 6 -3 62 21
-3 -2 0 1 2 3 5 6 6 8 21 62
<?php
/*
Php Program
Sort array using stack
*/
//Stack Node
class Node
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = null;
}
}
class MyStack
{
public $top;
function __construct()
{
$this->top = null;
}
//Add a new element in stack
public function push($data)
{
//Make a new stack node
$new_node = new Node($data);
if ($new_node != null)
{
$new_node->next = $this->top;
$this->top = $new_node;
}
else
{
echo("Memory overflow\n");
}
}
//Add a top element in stack
//When stack is empty it returns -1
public function pop()
{
$temp = -1;
if ($this->top != null)
{
$temp = $this->top->data;
$this->top = $this->top->next;
}
return $temp;
}
public function is_empty()
{
if ($this->top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
public function peek()
{
if ($this->top != null)
{
return $this->top->data;
}
else
{
return -1;
}
}
//Sort array element by using stack
public function sort_array( & $arr, $size)
{
if ($size <= 0)
{
return;
}
$temp = 0;
$j = 0;
$k = 0;
for ($i = 0; $i < $size; ++$i)
{
if ($this->is_empty() || $this->peek() <= $arr[$i])
{
//Add array element into stack when stack is empty,
//or array element is greater than equal to top of stack
$this->push($arr[$i]);
}
else
{
$j = $i;
$temp = $arr[$j];
//When array element is less than stack top element
//Then insert new element in its proper position
while (!$this->is_empty() && $this->peek() > $temp)
{
//use array space and assign the stack element
//until stack top is not null or its value
//is less than current array element
$arr[$j] = $this->pop();
$j--;
}
//assign current element
$arr[$j] = $temp;
//After that array elements between given index is add to stack
for ($k = $j; $k <= $i; $k++)
{
$this->push($arr[$k]);
}
}
}
//Assign the sorted value in actual array
for ($i = $size - 1; $i >= 0; --$i)
{
$arr[$i] = $this->pop();
}
}
//Display array elements
public function display( & $arr, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo(" ". $arr[$i]);
}
echo("\n");
}
}
function main()
{
$obj = new MyStack();
//Define the element of unsorted array
$arr = array(6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21);
//Get the size of array
$size = count($arr);
$obj->display($arr, $size);
$obj->sort_array($arr, $size);
$obj->display($arr, $size);
}
main();
Output
6 1 0 5 -2 8 2 3 6 -3 62 21
-3 -2 0 1 2 3 5 6 6 8 21 62
/*
Node Js Program
Sort array using stack
*/
//Stack Node
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class MyStack
{
constructor()
{
this.top = null;
}
//Add a new element in stack
push(data)
{
//Make a new stack node
var new_node = new Node(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
process.stdout.write("Memory overflow\n");
}
}
//Add a top element in stack
//When stack is empty it returns -1
pop()
{
var temp = -1;
if (this.top != null)
{
temp = this.top.data;
this.top = this.top.next;
}
return temp;
}
is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return -1;
}
}
//Sort array element by using stack
sort_array(arr, size)
{
if (size <= 0)
{
return;
}
var temp = 0;
var j = 0;
var k = 0;
for (var i = 0; i < size; ++i)
{
if (this.is_empty() || this.peek() <= arr[i])
{
//Add array element into stack when stack is empty,
//or array element is greater than equal to top of stack
this.push(arr[i]);
}
else
{
j = i;
temp = arr[j];
//When array element is less than stack top element
//Then insert new element in its proper position
while (!this.is_empty() && this.peek() > temp)
{
//use array space and assign the stack element
//until stack top is not null or its value
//is less than current array element
arr[j] = this.pop();
j--;
}
//assign current element
arr[j] = temp;
//After that array elements between given index is add to stack
for (k = j; k <= i; k++)
{
this.push(arr[k]);
}
}
}
//Assign the sorted value in actual array
for (var i = size - 1; i >= 0; --i)
{
arr[i] = this.pop();
}
}
//Display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
}
function main(args)
{
var obj = new MyStack();
//Define the element of unsorted array
var arr = [6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21];
//Get the size of array
var size = arr.length;
obj.display(arr, size);
obj.sort_array(arr, size);
obj.display(arr, size);
}
main();
Output
6 1 0 5 -2 8 2 3 6 -3 62 21
-3 -2 0 1 2 3 5 6 6 8 21 62
# Python 3 Program
# Sort array using stack
# Stack Node
class Node :
def __init__(self, data) :
self.data = data
self.next = None
class MyStack :
def __init__(self) :
self.top = None
# Add a new element in stack
def push(self, data) :
# Make a new stack node
new_node = Node(data)
if (new_node != None) :
new_node.next = self.top
self.top = new_node
else :
print("Memory overflow\n", end = "")
# Add a top element in stack
# When stack is empty it returns -1
def pop(self) :
temp = -1
if (self.top != None) :
temp = self.top.data
self.top = self.top.next
return temp
def is_empty(self) :
if (self.top != None) :
return False
else :
return True
# Used to get top element of stack
def peek(self) :
if (self.top != None) :
return self.top.data
else :
return -1
# Sort array element by using stack
def sort_array(self, arr, size) :
if (size <= 0) :
return
temp = 0
j = 0
k = 0
i = 0
while (i < size) :
if (self.is_empty() or self.peek() <= arr[i]) :
# Add array element into stack when stack is empty,
# or array element is greater than equal to top of stack
self.push(arr[i])
else :
j = i
temp = arr[j]
# When array element is less than stack top element
# Then insert new element in its proper position
while (not self.is_empty() and self.peek() > temp) :
# use array space and assign the stack element
# until stack top is not null or its value
# is less than current array element
arr[j] = self.pop()
j -= 1
# assign current element
arr[j] = temp
# After that array elements between given index is add to stack
k = j
while (k <= i) :
self.push(arr[k])
k += 1
i += 1
# Assign the sorted value in actual array
i = size - 1
while (i >= 0) :
arr[i] = self.pop()
i -= 1
# Display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
def main() :
obj = MyStack()
arr = [6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21]
# Get the size of array
size = len(arr)
obj.display(arr, size)
obj.sort_array(arr, size)
obj.display(arr, size)
if __name__ == "__main__": main()
Output
6 1 0 5 -2 8 2 3 6 -3 62 21
-3 -2 0 1 2 3 5 6 6 8 21 62
# Ruby Program
# Sort array using stack
# Stack Node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top
attr_accessor :top
def initialize()
@top = nil
end
# Add a new element in stack
def push(data)
# Make a new stack node
new_node = Node.new(data)
if (new_node != nil)
new_node.next = @top
@top = new_node
else
print("Memory overflow\n")
end
end
# Add a top element in stack
# When stack is empty it returns -1
def pop()
temp = -1
if (@top != nil)
temp = @top.data
@top = @top.next
end
return temp
end
def is_empty()
if (self.top != nil)
return false
else
return true
end
end
# Used to get top element of stack
def peek()
if (@top != nil)
return @top.data
else
return -1
end
end
# Sort array element by using stack
def sort_array(arr, size)
if (size <= 0)
return
end
temp = 0
j = 0
k = 0
i = 0
while (i < size)
if (self.is_empty() || self.peek() <= arr[i])
# Add array element into stack when stack is empty,
# or array element is greater than equal to top of stack
self.push(arr[i])
else
j = i
temp = arr[j]
# When array element is less than stack top element
# Then insert new element in its proper position
while (!self.is_empty() && self.peek() > temp)
# use array space and assign the stack element
# until stack top is not null or its value
# is less than current array element
arr[j] = self.pop()
j -= 1
end
# assign current element
arr[j] = temp
# After that array elements between given index is add to stack
k = j
while (k <= i)
self.push(arr[k])
k += 1
end
end
i += 1
end
# Assign the sorted value in actual array
i = size - 1
while (i >= 0)
arr[i] = self.pop()
i -= 1
end
end
# Display array elements
def display(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
end
def main()
obj = MyStack.new()
arr = [6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21]
# Get the size of array
size = arr.length
obj.display(arr, size)
obj.sort_array(arr, size)
obj.display(arr, size)
end
main()
Output
6 1 0 5 -2 8 2 3 6 -3 62 21
-3 -2 0 1 2 3 5 6 6 8 21 62
/*
Scala Program
Sort array using stack
*/
//Stack Node
class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data,null);
}
}
class MyStack(var top: Node)
{
def this()
{
this(null);
}
//Add a new element in stack
def push(data: Int): Unit = {
//Make a new stack node
var new_node: Node = new Node(data);
if (new_node != null)
{
new_node.next = top;
top = new_node;
}
else
{
print("Memory overflow\n");
}
}
//Add a top element in stack
//When stack is empty it returns -1
def pop(): Int = {
var temp: Int = -1;
if (top != null)
{
temp = top.data;
top = top.next;
}
return temp;
}
def is_empty(): Boolean = {
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
def peek(): Int = {
if (top != null)
{
return top.data;
}
else
{
return -1;
}
}
//Sort array element by using stack
def sort_array(arr: Array[Int], size: Int): Unit = {
if (size <= 0)
{
return;
}
var temp: Int = 0;
var j: Int = 0;
var k: Int = 0;
var i: Int = 0;
while (i < size)
{
if (this.is_empty() || this.peek() <= arr(i))
{
//Add array element into stack when stack is empty,
//or array element is greater than equal to top of stack
this.push(arr(i));
}
else
{
j = i;
temp = arr(j);
//When array element is less than stack top element
//Then insert new element in its proper position
while (!this.is_empty() && this.peek() > temp)
{
//use array space and assign the stack element
//until stack top is not null or its value
//is less than current array element
arr(j) = this.pop();
j -= 1;
}
//assign current element
arr(j) = temp;
//After that array elements between given index is add to stack
k = j;
while (k <= i)
{
this.push(arr(k));
k += 1;
}
}
i += 1;
}
//Assign the sorted value in actual array
i = size - 1;
while (i >= 0)
{
arr(i) = this.pop();
i -= 1;
}
}
//Display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyStack = new MyStack();
var arr: Array[Int] = Array(6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21);
//Get the size of array
var size: Int = arr.length;
obj.display(arr, size);
obj.sort_array(arr, size);
obj.display(arr, size);
}
}
Output
6 1 0 5 -2 8 2 3 6 -3 62 21
-3 -2 0 1 2 3 5 6 6 8 21 62
/*
Swift Program
Sort array using stack
*/
//Stack Node
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class MyStack
{
var top: Node? ;
init()
{
self.top = nil;
}
//Add a new element in stack
func push(_ data: Int)
{
//Make a new stack node
let new_node: Node? = Node(data);
if (new_node != nil)
{
new_node!.next = self.top;
self.top = new_node;
}
else
{
print("Memory overflow\n", terminator: "");
}
}
//Add a top element in stack
//When stack is empty it returns -1
func pop() -> Int
{
var temp: Int = -1;
if (self.top != nil)
{
temp = self.top!.data;
self.top = self.top!.next;
}
return temp;
}
func is_empty() -> Bool
{
if (self.top != nil)
{
return false;
}
else
{
return true;
}
}
//Used to get top element of stack
func peek() -> Int
{
if (self.top != nil)
{
return self.top!.data;
}
else
{
return -1;
}
}
//Sort array element by using stack
func sort_array(_ arr: inout[Int], _ size: Int)
{
if (size <= 0)
{
return;
}
var temp: Int = 0;
var j: Int = 0;
var k: Int = 0;
var i: Int = 0;
while (i < size)
{
if (self.is_empty() || self.peek() <= arr[i])
{
//Add array element into stack when stack is empty,
//or array element is greater than equal to top of stack
self.push(arr[i]);
}
else
{
j = i;
temp = arr[j];
//When array element is less than stack top element
//Then insert new element in its proper position
while (!self.is_empty() && self.peek() > temp)
{
//use array space and assign the stack element
//until stack top is not null or its value
//is less than current array element
arr[j] = self.pop();
j -= 1;
}
//assign current element
arr[j] = temp;
//After that array elements between given index is add to stack
k = j;
while (k <= i)
{
self.push(arr[k]);
k += 1;
}
}
i += 1;
}
//Assign the sorted value in actual array
i = size - 1;
while (i >= 0)
{
arr[i] = self.pop();
i -= 1;
}
}
//Display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main()
{
let obj: MyStack = MyStack();
var arr: [Int] = [6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21];
//Get the size of array
let size: Int = arr.count;
obj.display(arr, size);
obj.sort_array(&arr, size);
obj.display(arr, size);
}
main();
Output
6 1 0 5 -2 8 2 3 6 -3 62 21
-3 -2 0 1 2 3 5 6 6 8 21 62
Time Complexity
The time complexity of the algorithm is O(n^2) in the worst case, where n is the size of the input array. This is because in the worst case, all elements are pushed and popped from the stack, which takes O(n) time in each iteration.
Resultant Output Explanation
For the given example array:
int arr[] = {6, 1, 0, 5, -2, 8, 2, 3, 6, -3, 62, 21};
The output shows the sorted array in non-decreasing order:
-3 -2 0 1 2 3 5 6 6 8 21 62
The output demonstrates that the array has been successfully sorted using the stack-based sorting algorithm.
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