Quicksort 1 - Partition

The divide-and-conquer algorithm called QuickSOrt (also known as Partition Sort).

Example:

Input:  n=5, arr[]={4,5,3,7,2}
Output: 3 2 4 5 7

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Quicksort1Partition {
    public static void main(String[] args) {
        int[] arr = { 4, 5, 3, 7, 2 };
        int[] result = quickSort(arr);
        System.out.println(Arrays.toString(result));
    }

    static int[] quickSort(int[] arr) {

        List<Integer> left = new ArrayList<Integer>();
        List<Integer> right = new ArrayList<Integer>();
        List<Integer> equal = new ArrayList<Integer>();
        int p = arr[0];
        equal.add(p);
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > p)
                right.add(arr[i]);
            else if (arr[i] < p)
                left.add(arr[i]);
            else if (arr[i] == p)
                equal.add(arr[i]);
        }
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < left.size(); i++)
            res.add(left.get(i));
        for (int i = 0; i < equal.size(); i++)
            res.add(equal.get(i));
        for (int i = 0; i < right.size(); i++)
            res.add(right.get(i));
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> quickSort(vector<int> arr)
{
    vector<int> left, right, equal;
    int p = arr[0];
    equal.push_back(p);
    for (int i = 1; i < arr.size(); i++)
    {
        if (arr[i] > p)
            right.push_back(arr[i]);
        else if (arr[i] < p)
            left.push_back(arr[i]);
        else if (arr[i] == p)
            equal.push_back(arr[i]);
    }
    vector<int> res;
    for (int i = 0; i < left.size(); i++)
        res.push_back(left[i]);
    for (int i = 0; i < equal.size(); i++)
        res.push_back(equal[i]);
    for (int i = 0; i < right.size(); i++)
        res.push_back(right[i]);
    return res;
}

int main()
{
    int n = 5;

    vector<int> arr = {4, 5, 3, 7, 2};
    vector<int> result = quickSort(arr);

    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i];

        if (i != result.size() - 1)
        {
            cout << " ";
        }
    }
    return 0;
}