This question is misleading and poorly specified. In quicksort the partition method does not get called recursively and the sorting is done in-place. What is described here is a version of merge sort, taking additional O(n) storage space. There's no way to pass this question with actual quicksort, because the order of the items in the sub-arrays does not get preserved.

Read a bit on quicksort on Wikipedia.

Additionally, the fact that the first item is selected as the pivot should be specified in the question, not expected to be inferred from the example.

Another well thought out challenge. I must say that QuickSort is rather a difficult topic. However, the explanations, the expected output and the exercise before this made it look easy. Again, an easy solution could be achieved by first tackling the previous exercise and following the instructions in this exercise carefully. The diagram on the expected output guides the logic behind the recursion.

The sort method - takes in an array and returns an array

1. If the array length < 2, do nothing it's already sorted.
2. If the array length = 2; check if first element is greater than the second element and swap.
3. If the array length > 2, i. partition the array into two ii. call sort method passing the left array iii. call sort method passing the right array iv. merger the left array with the partition and the right array in this other. iv. print the resulting sub array before every return v. return the sub array.

I must say that this is the most clearer instruction of all the challenges I have tackled so far. Could it be because quick sort is rather a problematic exercise?

When the problem gives the function declaration already, I tend to stick with it and not change it. You can solve this problem with the given vector parameter. Notice arr is passed in as a reference, so there is no need to return back another vector. The exit case can just be detected if size < 2, don't need to swap when size == 2. I tested with a swap, but it just gave me the same answer. Hope this helps anyone stuck on this problem.

[C++]

void quickSort(vector &arr) {

// Complete this function

int size = arr.size();
if (size < 2) {
    return;
}

vector <int> leftArray;
vector <int> rightArray;

int pivot = arr[0];

for (int i = 1; i < size; ++i) {
    if (arr[i] <= pivot) {
        leftArray.push_back(arr[i]);
    }
    else {
        rightArray.push_back(arr[i]);
    }
}
quickSort(leftArray);
quickSort(rightArray);

int index = 0;

// Copy left array back into the original array
for (unsigned int l = 0; l < leftArray.size(); ++l) {
    arr[index++] = leftArray[l];
    cout << leftArray[l] << " ";
}

// Copy the pivot between left & right arrays
arr[index++] = pivot;
cout << pivot << " ";

// Copy right array back into the original array
for (unsigned int r = 0; r < rightArray.size(); ++r) {
    arr[index++] = rightArray[r];
    cout << rightArray[r] << " ";
}
cout << endl;

}

Is this the right way to solve this challenge in Python, or can someone improve it?

def quick_sort(*ar):
    p, *a = ar
    first, last = [], []
    for i in a:
        if i < p:
            first.append(i)
        else:
            last.append(i)
    if len(first) > 1:
        first = quick_sort(*first)
        print(*first)
    if len(last) > 1:
        last = quick_sort(*last)
        print(*last)
    return first + [p] + last

n = int(input())
p, *a = map(int, input().split())
print(*quick_sort(p, *a))

I used a different partition function than the one you guys are using i think my output for first test case is

1 2 1 2 3 8 9 7 8 9 1 2 3 5 7 8 9. Just like Quicksort1-Partition which checks for variations in partition shouldn't this do the same?

Solution in JAVA :- public class Solution {

    static int partition(int ar[], int minpos, int maxpos)
    {
        int p = ar[minpos];
        ArrayList<Integer> leftlist = new ArrayList<Integer>();
        ArrayList<Integer> rightlist = new ArrayList<Integer>();

        for(int i = minpos+1 ; i <= maxpos; i++)
            {
               if(ar[i] > p)
                   rightlist.add(ar[i]);
               else
                   leftlist.add(ar[i]);
            }
        copy(leftlist,ar,minpos);
        int ppos = leftlist.size()+minpos;
        ar[ppos] = p;
        copy(rightlist,ar,ppos+1);

        return minpos + leftlist.size();
    }

     static void copy(ArrayList<Integer> list, int ar[], int startIdx)
     {
             for(int num : list)
            {
               ar[startIdx++] = num;      
            }
     }

    static void quickSort(int ar[], int minpos, int maxpos)
   {
        if(minpos >= maxpos)
            return;

       int pos = partition (ar,minpos,maxpos);

        quickSort(ar,minpos,pos-1);
        quickSort(ar,pos+1,maxpos);

        printArray(ar,minpos, maxpos);
   }

    static void quickSort(int[] ar) 
    {
        quickSort(ar,0,ar.length-1);
    }   

static void printArray(int[] ar,int start, int end) { for(int i = start; i <= end;i++) { System.out.print(ar[i]+" "); } System.out.println(""); }

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

}

I used JAVA.

import java.util.*; public class Solution {
static ArrayList quickSort(Integer[] ar) {

          int p=ar[0];
          ArrayList<Integer> left=new ArrayList<>();
          ArrayList<Integer> right=new ArrayList<>();
          ArrayList<Integer> equal=new ArrayList<>();

          for(int num:ar)
          {
              if(num==p)
                  equal.add(num);
              else if(num>p)
                  right.add(num);
                  else left.add(num);
          }

          if(left.size()>1)
              left=quickSort(left.toArray(new Integer[left.size()]));
          if(right.size()>1)
              right=quickSort(right.toArray(new Integer[right.size()]));

          left.addAll(equal);
          left.addAll(right);
          Integer array[]=left.toArray(new Integer[left.size()]);
          printArray(array);
          return left;

   }   

static void printArray(Integer[] ar) { for(int n: ar){ System.out.print(n+" "); } System.out.println(""); }

  public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
       int n = in.nextInt();
       Integer[] ar = new Integer[n];
       for(int i=0;i<n;i++){
          ar[i]=in.nextInt(); 
       }
       quickSort(ar);
   }    

}

C++;

//Quicksort 2 - Sorting
#include <iostream>
using namespace std;

int subFunc_quickSort_partition(int *arr, int startIndex, int endIndex){
    int pivot = arr[startIndex];
    int pivotIndex = startIndex;
    for(int i=startIndex+1 ; i<=endIndex ; i++){
        if(arr[i]<pivot){
            int tempNum = arr[i];
            for(int j=i ; j>pivotIndex ; j--)
                arr[j] = arr[j-1];
            arr[pivotIndex] = tempNum;
            pivotIndex++;
        }
    }

    return pivotIndex;
}

void func_quickSort(int *arr, int startIndex, int endIndex){
    if(startIndex>=endIndex)
        return;

    int pivotindex = subFunc_quickSort_partition(arr,startIndex,endIndex);

    func_quickSort(arr,startIndex,pivotindex-1);
    func_quickSort(arr,pivotindex+1,endIndex);

    for(int a=startIndex ; a<=endIndex ; a++)
        cout << arr[a] << " ";
    cout<<endl;
}

int main (){
    int arraySize = 0;
    cin >> arraySize;
    int *arr = new int[arraySize];
    for(int a=0 ; a<arraySize ; a++)
        cin >> arr[a];

    func_quickSort(arr,0,arraySize-1);

}

I have sorted the array however, I am a bit confused regarding the output. I didn't quite understand the meaning of the subarrays

I realised going through the discussions for this problem that my approach is a bit different to that being suggested by the others.

This being my first attempt at Quick Sort would appreciate constructive comments

import java.util.Iterator; import java.util.List; import java.util.Scanner; import java.util.Vector;

public class QuickSort2_Sorting {

static List<Integer> QuickSort(List<Integer> arr)
{

    int n=arr.size();

    List<Integer> left = new Vector<Integer>();
    List<Integer> right = new Vector<Integer>();
    int pivot=0;

    if(n<2)
    return arr;
    else
    {

        pivot = arr.get(0);

        Iterator<Integer> i = arr.iterator();
        int x =0;

        while(i.hasNext()){
            x = i.next();

            if(x > pivot)
            {
                right.add(x);

            }
            else if( x < pivot)
            {
                left.add(x);

            }

         }

    }


    left = QuickSort(left);

    right = QuickSort(right);


    left.add(pivot);
    left.addAll(right);


    printArray(left);

    return left;
}

static void printArray(List<Integer> ar) {
      for(int n: ar){
         System.out.print(n+" ");
      }
        System.out.println("");
   }

public static void main(String args[])
{
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    List<Integer> arr = new Vector<Integer>();

    for(int i=0;i<n;i++)
    {
        arr.add(scan.nextInt());
    }

    scan.close();

    QuickSort(arr);
}

}