Quicksort 1 Partition Hackerrank

The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with an average case performance of O(n²). In these next few challenges, we’re covering a divide-and-conquer algorithm called Quicksort (also known as Partition Sort).

Step 1: Divide
Choose some pivot element, p, and partition your unsorted array, ar, into three smaller arrays: left, right, and equal, where each element in left<p, each element in right>p, and each element in equal=p.

Challenge
Given ar and p=ar[0], partition ar into left, right, and equal using the Divide instructions above. Then print each element in left followed by each element in equal, followed by each element in right on a single line. Your output should be space-separated.

Note: There is no need to sort the elements in-place; you can create two lists and stitch them together at the end.

Input Format

The first line contains n (the size of ar).
The second line contains n space-separated integers describing ar (the unsorted array). The first integer (corresponding to ar[0]) is your pivot element, p.

Constraints

1<=n<=1000
-10000<=x<=10000 x{ar}
All elements will be unique.
Multiple answers can exist for the given test case. Print any one of them.

Output Format

On a single line, print the partitioned numbers (i.e.: the elements in left, then the elements in equal, and then the elements in right). Each integer should be separated by a single space.
Sample Input

5
4 5 3 7 2

Sample Output

3 2 4 5 7

Solution

#!/bin/python

# Head ends here
def partition(ar):
    pivot = ar[0]
    l = len(ar)
    
    start_index = 0
    end_index = l-1
    new_ar = []
    
    for i in range(1,l):
        if ar[i] <= pivot:
            new_ar.append(ar[i])
    new_ar.append(pivot)
    for i in range(1,l):
        if ar[i] > pivot:
            new_ar.append(ar[i])
        
    print '%s' % ' '.join(map(str, new_ar))
    return ""

# Tail starts here

m = input()
ar = [int(i) for i in raw_input().strip().split()]
partition(ar)

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
void partition(vector <int>  ar) {
   int p=ar[0];
    vector <int> l, r;
    for(int i=0; i<ar.size(); i++) {
        int x=ar[i];
       if (p>ar[i])
        l.push_back(x); 
        else if(p<ar[i])
        r.push_back(x); 
    }
    if(!l.empty()){
    for (int x = 0; x != l.size(); x++)
        cout<<l[x]<<" ";}
        cout<<p<<" ";
     for (int x = 0; x != r.size(); x++)
    cout<<r[x]<<" ";
    
}
int main(void) {
   vector <int>  _ar;
   int _ar_size;
   cin >> _ar_size;
    
     for(int _ar_i=0; _ar_i<_ar_size; _ar_i++) {
        int _ar_tmp;
        cin >> _ar_tmp;
        _ar.push_back(_ar_tmp); 
    }

   partition(_ar);
   
   return 0;
}

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

/* Head ends here */
void partition(int ar_size, int *  ar)
{
    int left[ar_size];
    int right[ar_size];
    int pivot=ar[0];
    int j,k=0;
    for(int i=1;i<ar_size;i++)
    {
       if(ar[i]<pivot)
       {
           left[j]=ar[i];
           j++;
       }
       else
       {
           right[k]=ar[i];
           k++;
       }
    }
    //j=0;k=0;
    for(int i=0;i<j;i++)
    {
           ar[i]=left[i];
    }
    ar[j]=pivot;
    for(int i=0;i<k;i++)
    {
           ar[i+j+1]=right[i];
    }
    for(int i=1;i<=ar_size;i++)
    {
           printf("%d ",ar[i]);
    }
}

/* Tail starts here */
int main() {
   
   int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) { 
   scanf("%d", &_ar[_ar_i]); 
}

partition(_ar_size, _ar);
   
   return 0;
}

/* Head ends here */
import java.util.*;
public class Solution {
    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(); 
           }
           partition(ar);
           printArray(ar);
    }
    static void printArray(int[] ar) {
         for(int n: ar){
            System.out.print(n+" ");
         }
           System.out.println("");
    }
    static void partition(int[] ar) {
        int p=ar[0];
        int[] copy=Arrays.copyOf(ar, ar.length);
        int c=0;
        for(int i=1;i<ar.length;i++){
            if(copy[i]<=p){
                ar[c]=copy[i];
                c++;
            }
        }
        ar[c]=p;
        c++;
        for(int j=0;j<ar.length;j++){
            if(copy[j]>p){
                ar[c]=copy[j];
                c++;
            }
        }
    }   
}