Skip to main content

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.

  1. 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.

  2. 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.

  3. Recursively apply the Quick Sort algorithm to the two sub-arrays.

  4. 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

  1. Define a swap function to exchange the values of two elements in an array.
  2. Implement a partition function 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.
  3. Create the quick_sort function that uses the partitioning process recursively to sort the array. The function operates on subarrays created by partitioning.
  4. Design a display function to print the elements of the array.
  5. In the main function, initialize the array arr with input elements, get the size of the array, and display the array before sorting.
  6. Call the quick_sort function to sort the array in ascending order using the Quick Sort algorithm.
  7. Finally, call the display function 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  9

Time 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.





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