Quick Sort Program in Python | Java | C | C++

In this article, we will discuss the implementation of quicksort which is another recursive algorithm where we will follow the divide-and-conquer strategy time complexity of the QuickSort algorithm is O(N log N) in the average case and it is O(n2) in the worst case but Quick Sort is an in place sorting algorithm. We take an almost constant amount of extra memory and despite having a worst-case running time of O(n2) Quick Sort is pretty fast and efficient in practical scenarios the worst-case running time of Quick Sort is almost always avoided by using what we call a randomized version of Quick Sort randomized quicksort gives us O(N log N) running time with very high probability. Quick Sort is often the most practical choice for an efficient sorting Algorithm in fact sort function given to us by most of the language libraries are implementations of Quick Sort.

Quick Sort Program in C 

Solution In C

Code:

#include<stdio.h>

int partition(int arr[],int first,int last)
{
int i,j,temp;
i=first-1;
int x=arr[last];
for(j=first;j<last;j++){
if(arr[j]<x)
{
i++;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
i++;
temp=arr[i];
arr[i]=arr[last];
arr[last]=temp;
return i;
}

void qsort(int arr[],int first,int last)
{
int mid;
if(first<last)
{

mid=partition(arr,first,last);
qsort(arr,first,mid-1);
qsort(arr,mid+1,last);
}
}

int main()
{
int size;
    printf("Enter the size of the array:");
    scanf("%d",&size);
    int arr[size],i;
    printf("Enter the element of the array:");
    for(i=0;i<size;i++)
        scanf("%d",&arr[i]);

    printf("Before Sorting Array Element are: ");
    for(i=0;i<size;i++)
        printf("%d ",arr[i]);

qsort(arr,0,size-1);

  printf("\nAfter Sorting Array Element are: ");
        for(i=0;i<size;i++)
        printf("%d ",arr[i]);

}

Input/Output:

Enter the size of the array:5

Enter the element of the array:

4

3
7
8
9
Before Sorting Array Elements are: 4 3 7 8 9
After Sorting Array Elements are: 3 4 7 8 9

Quick sort Program in C plus plus 

Solution In C++

Code:

#include<iostream>
using namespace std;
int partition(int arr[],int first,int last)
{
int i,j,temp;
i=first-1;
int x=arr[last];
for(j=first;j<last;j++){
if(arr[j]<x)
{
i++;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
i++;
temp=arr[i];
arr[i]=arr[last];
arr[last]=temp;
return i;
}
void qsort(int arr[],int first,int last)
{
int mid;
if(first<last)
{

mid=partition(arr,first,last);
qsort(arr,first,mid-1);
qsort(arr,mid+1,last);
}
}
int main()
{
int size;
    cout<<"Enter the size of the array:";
    cin>>size;
    int arr[size],i;
    cout<<"Enter the element of the array:";
    for(i=0;i<size;i++)
        cin>>arr[i];

    cout<<"Before Sorting Array Element are: ";
    for(i=0;i<size;i++)
        cout<<arr[i]<<" ";

qsort(arr,0,size-1);

   cout<<"\nAfter Sorting Array Element are: ";
        for(i=0;i<size;i++)
        cout<<arr[i]<<" ";

}

Input/Output:

Enter the size of the array:4
Enter the element of the array:
7
9
3
5
Before Sorting Array Elements are: 7 9 3 5
After Sorting Array Elements are: 5 3 7 9

Quick Sort  Program in Java

Solution In Java

Code:

import java.util.Scanner;
public class Qucik_Sort {
static int partition(int arr[],int first,int last)
{
int i,j,temp;
i=first-1;
int x=arr[last];
for(j=first;j<last;j++){
if(arr[j]<x)
{
i++;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
i++;
temp=arr[i];
arr[i]=arr[last];
arr[last]=temp;
return i;
}

static void qsort(int arr[],int first,int last)
{
int mid;
if(first<last)
{

mid=partition(arr,first,last);
qsort(arr,first,mid-1);
qsort(arr,mid+1,last);
}
}

public static void main(String[] args) {
Scanner cs=new Scanner(System.in);
int size;
    System.out.print("Enter the size of the array:");
    size=cs.nextInt();
    int arr[]=new int[size],i;
    System.out.print("Enter the element of the array:");
    for(i=0;i<size;i++)
        arr[i]=cs.nextInt();

    System.out.print("Before Sorting Array Element are: ");
    for(i=0;i<size;i++)
        System.out.print(arr[i]+" ");
        
    qsort(arr,0,size-1);
   
        System.out.print("\nAfter Sorting Array Element are: ");
        for(i=0;i<size;i++)
        System.out.print(arr[i]+" ");
cs.close();


}

}

Input/Output:

Enter the size of the array:4
Enter the element of the array:3
2
2
6
Before Sorting Array Elements are: 3 2 2 6 
After Sorting Array Elements are: 2 2 3 6 

Quick Sort Program in python using list

Solution In Python

def partition(arr,first,last):
    i=first-1
    x=arr[last]
    for j in range(first,last):
        if(arr[j]<x):
            i+=1
            temp=arr[i]
            arr[i]=arr[j]
            arr[j]=temp
    i+=1
    temp=arr[i]
    arr[i]=arr[last]
    arr[last]=temp
    return i

def qsort(arr,first,last):
    if(first<last):
        mid=partition(arr,first,last)
        qsort(arr,first,mid-1)
        qsort(arr,mid+1,last)

size=int(input("Enter the size of the array:"))
arr=[]
print("Enter the element of the array:")
for i in range(0,size):
    num = int(input())
    arr.append(num)

print("Before Sorting Array Element are: ",arr)

qsort(arr,0,size-1)

print("\nAfter Sorting Array Element are: ",arr)

Input/Output:

Enter the size of the array:5
Enter the element of the array:
4
3
6
7
4
Before Sorting Array Element are:  [4, 3, 6, 7, 4]

After Sorting Array Element are:  [3, 4, 4, 6, 7]