[Python] bubble, insertion, selection, quick, merge, heap
in real life, we use\n\n    def sortArray(self, nums):\n        return sorted(nums)\n\n\nbut we are playing leetcode right now...\n\nclass Solution:\n    def so
in real life, we use\n```\n    def sortArray(self, nums):\n        return sorted(nums)\n```\n\nbut we are playing leetcode right now...\n```\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        # self.quickSort(nums)\n        # self.mergeSort(nums)\n        # self.bubbleSort(nums)\n        # self.insertionSort(nums)\n\t\t# self.selectionSort(nums)\n        self.heapSort(nums)\n        return nums\n    \n\t# @bubbleSort, TLE\n    def bubbleSort(self, nums):\n        n = len(nums)\n        for i in range(n):\n            for j in range(0, n - i - 1):\n                if nums[j] > nums[j + 1]:\n                    nums[j], nums[j + 1] = nums[j + 1], nums[j]\n                    \n\t# @insertionSort, TLE\n    def insertionSort(self, nums): \n        for i in range(1, len(nums)): \n            key = nums[i]\n            j = i-1\n            while j >= 0 and key < nums[j] : \n                    nums[j + 1] = nums[j] \n                    j -= 1\n            nums[j + 1] = key\n\t\t\n\t# @selectionSort, TLE\n\tdef selectionSort(self, nums):\n\t\tfor i in range(len(nums)):\n\t\t\t_min = min(nums[i:])\n\t\t\tmin_index = nums[i:].index(_min)\n\t\t\tnums[i + min_index] = nums[i]\n\t\t\tnums[i] = _min\n\t\treturn nums\n    \n\t# @quickSort\n    def quickSort(self, nums):\n        def helper(head, tail):\n            if head >= tail: return \n            l, r = head, tail\n            m = (r - l) // 2 + l\n            pivot = nums[m]\n            while r >= l:\n                while r >= l and nums[l] < pivot: l += 1\n                while r >= l and nums[r] > pivot: r -= 1\n                if r >= l:\n                    nums[l], nums[r] = nums[r], nums[l]\n                    l += 1\n                    r -= 1\n            helper(head, r)\n            helper(l, tail)\n\n        helper(0, len(nums)-1)\n        return nums\n     \n\t# @mergeSort\n    def mergeSort(self, nums): \n        if len(nums) > 1: \n            mid = len(nums)//2\n            L = nums[:mid] \n            R = nums[mid:] \n\n            self.mergeSort(L)\n            self.mergeSort(R)\n\n            i = j = k = 0\n\n            while i < len(L) and j < len(R): \n                if L[i] < R[j]: \n                    nums[k] = L[i] \n                    i+=1\n                else: \n                    nums[k] = R[j] \n                    j+=1\n                k+=1\n \n            while i < len(L): \n                nums[k] = L[i] \n                i+=1\n                k+=1\n\n            while j < len(R): \n                nums[k] = R[j] \n                j+=1\n                k+=1\n   \n   # @heapSort\n    def heapSort(self, nums):\n        def heapify(nums, n, i): \n            l = 2 * i + 1\n            r = 2 * i + 2\n\t\t\t\n            largest = i\n            if l < n and nums[largest] < nums[l]: \n                largest = l \n\n            if r < n and nums[largest] < nums[r]: \n                largest = r \n\n            if largest != i: \n                nums[i], nums[largest] = nums[largest], nums[i]\n                \n                heapify(nums, n, largest)\n                \n        n = len(nums) \n\n        for i in range(n//2+1)[::-1]: \n            heapify(nums, n, i) \n\n        for i in range(n)[::-1]: \n            nums[i], nums[0] = nums[0], nums[i]\n            heapify(nums, i, 0) \n```\n\n---\nSort Objects:\n\n[Pyhon] \n```python\nclass Node:\n    def __init__(self, val):\n        self.val = val\n\n    def __cmp__(self, other):\n        if self.val < other.val:\n            return -1\n        elif self.val > other.val:\n            return 1\n        else:\n\t\t\treturn 0\n\nclass Solution(object):\n    def sortArray(self, nums):\n        nodes = [Node(n) for n in nums]\n        return [node.val for node in sorted(nodes)]\n```\n\n[Pyhon3] notice, in python3, we don\'t have `__cmp__(self, other)` any more\n```python\nclass Node:\n    def __init__(self, val):\n        self.val = val\n\t\n\t# lt means less than, le means less or equal than etc.\n    def __lt__(self, other):\n        return self.val < other.val\n    # incase you need more logic\n    # def __le__(self, other):\n    #     return self.val <= other.val\n    # def __eq__(self, other):\n    #     return self.val == other.val\n    # def __ne__(self, other):\n    #     return self.val != other.val\n    # def __gt__(self, other):\n    #     return self.val > other.val\n    # def __ge__(self, other):\n    #     return self.val >= other.val\n\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        nodes = [Node(n) for n in nums]\n        return [node.val for node in sorted(nodes)]\n```\n
[]