7-line quicksort to write in interviews (Python)
This is my go-to solution when asked this question in interviews. It\'s short, simple to write, very bug free, and looks very clean and pythonic. Writing this v
This is my go-to solution when asked this question in interviews. It\'s short, simple to write, very bug free, and looks very clean and pythonic. Writing this version of quicksort is very effective in communicating your understanding of the algorithm and its concepts to the interviewer.\n\nThe only tradeoff in the code is it uses a bit of extra space. You can always write the messier in-place solution as a followup.\n```\ndef quicksort(self, nums):\n    if len(nums) <= 1:\n        return nums\n\n    pivot = random.choice(nums)\n    lt = [v for v in nums if v < pivot]\n    eq = [v for v in nums if v == pivot]\n    gt = [v for v in nums if v > pivot]\n\n    return self.quicksort(lt) + eq + self.quicksort(gt)\n```\nRuntime: O(nlogn) expected, O(n^2) worst case.\nWith a proper choice of pivot (using the median of medians algorithm), the runtime can be reduced to strict O(nlogn).\nSpace: O(n) expected, O(n^2) worst case
['Sorting', 'Python']