« Quick Sort a array

Problem

Sort an array A using Quick Sort. Change in the input array itself. So no need to return or print anything.

Input format :

Line 1 : Integer n i.e. Array size

Line 2 : Array elements (separated by space)

Output format :

Array elements in increasing order (separated by space)

Constraints :

1 <= n <= 10^3

Sample Input 1 :

6

2 6 8 5 4 3

Sample Output 1 :

2 3 4 5 6 8

Sample Input 2 :

5

1 5 2 7 3

Sample Output 2 :

1 2 3 5 7

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14void swap(int *a, int *b)
15{
16    int temp = *a;
17    *a = *b;
18    *b = temp;
19}
20
21int partition(int input[], int low, int high)
22{
23    int pivot = input[high];
24    int i = low;
25    for (int j = low; j <= high; j++)
26    {
27        if (input[j] < pivot)
28        {
29            swap(&input[i], &input[j]);
30            i++;
31        }
32    }
33    swap(&input[i], &input[high]);
34    return (i);
35}
36
37void quickSort(int input[], int low, int high)
38{
39    if (low >= high)
40    {
41        return;
42    }
43    int pi = partition(input, low, high);
44    quickSort(input, low, pi - 1);
45    quickSort(input, pi + 1, high);
46}
47
48void quicksort(int input[], int size)
49{
50    quickSort(input, 0, size - 1);
51}
52
53int main()
54{
55    int n;
56    cin >> n;
57    int *input = new int[n];
58    for (int i = 0; i < n; i++)
59    {
60        cin >> input[i];
61    }
62    quicksort(input, n);
63    for (int i = 0; i < n; i++)
64    {
65        cout << input[i] << " ";
66    }
67    cout << endl;
68    delete[] input;
69    return 0;
70}