We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Quicksort 2 - Sorting
  2. Discussions

Quicksort 2 - Sorting

Problem
Submissions
Leaderboard
Discussions

Sort 186 Discussions, By:

recency

Please Login in order to post a comment

  • patelmit7474
    4 months ago+ 1 comment

    Anyone else's output not matching even though it is partitioning and sorting the way it suppposed to?

    0|
    Permalink
  • patelmit7474
    4 months ago+ 0 comments

    **Java Solution: **

    static void quickSort(int[] ar, int start, int end) {
                if (start < end) {
                int pi = partition(ar, start, end);
                quickSort(ar, start, pi - 1);
                quickSort(ar, pi + 1, end);
                printArray(ar, start, end);
                }
    	    }
            
            static int partition(int[] ar, int start, int end) {
                int pivot = ar[start];
                int i = start + 1, j = end;
                
                while (i <= j) {
                    if (ar[i] > pivot && ar[j] < pivot) {
                        int temp = ar[i];
                        ar[i] = ar[j];
                        ar[j] = temp;
                    }
                    
                    while (i <= end && ar[i] < pivot) i++;
                    while (j > start && ar[j] > pivot) j--;
                }
                ar[start] = ar[j];
                ar[j] = pivot;
                return j;
            }
    
    0|
    Permalink
  • ravindravarma887
    5 months ago+ 0 comments

    How's this Quicksort implmentation if we're not doing partition in-place?

    This is my solution, it gives different result than what's expected for this question but this is much more optimal because we don't use any extra auxiliary space.

    def quickSort(arr, start, end):
        if(start < end):
            pIndex = partition(arr, start, end)
            quickSort(arr, start, pIndex - 1)
            quickSort(arr, pIndex + 1, end)
        if(len(arr[start: end + 1]) > 1):
            print(" ".join(arr[start: end + 1]))
    def partition(arr, start, end):
        pivot = arr[start]
        pIndex = start + 1
        for i in range(start + 1, end+1):
            if(arr[i] < pivot):
                arr[i], arr[pIndex] = arr[pIndex], arr[i]
                pIndex += 1
                
        arr[start], arr[pIndex-1] = arr[pIndex-1], arr[start]
        return pIndex - 1
        
    n = int(input())
    arr = input().split()
    quickSort(arr, 0, n-1)
    
    0|
    Permalink
  • ava_xiaohong_de1
    10 months ago+ 0 comments

    Use the Quicksort algorithm to sort the entire array

    def sorting(ar):

    if len(ar) <= 1:
        return ar
    
    left, equal, right = partition(ar)
    merging_arr = sorting(left) + equal + sorting(right)
    print (' '.join(str(e) for e in merging_arr))   
    
    return merging_arr
    

    def partition(ar):

    left, equal, right=[],[ar[0]],[]
    
    for elem in ar[1:]:
        if elem < ar[0]:
            left.append(elem)
        elif elem == ar[0]:
            equal.append(elem)        
        else:
            right.append(elem)
    
    return left, equal, right
    

    if name == 'main':

    n = input()
    
    ar = list(map(int,input().rstrip().split()))
    
    sorting(ar)
    
    1|
    Permalink
  • h2100050009
    12 months ago+ 0 comments

    C solution (not mine but I got it from below took too long me to scroll ) For a beginner like me who has just began data structures 2 weeks ago this question left me scratching my mind for past 2 hours T-T

    #include <stdio.h>
    #include <stdlib.h>
    
    void quickSort(int *ar, int size)
    {
        if(size > 1){
            int temp, pivot = ar[0], ub = size-1;
            for(int i = size-1; i >= 0; --i){
                if(ar[i] >= pivot){
                    temp = ar[i];
                    int j = i;
                    while(j < ub){//Variation of Insertion Sorting
                        ar[j] = ar[j+1];
                        ++j;
                    }
                    ar[ub--] = temp;
                }
            }
            ++ub;
            quickSort(ar, ub);
            quickSort(ar+ub+1, size-ub-1);
        
            //Output
            for(int i = 0; i < size; ++i){
                printf("%d ", ar[i]);
            }
            printf("\n");
        }
    }
    
    
    int main(void)
    {
        int N;
        scanf("%d", &N);
        int ar[N];
        
        for(int i = 0; i < N; i++){
            scanf("%d", &ar[i]); 
        }
        
        quickSort(ar, N);
        
        return 0;
    }
    
    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy