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.
  1. Quicksort 2 - Sorting
  2. Discussions

Quicksort 2 - Sorting

Sort 187 Discussions, By:

  • edgarpescobar
     + 0 comments

    Python 3

    I think is the most elegant solution

    def quickSort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return  quickSort(less) + [pivot] + quickSort(greater)

  • patelmit7474
     + 1 comment

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

  • patelmit7474
     + 1 comment

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

  • ravindravarma887
     + 1 comment

    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)

  • ava_xiaohong_de1
     + 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)
Load more conversations