Java Quick Sort Implementation

Quick sort is a divide and conquer algorithm. It divides a large list into 2 smaller sublists, the low elements and the high elements, then recursively does the same to the sublists.
First, pick an element from the unsorted list as a pivot point.
Second, reorder the list into two lists. A list of elements with values less than the pivot element and a list of elements with values greater
than the pivot element.
Third, recursively does the above steps to sort the list.

Here is an example of quick sort implemented with Java.

public class QuickSort {

    private int[] intlist;
    
    public QuickSort(int[] list)
    {
        this.intlist=list;
    }
    
    public void print()
    {
        for(int i=0; i<intlist.length; i++)
        {
                System.out.print(intlist[i]+" ");
        }
        System.out.println();
    }


    public int partition(int arr[], int left, int right)
    {  
        int l = left, r = right;  
        int tmp;  
        int pivot = arr[(left + right) / 2];  
        while (l <= r) 
        {        
            while (arr[l] < pivot)             
                    l++;
            while (arr[r] > pivot)
                    r--;
            if (l <= r) {  
                    tmp = arr[l];
                    arr[l] = arr[r];
                    arr[r] = tmp;
                    l++;
                    r--;
            }
        }
        return l;
    }

    public void quickSort(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
                quickSort(arr, left, index - 1);
        if (index < right)
                quickSort(arr, index, right);
    }

    public static void main(String args[])
    {
        int [] inta={33, 90, 2, 45, 1, 88, 75};
        QuickSort qs=new QuickSort(inta);
        qs.print();
        qs.quickSort(qs.intlist, 0,qs.intlist.length-1);
        qs.print();
    }

}

The output:

    33 90 2 45 1 88 75
    1 2 33 45 75 88 90

Search within Codexpedia

Custom Search

Search the entire web

Custom Search