Quick Sort

The algorithm is similar to the bubble sort algorithm, which is based on the idea of exchange sort. The quicksort algorithm improves the bubble sort algorithm and has higher execution efficiency.

Quicksort algorithm

  • The array is first divided into left and right parts by a pivot chosen at random and with no limit
  • Place the data set greater than the bounding value to the right of the array, and the data set less than the bounding value to the left of the array.
  • Then the data on the left and right can be sorted independently, and the data on the left can be divided into left and right parts by taking a boundary value
  • Repeat the above process, and you can see that this is a recursive definition. After recursively ordering the left side, recursively ordering the right side. When the left and right parts of the data are sorted, the entire array is sorted.

The basic idea

  • The idea of divide and conquer is to divide a problem into subproblems, recursively dividing the array until the problem is simple enough to solve

  • First, select an element in the array as pivot and in this case choose 4 as pivot
  • We then set two Pointers to each side of the array
  • I’m going to start from the left and move the left pointer to 6 because 6 is bigger than 4 so I’m going to switch 6 and 4

  • Next, start moving the right hand pointer from right to left
  • When we get to 3 and we see that 3 is less than 4, we need to make sure that the element on the right is greater than 4 so we swap 3 and 4.
  • After the exchange, move the left pointer to move the left pointer to the right one position
  • Since 5 is greater than 4, we have to swap 4 and 5

  • And then I move the right pointer again, and I move it one place to the left to get to 1, which is less than 4 again so I keep swapping
  • When the exchange is completed, move the left pointer again and find that the pointer overlaps in a position this time, which ends the iteration

demo

  • Choose 2 for pivot as the standard value
  • We then place a pointer to each end of the array, and the two Pointers line up against each other
  • First we move the right pointer to the left, and when we move it to a value greater than or equal to the standard value, which is the pivot value, we move it further

  • When starting from the right, the pointer finds a value smaller than the standard value and stops
  • And then the left hand pointer starts looking for something that’s greater than the standard value, so 2 is equal to the standard value and we go ahead and we come in 5, 5 is greater than 2 so we go from the left hand pointer and we stop at 5
  • Then determine whether the two Pointers point to the same location

  • Once the swap is complete, it is now the turn to begin moving the right hand pointer, which continues to move forward one position, at which point the two Pointers overlap
  • We then swap the values of 2 and the two pointer positions for the first iteration

The array is now split into two parts by 2 pivot, where all the data elements to the left of 2 are less than 2 and all the data elements to the right of 2 are greater than 2

Time complexity

  • The worst case is O(n2)O(n^2)O(n2).
  • Optimal or average O(nlog⁡(n))O(n\log(n))O(nlog(n))
class Solution:

    def quickSort(self,nums,left,right) :
        if (left >= right):
            return
        p = nums[left]
        i = left
        j = right
        while(i ! = j):while (j > i) and nums[j] > p:
                j -= 1
            nums[i],nums[j] = nums[j],nums[i]
            while (i < j) and nums[i] <= p:
                i += 1
            nums[i],nums[j] = nums[j],nums[i]
        self.quickSort(nums,left,i-1)
        self.quickSort(nums,i+1,right)
        # print(nums)
        
    def quickArraySort(self,nums) :
        left = 0
        right = len(nums) - 1
        self.quickSort(nums,left,right)

Copy the code