leetcode-python/sorting/quick_sort.py at master · joshydavid/leetcode-python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
Quick sort is a divide and conquer algorithm that picks an element as pivot and partitions the given array around the picked pivot.

Unlike merge sort, quick sort is not a stable sort. This means that the input order of equal elements in the sorted output may not be preserved. [("iPhone", 2025), ("iPad", 2025)] == [("iPad", 2025), ("iPhone", 2025)]
"""

import random


class Solution:
    def quick_sort(self, nums):
        if len(nums) <= 1:
            return nums

        pivot = random.choice(nums)
        left = [num for num in nums if num < pivot]
        middle = [num for num in nums if num == pivot]
        right = [num for num in nums if num > pivot]

        return self.quick_sort(left) + middle + self.quick_sort(right)

        # Time Complexity: O(n log n)
        # Space Complexity: O(n log n)


if __name__ == "__main__":
    solution = Solution()

    nums = [38, 27, 43, 3, 9, 82, 10]
    result = solution.quick_sort(nums)
    assert result == [3, 9, 10, 27, 38, 43, 82]
    print(result)
    print("Test Case Passed!")