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
Related Posts