2. Sort a given set of n integer elements using Quick Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++/Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case.
import java.util.*;
//Quick Sort is based on Divide and Conquor algorithm
public class QuickSort {
// Swap function is used to swap two elements in an array
public static void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
public static void sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Quick sort algorithm");
while (true) {
System.out.println("Enter the number of n (n > 5000): ");
int n = scan.nextInt();
int arr[] = new int[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt(100000);
}
System.out.println("Random Array: " + Arrays.toString(arr));
long start = System.nanoTime();
sort(arr, 0, arr.length - 1);
long end = System.nanoTime();
System.out.println("Sorted Array: " + Arrays.toString(arr));
System.out.println("Time taken to complete the process : " + (end - start) / 1e6 + " milli seconds");
}
}
}
NULL