Quicksort 2 Sorting Hackerrank problem solution

Quicksort 2 Sorting Hackerrank

In the previous challenge, you wrote a partition method to split an array into two sub-arrays, one containing smaller elements and one containing larger elements than a given number. This means you ‘sorted’ half the array with respect to the other half. Can you repeatedly use partition to sort an entire array?

Guideline
In Insertion Sort, you simply went through each element in order and inserted it into a sorted sub-array. In this challenge, you cannot focus on one element at a time, but instead must deal with whole sub-arrays, with a strategy known as “divide and conquer”.

When partition is called on an array, two parts of the array get ‘sorted’ with respect to each other. If partition is then called on each sub-array, the array will now be split into four parts. This process can be repeated until the sub-arrays are small. Notice that when partition is called on just one of the numbers, they end up being sorted.

Can you repeatedly call partition so that the entire array ends up sorted?

Print Sub-Arrays
In this challenge, print your array every time your partitioning method finishes, i.e. whenever two subarrays, along with the pivot, are merged together.

  • The first element in a sub-array should be used as a pivot.
  • Partition the left side before partitioning the right side.
  • The pivot should be placed between sub-arrays while merging them.
  • Array of length 1 or less will be considered sorted, and there is no need to sort or to print them.
  • Note
    Please maintain the original order of the elements in the left and right partitions while partitioning around a pivot element.

    For example: Partition about the first element for the array A[]={5, 8, 1, 3, 7, 9, 2} will be {1, 3, 2, 5, 8, 7, 9}

    Input Format
    There will be two lines of input:

    n- the size of the array
    ar- the n numbers of the array

    Output Format
    Print every partitioned sub-array on a new line.

    Constraints

    1<=n<=1000 -10000<=x<=10000 x{arr} Each number is unique. Sample Input

    7
    5 8 1 3 7 9 2

    Sample Output

    2 3
    1 2 3
    7 8 9
    1 2 3 5 7 8 9

    Explanation
    This is a diagram of Quicksort operating on the sample array:
    https://i1.wp.com/s3.amazonaws.com/hr-challenge-images/quick-sort/QuickSort.png?resize=474%2C659&ssl=1

    Task
    The method quickSort takes in a parameter, ar, an unsorted array. Use the Quicksort algorithm to sort the entire array.

    Solution
    # python 3
    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))
    #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;
    
    /* Head ends here */
    void quickSort(vector <int>  ar) {
        
        if(ar.size()<=1) return;
        int p=ar[0];
         vector<int> A,B;
        for(int i=0;i<ar.size();i++)  {
            if(ar[i]<p) A.push_back(ar[i]);
            else if(ar[i]>p) B.push_back(ar[i]);
                   
        }
        quickSort(A);
        quickSort(B);
        sort(A.begin(),A.end());
        sort(B.begin(),B.end());
        for(int i=0;i<A.size();i++) ar[i]=A[i];
        for(int i=0;i<B.size();i++) ar[i+A.size()+1]=B[i];
        ar[A.size()]=p;
        
        for(int i=0;i<ar.size();i++) cout<<ar[i]<<" ";
        cout<<endl;
        
            
    }
    
    
    /* Tail starts here */
    int main() {
       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); 
    }
    
    quickSort(_ar);
       
       return 0;
    }
    import java.util.*;
    public class Solution {
           
        static void quickSort(int[] ar) {
            quicksort(ar,0,ar.length);
        }
        static void quicksort(int ar[],int st,int en){
            if(st>=en){
                return;
            }
            else{
                int pos=partition(ar,st,en);
               
                quicksort(ar,st,pos);
                quicksort(ar,pos+1,en);
                if(st!=en-1)
                 printArray(ar,st,en);
            }
        }
        static int partition(int[] ar,int st,int en) {
        	if(st==en)
        		return st;
            int p=ar[st];
            ArrayList<Integer> leftList=new ArrayList<Integer>();
            ArrayList<Integer> rightList=new ArrayList<Integer>();
            for(int i=st+1;i<en;i++){
                if(ar[i]>p){
                    rightList.add(ar[i]);
                }
                else{
                    leftList.add(ar[i]);
                }
            }
            copy(leftList,ar,st);
            ar[st+leftList.size()]=p;
            copy(rightList,ar,st+leftList.size()+1);
            //printArray(ar,st,en);
            return st+leftList.size();
        }   
        static void copy(ArrayList<Integer> list,int[] ar,int startIdx){
            for(int num:list){
                ar[startIdx++]=num;
            }
        }
    
    /* Tail starts here */
     
     static void printArray(int[] ar,int st,int en) {
             for(int i=st;i<en;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);
           }    
       }
    

    A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

    Leave a reply:

    Your email address will not be published.