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