Code implementation of the Quick Sort:
C++
#include
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]
// 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
// 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
Python
# 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#
// 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
JavaScript
// 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
Contact Us