Quick Sort

 Let's begin!

Quick Sort is a sorting algorithm which follows the principle of Divide and Conquer with average time complexity as n(log n) and worst time complexity as n^2. 

We have two functions to implement Quick Sort:

Quick Sort Functions

• quickSort( ) Recursively call the function until start is less than end.
• partition( ) Swap elements to left which are less than pivot and brings pivot to it's ideal position.

	#include <iostream>
	using std::endl;
	using std::cin;
	using std::cout;
	void display(int arr[], int length)
	{
	for(int i=0; i<length; i++)
	{
	cout<<arr[i]<<" ";
	}
	cout<<endl;
	}
	void swap(int *num1, int *num2)
	{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
	}
	int partition(int arr[], int start, int end)
	{
	int pivot = arr[end];
	int initial = start-1;
	for (int i=start; i<=end-1; i++)
	{
	if(arr[i] < pivot)
	{
	swap(&arr[++initial], &arr[i]);
	}
	}
	swap(&arr[++initial], &arr[end]);
	return initial;
	}
	void quickSort(int arr[], int start, int end)
	{
	if(start<end)
	{
	int pivot_index = partition(arr, start, end);
	quickSort(arr, start, --pivot_index);
	quickSort(arr, ++pivot_index, end);
	}
	}
	int main()
	{
	int length;
	cout<<"Length of the Array: ";
	cin>>length;
	int arr[length];
	for(int i=0; i<length; i++)
	{
	cout<<"Enter Element "<<(i+1)<<" : ";
	cin>>arr[i];
	}
	cout<<"Given Array: ";
	display(arr, length);
	quickSort(arr, 0, length-1);
	cout<<"Sorted Array: ";
	display(arr, length);
	return 0;
	}

view raw quick_sort.cpp hosted with ❤ by GitHub

	package Algorithms.Sort;
	import java.util.Scanner;
	public class QuickSort {
	static public void display(int arr[], int length){
	for(int i=0; i<length; i++)
	{
	System.out.print(arr[i]+" ");
	}
	System.out.println("");
	}
	static public int partition(int arr[], int start, int end){
	int pivot = arr[end];
	int initial = start-1;
	for(int i=start; i<end; i++)
	{
	if(arr[i] < pivot)
	{
	int temp = arr[++initial];
	arr[initial] = arr[i];
	arr[i] = temp;
	}
	}
	int temp = arr[++initial];
	arr[initial] = arr[end];
	arr[end] = temp;
	return initial;
	}
	static public void quickSort(int arr[], int start, int end){
	if (start<end)
	{
	int pivot_index = partition(arr, start, end);
	quickSort(arr, start, --pivot_index);
	quickSort(arr, ++pivot_index, end);
	}
	}
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	System.out.print("Enter Length of the Array: ");
	int length = scan.nextInt();
	int arr[] = new int[length];
	for(int i=0; i<length; i++)
	{
	System.out.print("Enter Element "+(i+1)+" : ");
	arr[i] = scan.nextInt();
	}
	scan.close();
	System.out.print("Given Array: ");
	display(arr, length);
	quickSort(arr, 0, length-1);
	System.out.print("Sorted Array: ");
	display(arr, length);
	}
	}

view raw QuickSort.java hosted with ❤ by GitHub

	def partition(arr, start, end):
	pivot = arr[end]
	index = start - 1
	for i in range(start, end):
	if arr[i] < pivot:
	index += 1
	arr[index], arr[i] = arr[i], arr[index]
	index += 1
	arr[end], arr[index] = arr[index], arr[end]
	return index
	def quickSort(arr, start, end):
	if start<end:
	pivot_index = partition(arr, start, end)
	quickSort(arr, start, pivot_index-1)
	quickSort(arr, pivot_index+1, end)
	if __name__ == "__main__":
	user_input = input("Enter Length of the List: ")
	length = int(user_input)
	arr = []
	for num in range(length):
	user_input = input("Enter Element {} : ".format(num+1))
	arr.append(int(user_input))
	print("Given Array: ", arr)
	quickSort(arr, 0, length-1)
	print("Sorted Array: ", arr)

view raw quick_sort.py hosted with ❤ by GitHub