912. sort an array

Given an array of integers nums, sort the array in ascending order. quick sort py

  • code
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:

        self.quickSort(nums, 0, len(nums)-1)
        return nums

    def quickSort(self, arr, left, right):
        mid = (left + right) // 2
        arr[mid], arr[right] = arr[right], arr[mid] # pick the mid as pivot every time
        if left < right:
            pivot = self.partition(arr, left, right)
            self.quickSort(arr, left, pivot-1)
            self.quickSort(arr, pivot+1, right)

    def partition(self, arr, left, right):
        i = left
        pivot = arr[right]
        for n in range(left, right):
            if arr[n] < pivot:
                arr[i], arr[n] = arr[n], arr[i]
                i += 1
        arr[right], arr[i] = arr[i], arr[right]
        return i

  • code
class Solution(object):
    def sortArray(self, nums):

        self.quickSort(nums, 0, len(nums) - 1)
        return nums
    def quickSort(self, nums, start, end):
        if start < end:
            # we get mid index for pivot element
            mid_idx = (start+end)//2 
            #we swap first and mid index element
            nums[start],nums[mid_idx] = nums[mid_idx],nums[start]
            p_index = self.partition(nums, start, end)
            #we need recursive calls left and right side
            self.quickSort(nums, start, p_index-1)
            self.quickSort(nums, p_index+1, end)
    def partition(self, nums, start, end):
        low = start + 1
        high = end
        pivot = nums[start]
        while True:
            # indicates we have already moved all the elements to their correct side of the pivot
            while low <= high and nums[high] >= pivot:
                high -= 1

            # Opposite process of the one above
            while low <= high and nums[low] <= pivot:
                low += 1

            if (low <= high):
                nums[low],nums[high] = nums[high],nums[low]
        nums[start], nums[high] = nums[high], nums[start]
        return high