Implementation of quicksort in Python

Code that generates a list of 100 integers with random numbers and quickly sorts them. I implemented it with a simple quicksort that does not use partitions.

Finally, a code to measure the execution time is attached.

quick_sort.py


from typing import List
import random
import time

def quick_sort(numbers: List[int]) -> List[int]:
    
    numbers_set = set(numbers)

    if len(numbers_set) <= 1:
        return numbers

    p1 = numbers[0]
    p2 = 0
    for i in range(len(numbers)):
        if numbers[i] != p1:
            p2 = numbers[i]
            break
    

    pivot = p1 if p1 > p2 else p2

    left_list = []
    right_list = []

    for i in range(len(numbers)):
        if numbers[i] < pivot:
            left_list.append(numbers[i])
        else:
            right_list.append(numbers[i])

    return quick_sort(left_list) + quick_sort(right_list)



if __name__ == "__main__":
    nums = [random.randint(0,100) for _ in range(100)]
    start = time.time()
    quick_sort(nums)
    elapsed_time = time.time() - start
    print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")   

Recommended Posts

Implementation of quicksort in Python
quicksort in python
Implementation of life game in Python
Implementation of original sorting in Python
RNN implementation in python
ValueObject implementation in Python
SVM implementation in python
Explanation of edit distance and implementation in Python
Quicksort an array in Python 3
Python implementation of particle filters
Neural network implementation in python
Overview of generalized linear models and implementation in Python
Variational Bayesian inference implementation of topic model in python
A reminder about the implementation of recommendations in Python
Pixel manipulation of images in Python
Sorting algorithm and implementation in Python
HMM parameter estimation implementation in python
Python implementation of self-organizing particle filters
Mixed normal distribution implementation in python
Implementation of login function in Django
Division of timedelta in Python 2.7 series
MySQL-automatic escape of parameters in python
Handling of JSON files in Python
Waveform display of audio in Python
Implementation of desktop notifications using Python
Python implementation of non-recursive Segment Tree
Implementation of Light CNN (Python Keras)
Law of large numbers in python
Implementation of Dijkstra's algorithm with python
Reversible scrambling of integers in Python
Quadtree in Python --2
Python in optimization
CURL in python
Conversion of string <-> date (date, datetime) in Python
Geocoding in python
Introduction of Python
SendKeys in Python
Check the behavior of destructor in Python
(Bad) practice of using this in Python
Meta-analysis in Python
Unittest in python
Output tree structure of files in Python
Display a list of alphabets in Python 3
Implementation module "deque" in queue and Python
Comparison of Japanese conversion module in Python3
It's an implementation of ConnectionPool in redis.py
Summary of various for statements in Python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
nCr in python
N-Gram in Python
Basics of Python ①
The result of installing python in Anaconda
Basics of python ①
Programming in python
Plink in Python
Constant in python
Copy of python
The basics of running NoxPlayer in Python