Code implementation of the Quick Sort
#include <bits/stdc++.h>
using namespace std;
int partition(int arr[],int low,int high)
{
//choose the pivot
int pivot=arr[high];
//Index of smaller element and Indicate
//the right position of pivot found so far
int i=(low-1);
for(int j=low;j<=high-1;j++)
{
//If current element is smaller than the pivot
if(arr[j]<pivot)
{
//Increment index of smaller element
i++;
swap(arr[i],arr[j]);
}
}
swap(arr[i+1],arr[high]);
return (i+1);
}
// The Quicksort function Implement
void quickSort(int arr[],int low,int high)
{
// when low is less than high
if(low<high)
{
// pi is the partition return index of pivot
int pi=partition(arr,low,high);
//Recursion Call
//smaller element than pivot goes left and
//higher element goes right
quickSort(arr,low,pi-1);
quickSort(arr,pi+1,high);
}
}
int main() {
int arr[]={10,7,8,9,1,5};
int n=sizeof(arr)/sizeof(arr[0]);
// Function call
quickSort(arr,0,n-1);
//Print the sorted array
cout<<"Sorted Array\n";
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
// This Code is Contributed By Diwakar Jha
// C program for QuickSort
#include <stdio.h>
// Utility function to swap tp integers
void swap(int* p1, int* p2)
{
int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
int partition(int arr[], int low, int high)
{
// choose the pivot
int pivot = arr[high];
// Index of smaller element and Indicate
// the right position of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
// Increment index of smaller element
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// The Quicksort function Implement
void quickSort(int arr[], int low, int high)
{
// when low is less than high
if (low < high) {
// pi is the partition return index of pivot
int pi = partition(arr, low, high);
// Recursion Call
// smaller element than pivot goes left and
// higher element goes right
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main()
{
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
quickSort(arr, 0, n - 1);
// Print the sorted array
printf("Sorted Array\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// This Code is Contributed By Diwakar Jha
// Java implementation of QuickSort
import java.io.*;
class GFG {
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// This function takes last element as pivot,
// places the pivot element at its correct position
// in sorted array, and places all smaller to left
// of pivot and all greater elements to right of pivot
static int partition(int[] arr, int low, int high)
{
// Choosing the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
// Increment index of smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// To print sorted array
public static void printArr(int[] arr)
{
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int N = arr.length;
// Function call
quickSort(arr, 0, N - 1);
System.out.println("Sorted array:");
printArr(arr);
}
}
// This code is contributed by Ayush Choudhary
// Improved by Ajay Virmoti
# Python3 implementation of QuickSort
# Function to find the partition position
def partition(array, low, high):
# Choose the rightmost element as pivot
pivot = array[high]
# Pointer for greater element
i = low - 1
# Traverse through all elements
# compare each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# If element smaller than pivot is found
# swap it with the greater element pointed by i
i = i + 1
# Swapping element at i with element at j
(array[i], array[j]) = (array[j], array[i])
# Swap the pivot element with
# the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])
# Return the position from where partition is done
return i + 1
# Function to perform quicksort
def quicksort(array, low, high):
if low < high:
# Find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)
# Recursive call on the left of pivot
quicksort(array, low, pi - 1)
# Recursive call on the right of pivot
quicksort(array, pi + 1, high)
# Driver code
if __name__ == '__main__':
array = [10, 7, 8, 9, 1, 5]
N = len(array)
# Function call
quicksort(array, 0, N - 1)
print('Sorted array:')
for x in array:
print(x, end=" ")
# This code is contributed by Adnan Aliakbar
// C# implementation of QuickSort
using System;
class GFG {
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// This function takes last element as pivot,
// places the pivot element at its correct position
// in sorted array, and places all smaller to left
// of pivot and all greater elements to right of pivot
static int partition(int[] arr, int low, int high)
{
// Choosing the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
// Increment index of smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// and after partition index
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Driver Code
public static void Main()
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int N = arr.Length;
// Function call
quickSort(arr, 0, N - 1);
Console.WriteLine("Sorted array:");
for (int i = 0; i < N; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by gfgking
// Function to partition the array and return the partition index
function partition(arr, low, high) {
// Choosing the pivot
let pivot = arr[high];
// Index of smaller element and indicates the right position of pivot found so far
let i = low - 1;
for (let j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
// Increment index of smaller element
i++;
[arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Swap pivot to its correct position
return i + 1; // Return the partition index
}
// The main function that implements QuickSort
function quickSort(arr, low, high) {
if (low < high) {
// pi is the partitioning index, arr[pi] is now at the right place
let pi = partition(arr, low, high);
// Separately sort elements before partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Driver code
let arr = [10, 7, 8, 9, 1, 5];
let N = arr.length;
// Function call
quickSort(arr, 0, N - 1);
console.log("Sorted array:");
console.log(arr.join(" "));
<?php
// code
?>
<?php
// This Function takes place last element as pivot
// Place the pivot as correct position
// In Sorted Array, and places all smaller to left
// of pivot and all greater element to its right of pivot
function partition(&$arr,$low,$high)
{
// Choose the Pivot Element
$pivot= $arr[$high];
// Index of smaller element and indicates
// The right position of pivot
$i=($low-1);
for($j=$low;$j<=$high-1;$j++)
{
if($arr[$j]<$pivot)
{
// Increment index of smaller element
$i++;
list($arr[$i],$arr[$j])=array($arr[$j],$arr[$i]);
}
}
// Pivot element as correct position
list($arr[$i+1],$arr[$high])=array($arr[$high],$arr[$i+1]);
return ($i+1);
}
// The main function that implement as QuickSort
// arr[]:- Array to be sorted
// low:- Starting Index
//high:- Ending Index
function quickSort(&$arr,$low,$high)
{
if($low<$high)
{
// pi is partition
$pi= partition($arr,$low,$high);
// Sort the array
// Before the partition of Element
quickSort($arr,$low,$pi-1);
// After the partition Element
quickSort($arr,$pi+1,$high);
}
}
// Driver Code
$arr= array(10,7,8,9,1,5);
$N=count($arr);
// Function Call
quickSort($arr,0,$N-1);
echo "Sorted Array:\n";
for($i=0;$i<$N;$i++)
{
echo $arr[$i]. " ";
}
//This code is contributed by Diwakar Jha
Output
Sorted Array 1 5 7 8 9 10
QuickSort – Data Structure and Algorithm Tutorials
QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.
Contact Us