Quicksort an array in Python 3

Introduction

Happy New Year 2020, everyone. My name is ryuichi69.
I wrote this sentence today after practicing the output and explanation of the algorithm. To be honest, it is difficult to write in an easy-to-understand manner, and if there are any parts that are difficult to understand in the explanation, omissions in requirements, etc., please contact us.

Quicksort

Overview

First, sorting means sorting the elements of an array in ascending or descending order. There are many types of

sorting methods, but quicksort is to sort by subdividing into an array of larger ones and an array of smaller ones starting from the reference value of the array. It is a method to go .

Quicksort example

For example, if you have an array a = [5,6,3,1,8], consider quicksorting it in ascending order. Furthermore, the median value in the array is used as the reference value.

Here, the median value of the elements of array a is 3. With this 3 as the boundary, the elements smaller than 3 are divided into two in half, such as blue below and the elements larger than 3 are yellow below. Furthermore, as shown in the second division in the figure below, the array is recursively divided in half, and the recursion is stopped when the number of elements in the array becomes one. Finally, it is completed by integrating into one array.

sort.png

Here is a summary of the implementation procedure.

Implementation procedure
  1. Find the median m (reference value) of element e in array a [i].
  2. Write a process to terminate recursion when the number of elements in the array after division becomes one (recursion stop condition).
  3. For each element element of the array. If a [i] m, store the element in the array right.
  4. The above 1 and 2 are recursively executed for the array left and the array right.

    Example Let

    n be a natural number and i be an integer satisfying 0 ≤ i ≤ (n-1). At this time, sort the array a [i] with n elements in ascending order by quicksort.

    Constraints
    1. 1≦n≦10
    2. 1≦a[i]≦10
    Input

    a = [7,3,10,5,9,1,6,4,8,2]

    Output

    [1,2,3,4,5,6,7,8,9,10]

    Program

    The source code is @ suecharo's " Sort algorithm and implementation in Python --Qiita It is based on the quick sort of ". I didn't know how to sort the array in two, so I cheated.

    quickSort.py

    
import os
import statistics

def quickSort(arr):

    #An array of elements smaller than the median of the array
    left = []

    #An array of elements larger than the median of the array
    right = []

    #Recursion stop condition
    #Stop when the number of elements is 1 or less after recursively dividing the array
    if len(arr) <= 1:
        return arr

    #Median of array(Median)To get
    median = int(statistics.median(arr))

    #A variable for counting the number of medians contained in an array
    medianFlg = 0

    for element in arr:
        #Array elements(element)Is less than the median
        #Store the value in the array left
        if element < median:
            left.append(element)
        #Array elements(element)Is greater than the median
        #Store the value in the array right
        elif element > median:
            right.append(element)
        else:
        #If element is the median of the array
        #Flag as many as the median value added to the return value+1 Continue
            medianFlg += 1

    #If you want to see how the array is divided,
    #It is good to check with print at this timing
    # print(left)
    # print(right)

    #Recursion is performed for each array left and array right
    #Divide the array into smaller arrays
    left = quickSort(left)
    right = quickSort(right)

    #Array left, median[median], Returns a concatenation of the array right
    return left + [median] * medianFlg + right

#for test
if __name__ == "__main__":

    print(quickSort([7,3,10,5,9,1,6,4,8,2]))

    Recommended Posts