Running Time of Quicksort HackerRank Solution

Running Time of Quicksort HackerRank Solution
Source : https://www.hackerrank.com/challenges/quicksort4

The running time of Quicksort will depend on how balanced the partitions are. If you are unlucky and select the greatest or the smallest element as the pivot, then each partition will separate only one element at a time, so the running time will be similar to Insertion Sort.

However, Quicksort will usually pick a pivot that is mid-range, and it will partition the array into two parts. Let's assume Partition is lucky and it always picks the median element as the pivot. What will be the running time in such a case?

Running Time of Recursive Methods
Quicksort is a recursive method, so we will have to use a technique to calculate the total running time of all the method calls. We can use a version of the "Recursion Tree Method" to estimate the running time for a given array of elements.

Each time partition is called on a sub-array, each element in the sub-array needs to be compared to the pivot element. Since all the sub-arrays are passed to partition, there will be total operations for each level of the tree.

How many levels will it take for the Quicksort to finish? Since we assume it always picks the middle element, the array will be split into two equal halves each time. So it will take splits until we get single elements in the sub-arrays. Since there are levels and each one involves operations, the total running time for Quicksort will be .

In real sorting, Quicksort won't always pick the exact middle element. But as long as it's regularly picking elements near the median value, it will have a running time better than Insertion Sort. To make sure that Quicksort works well on most inputs, the real-world implementations do not pick the same index as pivot each time. They use some other technique, e.g. picking a random element. There are other techniques, as well, that can be used to improve Quicksort. The Java Arrays class uses a modified version of Quicksort to sort primitives.

Notice that of Quicksort is much much faster than the ) of Insertion Sort. For example, for an array of one million elements, , while is approximately , a much more manageable number.

Challenge
In practice, how much faster is Quicksort (in-place) than Insertion Sort? Compare the running time of the two algorithms by counting how many swaps or shifts each one takes to sort an array, and output the difference. You can modify your previous sorting code to keep track of the swaps. The number of swaps required by Quicksort to sort any given input have to be calculated. Keep in mind that the last element of a block is chosen as the pivot, and that the array is sorted in-place as demonstrated in the explanation below.

Any time a number is lower than the partition, it should be "swapped", even if it doesn't actually move to a different location. Also ensure that you count the swap when the pivot is moved into place. The count for Insertion Sort should be the same as the previous challenge, where you just count the number of "shifts".

Note
Please use Lomuto Partition for this challenge.

Input Format
There will be two lines of input:

• - the size of the array
• - numbers that make up the array

Output Format
Output one integer , where (insertion sort shifts) - (quicksort swaps)

Constraints

Sample Input

71 3 9 8 2 7 5

Sample Output

1

Explanation
Insertion Sort will take 9 "shifts" to sort the array. Quicksort will take 8 "swaps" to sort it, as shown in the diagram below. is the final output.

Source : https://www.hackerrank.com/challenges/quicksort4

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	public class Solution {
	private static int swaps = 0; // counts swaps in quickSort
	public static void main(String[] args) {
	/* Save input */
	Scanner scan = new Scanner(System.in);
	int s = scan.nextInt();
	int[] array = new int[s];
	for (int i = 0; i < s; i++) {
	array[i] = scan.nextInt();
	}
	scan.close();
	/* Count shifts, swaps */
	int[] array2 = array.clone(); // save a copy before we sort it
	int shifts = insertionSortShifts(array);
	quickSort(array2);
	System.out.println(shifts - swaps);
	}
	public static int insertionSortShifts(int[] array) {
	int shifts = 0;
	for (int i = 1; i < array.length; i++) {
	int j = i;
	int value = array[i];
	while (j >= 1 && array[j-1] > value) { // find where to insert "value"
	array[j] = array[j-1]; // shift elements (1 by 1) to make room for inserting
	j--;
	shifts++;
	}
	array[j] = value;
	}
	return shifts;
	}
	public static void quickSort(int [] array) {
	quickSort(array, 0, array.length - 1);
	}
	private static void quickSort(int [] array, int start, int end) {
	if (start < end) {
	int pivotIndex = partition(array, start, end);
	quickSort(array, start, pivotIndex - 1);
	quickSort(array, pivotIndex + 1, end);
	}
	}
	/* Must use "Lomuto Partition" scheme (which isn't very efficient) from Wikipedia:
	https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme */
	private static int partition(int[] A, int lo, int hi) {
	int pivot = A[hi];
	int i = lo - 1;
	for (int j = lo; j <= hi - 1; j++) {
	if (A[j] <= pivot) {
	i++;
	swap(A, i , j);
	}
	}
	swap(A, i + 1, hi);
	return i + 1;
	}
	private static void swap(int [] array, int i, int j) {
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
	swaps++;
	}
	}