Computer scienceProgramming languagesJavaInterview preparationAlgorithms and problem solving techniques

Sorting algorithm problem in action

Theory

Quick sort

Report a typo

Write a function quickSort that takes an unsorted list of integers as input and returns a sorted list using the quick sort algorithm. Your implementation should be recursive and should use the first element of the input list as the pivot element.

Your function should also include the following modifications to the basic quick sort algorithm:

  1. For input sizes below a certain threshold (e.g., 10 elements), switch to an insertion sort algorithm instead of recursively calling quick sort. This is because insertion sort is generally faster for small input sizes.

  2. To improve performance, use a random pivot element instead of always using the first element of the input list.

Your implementation should have an average time complexity of O(n log n)O(n\:log\:n) and should use in-place sorting (i.e., without creating a new copy of the input list).

Note: you can assume that the input list contains only integers.

Sample Input 1: 

15
12 4 6 7 3 1 15 8 9 2 11 5 14 13 10

Sample Output 1: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Write a program in Java 17
import java.util.Scanner;

class Main {
public static void quickSort(int[] arr, int start, int end) {
// implement me
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
int[] arr = new int[count];
for (int i = 0; i < count; ++i) {
arr[i] = scanner.nextInt();
}

quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
___

Create a free account to access the full topic