A memo that I wrote a quicksort in Python

I wrote a note for myself about Quicksort.

What is quicksort?

--A high-speed sorting algorithm based on the divide-and-conquer method that can handle large data sizes. --Computational complexity is O (nlogn) --Because there are logn layers and the amount of calculation for each layer is O (n). --Unstable sorting that changes the order of the same values when sorting --No need for memory to temporarily store data



def partition(A, p, r):
    x = A[r-1]
    i = p-1
    for j in range(p, r-1):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r-1] = A[r-1], A[i+1]
    return i+1
n = int(input())
A = list(map(int, input().split()))

def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q)
        quick_sort(A, q+1, r)
    return A
print(quick_sort([3, 1, 10, 2.5, 11, 3, 21,4, -1], 0, 9))
# [-1, 1, 2.5, 3, 3, 4, 10, 11, 21]

The above algorithm has a constant selection of criteria (the last value), so it may be inefficient depending on the data sequence. Computational complexity may be O (n ^ 2) The recursion may be too deep and an error may occur Therefore, it is necessary to devise ways to randomly select the criteria, select the median, and so on.


Sort algorithm and implementation in Python

Recommended Posts

A memo that I wrote a quicksort in Python
I wrote a class in Python3 and Java
[Memo] I tried a pivot table in Python
I wrote python in Japanese
A memo that I touched the Datastore with python
I wrote Fizz Buzz in Python
I wrote the queue in Python
I wrote the stack in Python
I tried "a program that removes duplicate statements in Python"
I wrote a script that splits the image in two
quicksort in python
I made a payroll program in Python!
I created a password tool in Python.
A memo that handles double-byte double quotes in Python regular expressions
[Python] A memo that I tried to get started with asyncio
I wrote a function to load a Git extension script in Python
I wrote a script to extract a web page link in Python
I wrote a code to convert quaternions to z-y-x Euler angles in Python
I made a web application in Python that converts Markdown to HTML
I want to create a window in Python
I tried playing a typing game in Python
[Python] I wrote a simple code that automatically generates AA (ASCII art)
A program that removes duplicate statements in Python
I wrote "Introduction to Effect Verification" in Python
A memo about writing merge sort in Python
I made a Discord bot in Python that translates when it reacts
I wrote a design pattern in kotlin Prototype
I tried to develop a Formatter that outputs Python logs in JSON
[Python] I forcibly wrote a short Perlin noise generation function in Numpy.
I tried adding a Python3 module in C
[IOS] I made a widget that displays Qiita trends in Pythonista3. [Python]
I wrote a Japanese parser in Japanese using pyparsing.
I wrote FizzBuzz in python using a support vector machine (library LIVSVM).
I made a Caesar cryptographic program in Python.
I wrote a tri-tree that can be used for high-speed dictionary implementation in D language and Python.
I wrote a graph like R glmnet in Python for sparse modeling in Lasso
I tried to create a class that can easily serialize Json in Python
[Fundamental Information Technology Engineer Examination] I wrote a linear search algorithm in Python.
I want to create a priority queue that can be updated in Python (2.7)
I registered PyQCheck, a library that can perform QuickCheck with Python, in PyPI.
[Beginner] What happens if I write a program that runs in php in Python?
Note that I understand the least squares algorithm. And I wrote it in Python.
I wrote a PyPI module that extends the parameter style in Python's sqlite3 module
I made a familiar function that can be used in statistics with Python
In Python, I made a LINE Bot that sends pollen information from location information.
I want to embed a variable in a Python string
I want to easily implement a timeout in python
I wrote a design pattern in kotlin Factory edition
I wrote a design pattern in kotlin Builder edition
I want to write in Python! (2) Let's write a test
I wrote a design pattern in kotlin Singleton edition
I made a VM that runs OpenCV for Python
I wrote a design pattern in kotlin Adapter edition
I tried to implement a pseudo pachislot in Python
I wrote a design pattern in kotlin, Iterator edition
I want to randomly sample a file in Python
I want to work with a robot in python.
What's in that variable (when running a Python script)
In Python, create a decorator that dynamically accepts arguments Create a decorator
I made a prime number generation program in Python 2
[Python, ObsPy] I wrote a beach ball with Matplotlib + ObsPy