Quick Sort Example

Here given code implementation process.

//C Program
//Quicksort Example in Array
#include <stdio.h>

//Display array elements
void display(int arr[],int size)
{
  for (int i = 0; i < size; ++i)
  {
    //Print array value of i location
    printf("%3d",arr[i] );
  }
  printf("\n");
}

//Swap the array element
void swap(int arr[],int first,int second)
{
  //first and second are index of array
  int temp = arr[first];
  arr[first] = arr[second];
  arr[second] = temp;
}
int part(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;
}
void quick_sort(int arr[],int low,int high)
{
  if(low < high)
  {
    //Get the pivot element
    int pv = part(arr,low,high);
    quick_sort(arr,low,pv-1);
    quick_sort(arr,pv+1,high);
  }
}
int main()
{
  //Define array element
  int arr[]= {3,7,1,-2,5,7,6,2,1,6,6,2,9,8};
  //Get the size of array
  int size=sizeof(arr)/sizeof(arr[0]);
  
  printf("Before Sort : \n");
  display(arr,size);

  quick_sort(arr,0,size-1);

  printf("After Sort : \n");
  display(arr,size);

 
  return 0;
}

Output

Before Sort :
  3  7  1 -2  5  7  6  2  1  6  6  2  9  8
After Sort :
 -2  1  1  2  2  3  5  6  6  6  7  7  8  9
/*
  C++ Program
  Quick Sort Example
*/
#include<iostream>

using namespace std;

class MySort {
	public:

		//Display array elements
		void display(int arr[], int size) {
			for (int i = 0; i < size; ++i) {
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	//Swap the array element
	void swap(int arr[], int first, int second) {
		//first and second are index of array
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	int part(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);
		return i + 1;
	}
	void quick_sort(int arr[], int low, int high) {
		if (low < high) {
			//Get the pivot element
			int pv = this->part(arr, low, high);
			this->quick_sort(arr, low, pv - 1);
			this->quick_sort(arr, pv + 1, high);
		}
	}
};
int main() {
	MySort obj ;
	int arr[] = {
		3,
		7,
		1,
		-2,
		5,
		7,
		6,
		2,
		1,
		6,
		6,
		2,
		9,
		8
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << "Before Sort : \n";
	obj.display(arr, size);
	obj.quick_sort(arr, 0, size - 1);
	cout << "After Sort : \n";
	obj.display(arr, size);
	return 0;
}

Output

Before Sort :
 3 7 1 -2 5 7 6 2 1 6 6 2 9 8
After Sort :
 -2 1 1 2 2 3 5 6 6 6 7 7 8 9
/*
  Java Program
  Quick Sort Example
*/
public class MySort {

  //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");
  }

  //Swap the array element
  public void swap(int []arr,int first,int second)
  {
    //first and second are index of array
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
  }
  public int part(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 quick_sort(int []arr,int low,int high)
  {
    if(low < high)
    {
      //Get the pivot element
      int pv = part(arr,low,high);
      quick_sort(arr,low,pv-1);
      quick_sort(arr,pv+1,high);
    }
  }
  public static void main(String[] args) 
  {
  

    MySort obj = new MySort();
    //Define array elements
    int []arr= {3,7,1,-2,5,7,6,2,1,6,6,2,9,8};
    //Get the size of array
    int size = arr.length;
    System.out.print("Before Sort : \n");
    obj.display(arr,size);

    obj.quick_sort(arr,0,size-1);
    System.out.print("After Sort : \n");
    obj.display(arr,size);

  }
}

Output

Before Sort :
 3 7 1 -2 5 7 6 2 1 6 6 2 9 8
After Sort :
 -2 1 1 2 2 3 5 6 6 6 7 7 8 9
/*
  C# Program
  Quick Sort Example
*/
using System;
public class MySort {
	//Display array elements
	public void display(int[] arr, int size) {
		for (int i = 0; i < size; ++i) {
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	//Swap the array element
	public void swap(int[] arr, int first, int second) {
		//first and second are index of array
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	public int part(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);
			}
		}
		swap(arr, i + 1, high);
		return i + 1;
	}
	public void quick_sort(int[] arr, int low, int high) {
		if (low < high) {
			//Get the pivot element
			int pv = part(arr, low, high);
			quick_sort(arr, low, pv - 1);
			quick_sort(arr, pv + 1, high);
		}
	}
	public static void Main(String[] args) {
		MySort obj = new MySort();
		int[]
		//Define array elements
		arr = {
			3,
			7,
			1,
			-2,
			5,
			7,
			6,
			2,
			1,
			6,
			6,
			2,
			9,
			8
		};
		//Get the size of array
		int size = arr.Length;
		Console.Write("Before Sort : \n");
		obj.display(arr, size);
		obj.quick_sort(arr, 0, size - 1);
		Console.Write("After Sort : \n");
		obj.display(arr, size);
	}
}

Output

Before Sort :
 3 7 1 -2 5 7 6 2 1 6 6 2 9 8
After Sort :
 -2 1 1 2 2 3 5 6 6 6 7 7 8 9
<?php
/*
  Php Program
  Quick Sort Example
*/
class MySort {
	//Display array elements

	public 	function display($arr, $size) {
		for ($i = 0; $i < $size; ++$i) {
			echo(" ". $arr[$i]);
		}
		echo("\n");
	}
	//Swap the array element

	public 	function swap(&$arr, $first, $second) {
		//first and second are index of array
		$temp = $arr[$first];
		$arr[$first] = $arr[$second];
		$arr[$second] = $temp;
	}
	public 	function part(&$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);
		return $i + 1;
	}
	public 	function quick_sort(&$arr, $low, $high) {
		if ($low < $high) {
			//Get the pivot element
			$pv = $this->part($arr, $low, $high);
			$this->quick_sort($arr, $low, $pv - 1);
			$this->quick_sort($arr, $pv + 1, $high);
		}
	}
}

function main() {
	$obj = new MySort();
	//Define array elements
	$arr = array(3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8);
	//Get the size of array
	$size = count($arr);
	echo("Before Sort : \n");
	$obj->display($arr, $size);
	$obj->quick_sort($arr, 0, $size - 1);
	echo("After Sort : \n");
	$obj->display($arr, $size);

}
main();

Output

Before Sort :
 3 7 1 -2 5 7 6 2 1 6 6 2 9 8
After Sort :
 -2 1 1 2 2 3 5 6 6 6 7 7 8 9
/*
  Node Js Program
  Quick Sort Example
*/
class MySort {
	//Display array elements
	display(arr, size) {
		for (var i = 0; i < size; ++i) {
			process.stdout.write(" " + arr[i]);
		}

		process.stdout.write("\n");
	}

	//Swap the array element
	swap(arr, first, second) {
		//first and second are index of array
		var temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	part(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);
		return i + 1;
	}
	quick_sort(arr, low, high) {
		if (low < high) {
			//Get the pivot element
			var pv = this.part(arr, low, high);
			this.quick_sort(arr, low, pv - 1);
			this.quick_sort(arr, pv + 1, high);
		}
	}
}

function main(args) {
	var obj = new MySort();
	//Define array elements
	var arr = [3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8];
	//Get the size of array
	var size = arr.length;
	process.stdout.write("Before Sort : \n");
	obj.display(arr, size);
	obj.quick_sort(arr, 0, size - 1);
	process.stdout.write("After Sort : \n");
	obj.display(arr, size);
}

main();

Output

Before Sort :
 3 7 1 -2 5 7 6 2 1 6 6 2 9 8
After Sort :
 -2 1 1 2 2 3 5 6 6 6 7 7 8 9
# Python 3 Program
# Quick Sort Example
class MySort :
	# Display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	# Swap the array element
	def swap(self, arr, first, second) :
		temp = arr[first]
		arr[first] = arr[second]
		arr[second] = temp
	
	def part(self, arr, low, high) :
		pv = arr[high]
		i = low - 1
		j = low
		while (j < high) :
			if (arr[j] < pv) :
				i += 1
				self.swap(arr, i, j)
			
			j += 1
		
		self.swap(arr, i + 1, high)
		return i + 1
	
	def quick_sort(self, arr, low, high) :
		if (low < high) :
			pv = self.part(arr, low, high)
			self.quick_sort(arr, low, pv - 1)
			self.quick_sort(arr, pv + 1, high)
		
	

def main() :
	obj = MySort()
	arr = [3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8]
	size = len(arr)
	print("Before Sort : \n", end = "")
	obj.display(arr, size)
	obj.quick_sort(arr, 0, size - 1)
	print("After Sort : \n", end = "")
	obj.display(arr, size)


if __name__ == "__main__":
	main()

Output

Before Sort :
  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
After Sort :
  -2  1  1  2  2  3  5  6  6  6  7  7  8  9
# Ruby Program
# Quick Sort Example
class MySort 
	# Display array elements
	def display(arr, size) 
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	# Swap the array element
	def swap(arr, first, second) 
		temp = arr[first]
		arr[first] = arr[second]
		arr[second] = temp
	end
	def part(arr, low, high) 
		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
		self.swap(arr, i + 1, high)
		return i + 1
	end
	def quick_sort(arr, low, high) 
		if (low < high) 
			pv = self.part(arr, low, high)
			self.quick_sort(arr, low, pv - 1)
			self.quick_sort(arr, pv + 1, high)
		end
	end
end
def main() 
	obj = MySort.new()
	arr = [3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8]
	size = arr.length
	print("Before Sort  :\n")
	obj.display(arr, size)
	obj.quick_sort(arr, 0, size - 1)
	print("After Sort  :\n")
	obj.display(arr, size)
end
main()

Output

Before Sort  :
 3 7 1 -2 5 7 6 2 1 6 6 2 9 8
After Sort  :
 -2 1 1 2 2 3 5 6 6 6 7 7 8 9
/*
  Scala Program
  Quick Sort Example
*/
class MySort {
	//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");
	}
	//Swap the array element
	def swap(arr: Array[Int], first: Int, second: Int): Unit = {
		val temp: Int = arr(first);
		arr(first) = arr(second);
		arr(second) = temp;
	}
	def part(arr: Array[Int], low: Int, high: Int): Int = {
		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;
		}
		this.swap(arr, i + 1, high);

		return i + 1;
	}
	def quick_sort(arr: Array[Int], low: Int, high: Int): Unit = {
		if (low < high) {
			val pv: Int = this.part(arr, low, high);
			this.quick_sort(arr, low, pv - 1);
			this.quick_sort(arr, pv + 1, high);
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MySort = new MySort();
		var arr: Array[Int] = Array(3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8);
		val size: Int = arr.length;
		print("Before Sort : \n");
		obj.display(arr, size);
		obj.quick_sort(arr, 0, size - 1);
		print("After Sort : \n");
		obj.display(arr, size);
	}
}

Output

Before Sort :
 3 7 1 -2 5 7 6 2 1 6 6 2 9 8
After Sort :
 -2 1 1 2 2 3 5 6 6 6 7 7 8 9
/*
  Swift Program
  Quick Sort Example
*/
class MySort {
	//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: "");
	}
	//Swap the array element
	func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
		let temp: Int = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	func part(_ arr: inout [Int], _ low: Int, _ high: Int) -> Int {
		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;
		}
		self.swap(&arr, i + 1, high);
		return i + 1;
	}
	func quick_sort(_ arr: inout [Int], _ low: Int, _ high: Int) {
		if (low < high) {
			let pv: Int = self.part(&arr, low, high);
			self.quick_sort(&arr, low, pv - 1);
			self.quick_sort(&arr, pv + 1, high);
		}
	}
}
func main() {
	let obj: MySort = MySort();
	var arr: [Int] = [3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8];
	let size: Int = arr.count;
	print("Before Sort : \n", terminator: "");
	obj.display(arr, size);
	obj.quick_sort(&arr, 0, size - 1);
	print("After Sort : \n", terminator: "");
	obj.display(arr, size);
}
main();

Output

Before Sort :
  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
After Sort :
  -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.

New Comment







© 2021, kalkicode.com, All rights reserved