Sort 186 Discussions, By:

4 months ago+ 1 comment

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

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;
        }

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)

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)

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;
}

Load more conversations