Quick Sort

Medium

Python

def quick_sort(arr):
    if len(arr)<=1: return arr
    p=arr[len(arr)//2]
    l=[x for x in arr if x<p]
    m=[x for x in arr if x==p]
    r=[x for x in arr if x>p]
    return quick_sort(l)+m+quick_sort(r)

Java

public void quickSort(int[] arr,int lo,int hi){
    if(lo<hi){
        int p=partition(arr,lo,hi);
        quickSort(arr,lo,p-1);
        quickSort(arr,p+1,hi);
    }
}
int partition(int[] arr,int l,int h){
    int p=arr[h],i=l-1;
    for(int j=l;j<h;j++) if(arr[j]<=p){i++;int t=arr[i];arr[i]=arr[j];arr[j]=t;}
    int t=arr[i+1];arr[i+1]=arr[h];arr[h]=t;
    return i+1;
}

Key Insight

Python comprehensions are readable. Java in-place is memory efficient.

Python → Java Differences

List comprehensions vs in-place
Python readable Java efficient
Different implementations same concept

Python

def quick_sort(arr):
    if len(arr)<=1: return arr
    p=arr[len(arr)//2]
    l=[x for x in arr if x<p]
    m=[x for x in arr if x==p]
    r=[x for x in arr if x>p]
    return quick_sort(l)+m+quick_sort(r)

Java

public void quickSort(int[] arr,int lo,int hi){
    if(lo<hi){
        int p=partition(arr,lo,hi);
        quickSort(arr,lo,p-1);
        quickSort(arr,p+1,hi);
    }
}
int partition(int[] arr,int l,int h){
    int p=arr[h],i=l-1;
    for(int j=l;j<h;j++) if(arr[j]<=p){i++;int t=arr[i];arr[i]=arr[j];arr[j]=t;}
    int t=arr[i+1];arr[i+1]=arr[h];arr[h]=t;
    return i+1;
}

Algorithm Steps

1. Choose pivot
2. Partition
3. Recurse

← Previous All Sorting Next →