Quick Sort Example
Given an array of integers, the goal is to rearrange the elements in such a way that they are in ascending order. For example, given the array [3, 7, 1, -2, 5, 7, 6, 2, 1, 6, 6, 2, 9, 8], after applying the Quick Sort algorithm, the array becomes [-2, 1, 1, 2, 2, 3, 5, 6, 6, 6, 7, 7, 8, 9].
Quick Sort is a widely used sorting algorithm known for its efficiency and average-case performance.
Idea to Solve the Problem
The Quick Sort algorithm uses a divide-and-conquer approach to efficiently sort an array. It selects a pivot element, partitions the array around the pivot, and recursively sorts the subarrays on either side of the pivot.
Choose a pivot element from the array. The pivot can be chosen in several ways, but a common approach is to select the last element of the array.
Partition the array into two sub-arrays, one containing elements that are smaller than the pivot and the other containing elements that are greater than or equal to the pivot.
Recursively apply the Quick Sort algorithm to the two sub-arrays.
Combine the sorted sub-arrays to produce the final sorted array.
Pseudocode
swap(arr, first, second):
temp = arr[first]
arr[first] = arr[second]
arr[second] = temp
partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j = low to high - 1:
if arr[j] < pivot:
i++
swap(arr, i, j)
swap(arr, i + 1, high)
return i + 1
quick_sort(arr, low, high):
if low < high:
pivot = partition(arr, low, high)
quick_sort(arr, low, pivot - 1)
quick_sort(arr, pivot + 1, high)
display(arr, size):
for i = 0 to size - 1:
print arr[i]
main():
Initialize arr with input elements
Get size of arr
Print "Before Sort:"
Call display(arr, size)
Call quick_sort(arr, 0, size - 1)
Print "After Sort:"
Call display(arr, size)Algorithm Explanation
- Define a
swapfunction to exchange the values of two elements in an array. - Implement a
partitionfunction that selects a pivot element and rearranges the array so that elements less than the pivot are on the left and greater are on the right. The pivot element is placed in its correct sorted position. - Create the
quick_sortfunction that uses the partitioning process recursively to sort the array. The function operates on subarrays created by partitioning. - Design a
displayfunction to print the elements of the array. - In the
mainfunction, initialize the arrayarrwith input elements, get the size of the array, and display the array before sorting. - Call the
quick_sortfunction to sort the array in ascending order using the Quick Sort algorithm. - Finally, call the
displayfunction to print the sorted array.
Code Solution
//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 9Time Complexity Analysis
The Quick Sort algorithm's average and best-case time complexity is O(n log n), which makes it one of the most efficient sorting algorithms. However, in the worst case, Quick Sort has a time complexity of O(n^2). The space complexity is O(log n) due to the recursive call stack.
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