[PYTHON] Quicksort details and code examples

What is Quicksort?

Pivot (reference) the elements and place the remaining elements back and forth depending on whether they are larger or smaller than the pivot.

The work of deciding the pivot and arranging the elements arranged before and after this is repeated.

Confirm when the elements become one.

** ▼ When setting the first element to pivot ** 

Quicksort flow

1. Determine the pivot and sort it back and forth depending on whether it is larger or smaller than that value. The value and location of the pivot are fixed.
2. Perform process 1 again for the previous array.
3. Perform process 1 again for the rear array.
4. The pivot is fixed more and more in the processes of 2 and 3, and finally all the elements are fixed.

## When the leftmost is pivot

python

##Specify pivot and left + pivot+A function (quick) that creates an array sorted on the right_sort）
def quick_sort(arr):
  #Sorting ends when there is only one element (sorting is not required if there are less than two elements)
  if len(arr) <= 1 :
    return arr
  #Specify the value of pivot
  p = arr[0]

  #Performs the process of dividing based on pivot. div function
  arr1, arr2 = div(p, arr[1:])

  #Combine the divided arrays with reference to pivot.
  #Quick on the split array itself_Sort.
  return quick_sort(arr1) + [p] + quick_sort(arr2)



##A function that creates left and right arrays based on pivot(div)
def div(p, arr):
  #Define a variable to put the left and right arrays of pivot
  left, right=[], []

  for i in arr:
    #Store on the left if smaller than pivot
    if i < p:
      left.append(i)
    #If it is above pivot, store it on the right side
    else:
      right.append(i)

  #Output left and right arrays respectively
  return left, right

Intuitive and easy to understand compared to merge sort.

• Caution If the value on the far left is set to pivot, the amount of calculation will increase if the values are already arranged in descending order.

For this reason, it is recommended that pivot be determined randomly.

## Quicksort when pivot is randomly determined Use numpy's random.choice (array).

Change the pivot of the quick_sort function above as follows.

python

import numpy as np
  p = random.choice(arr)

quick_sort

import numpy as np

def quick_sort2(arr):
  #Sorting ends when there is only one element (sorting is not required if there are less than two elements)
  if len(arr) <= 1 :
    return arr

  #Specify the value of pivot
  p = random.choice(arr)

  #Performs the process of dividing based on pivot. div function
  arr1, arr2 = div(p, arr[1:])

  #Combine the divided arrays with reference to pivot.
  #Quick on the split array itself_Sort.
  return quick_sort(arr1) + [p] + quick_sort(arr2)