There are so many sorting technique / algorithm like bubble sort, merge sort, selection sort, quick sort, insertion sort etc.
Quicksort is the mostly used sorting algorithm in the computer world. The performance of the Quick Sort is better than bubble sorting, merge sorting. The main key point is divide and conquer. Due to his divide rule sometimes it also called as partition-exchange sort. This sorting used when need to handle with a big amount of data.
QuickSort Algorithm Java:-
- First select any reference element from the data, this reference element also called as pivot element.
- Now divide the full list into two group with respect to this reference element, one will have all the element less than the reference element and another group will have all the element with greater than reference element.
- Now repeat step one and step two in both parts.
Implementation of QuickSort Java:-
package one;
import java.util.ArrayList;
import java.util.Random;
public class QuickSort
{
public static void main(String[] args)
{
// Creating a list of a integer
ArrayList<Integer> list = new ArrayList<Integer>();
// Create a new object to create a random integer number
Random randomGenerator = new Random();
for (int i = 0; i < 11; ++i)
{
// add random generated
list.add(randomGenerator.nextInt(100));
}
for(int i : list)
System.out.print(i + ",");
QuickSorting(list, 0, list.size()-1);
System.out.println("\n" + "Sorted List is ");
for(int i : list)
System.out.print(i + ",");
}
private static void QuickSorting(ArrayList<Integer> list, int start, int end)
{
if (list.isEmpty())
return;
if (start >= end)
return;
// Get the reference element
int middle = (end + start)/2;
int refElement = list.get(middle);
int left = start, right = end;
while(left <= right)
{
// check a number from left which is greater than reference element
while(list.get(left) < refElement)
left++;
// check a number from right which is less than reference element
while(list.get(right) > refElement)
right--;
// if from above checking we find any odd will exchange the number
// so that all element those are less than reference element will move to left
if (left <= right)
{
int temp = list.get(left);
list.set(left, list.get(right));
list.set(right, temp);
left++;
right--;
}
}
// Do recursively call on both group
if (start < right)
QuickSorting(list,start, right);
if ( left < end)
QuickSorting(list,left, end);
}
}
Output:
79,91,57,84,10,78,9,28,60,77,47
Sorted List is:-
9,10,28,47,57,60,77,78,79,84,91
Explanation of Java QuickSort Example:-
In first pass 79,91,57,84,10,78,9,28,60,77,47
It will get middle index from the list and get the reference element
int middle = (end + start)/2;
int refElement = list.get(middle);
From above reference element will be (0 + 10)/ 2 = 5 i.s value at 5th index that is 78.
And variable left will set 0, and right will set 10.
Now we have two sub list as 79,91,57,84,10,78,9,28,60,77,47.
Now loop will loop start until left will reach to right position.
Now reference element (78) will check if any element from left list is greater, 79 is greater than 78.
Now reference element (78) will check if any element from left list is less, 47 is less than 78, both numbers will interchange his position.
So now list would be looks like as 47,91,57,84,10,78,9,28,60,77,79.
Now left value is 1 and right value is 9.
Now reference element (78) will check value at index 1 (91), reference element is less than value at index 1 (91), now reference element (78) will check value at index 9 (77) , reference element is greater than value at index 9. Now value at index 1 and 9 will interchange. New list is 47,77,57,84,10,78,9,28,60,91,79
Now left value is 2 and right value is 8.
Now reference element (78) will check value at index 2 (57), reference element is greater than value at index 2 (57), so now value of left will be 3 again reference element (78) will check value at index 3 (84), reference element is less than value at index 3 (84).
Now reference element (78) will check value at index 8 (60), reference element is greater than value at index 8 (60). Now value at index 3 and 8 will interchange. New list is
47,77,57,60,10,78,9,28,84,91,79
Now left value is 4 and right value is 7
Now reference element (78) will check value at index 4 (10), reference element is greater than value at index 4 (10), so now so now value of left will be 5, reference element (78) will check value at index 5 (78) ,reference element is equal to value at index 5 (78).
Now reference element (78) will check value at index 7 (28), reference element is greater than value at index 7 (28). Now value at index 5 and 7 will interchange. New list is
47,77,57,60,10,28,9,78,84,91,79
Now left value is 6 and right value is 6
Now loop will run and, this time, value at index 6 will check with a value of left will increase from 6 to 7.
The if condition “if (left <= right)” will fail no interchange will happen. And finally, while block terminates.
This time start = 0, end = 10, left = 7, right = 6.
if (start < right)
QuickSorting(list,start, right);
if ( left < end)
QuickSorting(list,left, end);
As from above code, QuickSort method will apply to two sub list as shown below.
47,77,57,60,10,28,9,78,84,91,79
After doing the recursive operation at the end will get sorted list.
