

Program: Implement quick sort in java.
Quicksort or partitionexchange sort, is a fast sorting algorithm, which is using divide and conquer algorithm. Quicksort first divides a large list
into two smaller sublists: the low elements and the high elements. Quicksort can then recursively sort the sublists.
Steps to implement Quick sort:
1) Choose an element, called pivot, from the list. Generally pivot can be the middle index element.
2) Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values
greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position.
This is called the partition operation.
3) Recursively apply the above steps to the sublist of elements with smaller values and separately the sublist of elements with greater values.
The complexity of quick sort in the average case is Θ(n log(n)) and in the worst case is Θ(n2).
package com.java2novice.sorting;
public class MyQuickSort {
private int array[];
private int length;
public void sort(int[] inputArr) {
if (inputArr == null  inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length  1);
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndexlowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
MyQuickSort sorter = new MyQuickSort();
int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}


Output: 
2 2 12 20 24 45 53 56 56 75 99



Tech Tip : Software developer can take a positive steps towards being productive by moving their software testing and debugging environment into the cloud with virtual desktop from www.CloudDesktopOnline.com with 24*7 dedicated migration support from
Apps4Rent.com.



Java Sorting Algorithms Examples
 Implement bubble sort in java.
 Implement selection sort in java.
 Implement insertion sort in java.
 Implement quick sort in java.
 Implement merge sort in java.



When to use LinkedList or ArrayList?
Accessing elements are faster with ArrayList, because it is index based.
But accessing is difficult with LinkedList. It is slow access. This is
to access any element, you need to navigate through the elements one by
one. But insertion and deletion is much faster with LinkedList, because
if you know the node, just change the pointers before or after nodes.
Insertion and deletion is slow with ArrayList, this is because, during
these operations ArrayList need to adjust the indexes according to
deletion or insetion if you are performing on middle indexes. Means,
an ArrayList having 10 elements, if you are inserting at index 5, then
you need to shift the indexes above 5 to one more.
I respect faith, but doubt is what gets you an education.
 Wilson Mizner
