# Sort a given set of n integer elements using Quick Sort method and compute its time complexity

0 like 0 dislike
1.3k views

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. The elements can be read from a file or can be generated using the random number generator. Demonstrate using Java how the divide-and-conquer method works along with its time complexity analysis: worst case,average case and best case.

### For Indian Students- INR 570/- || For International Students- \$12.99/-

S.No.

Course Name

Apply Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence

Apply Coupon

2.

Computer Vision with OpenCV | Deep Learning CNN Projects

Apply Coupon

3.

Complete Machine Learning & Data Science with Python Apply Coupon

4.

Natural Language Processing-NLP with Deep Learning in Python Apply Coupon

5.

Computer Vision OpenCV Python | YOLO| Deep Learning in Colab Apply Coupon

6.

Complete Python Programming from scratch with Projects Apply Coupon

0 like 0 dislike
by Goeduhub's Expert (5.8k points)

Java Program

import java.util.Random;

import java.util.Scanner;

class QuickSort {

static int comparisons = 0;

static int[] arr;

static void quickSort(int low, int high) {

if (low < high) {

comparisons += 1;

int j = partition(low, high);

quickSort(low, j - 1);

quickSort(j + 1, high);

}

}

static int partition(int low, int high) {

int pivot = arr[low];

int i = low, j = high;

while (i < j) {

comparisons += 1;

while (i < high && arr[i] <= pivot) {

comparisons += 2;

i = i + 1;

}

while (j > low && arr[j] >= pivot) {

comparisons += 2;

j = j - 1;

}

if (i < j) {

comparisons += 1;

interchange(i, j);

}

}

arr[low] = arr[j];

arr[j] = pivot;

return j;

}

static void interchange(int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

public static void main(String[] args) {

int n;

Scanner scanner = new Scanner(System.in);

System.out.print("Enter value of n: ");

n = scanner.nextInt();

arr = new int[n];

System.out.println("Quick Sort");

System.out.println("1. Best/Average Case");

System.out.println("2. Worst Case");

int ch = scanner.nextInt();

switch (ch) {

case 1:

Random random = new Random(3000);

for (int i = 0; i < n; i++) {

arr[i] = random.nextInt();

}

break;

case 2:

for (int i = 0; i < n; i++) {

arr[i] = i + 1;

}

break;

}

long start = System.nanoTime();

quickSort(0, n - 1);

long end = System.nanoTime();

System.out.println("Sorted Array");

for (int i = 0; i < n; i++) {

System.out.println(arr[i]);

}

System.out.println("Time taken: " + (end - start));

System.out.println("Comparisons: " + comparisons);

}

}

Output

.............

Series of numbers is generated (5100 numbers)

.............