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

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Quicksort 2 - Sorting
  2. Discussions

Quicksort 2 - Sorting

Problem
Submissions
Leaderboard
Discussions

    You are viewing a single comment's thread. Return to all comments →

  • ravindravarma887
    7 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
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy