Skip to main content

Sort array using stack

Here given code implementation process.

//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
Last updated on by Kalkicode




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.

New Comment