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.
[code language=”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();
}

}
[/code]

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