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

Search the entire web
