[GO] Python beginners organize quicksort

This is a memorandum

I'll really forget

Citation site

This time, I would like to introduce the sites I visited in order to organize them earlier.

-Algorithm reference -Trace reference

The algorithms themselves are slightly different for each, but since they are the same quicksort, we will organize them based on @ muijp's algorithm.

program

[@ Muijp's Quicksort](https://qiita.com/muijp/items/257e8b9b49d891137d56#%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3% 82% BD% E3% 83% BC% E3% 83% 88-quick-sort) has a random array program and debug output that was advised by @shiracamus the other day.

q_sort.py


def qSort(a):
    print(a)#For debugging
    if len(a) in (0, 1):
        return a

    p = a[-1]
    l = [x for x in a[:-1] if x <= p]
    r = [x for x in a[:-1] if x >  p]

    return qSort(l) + [p] + qSort(r)
a = r.sample(range(1,11),k=9)
qSort(a)
#output_____________________
[3, 7, 1, 6, 9, 8, 2, 10, 4]
[3, 1, 2]
[1]
[3]
[7, 6, 9, 8, 10]
[7, 6, 9, 8]
[7, 6]
[]
[7]
[9]
[]
>>[1, 2, 3, 4, 6, 7, 8, 9, 10]

Yeah, the program is too concise to understand.

Disassemble and think

The first thing to notice return qSort(l) + [p] + qSort(r) I think that. This is the part where small numbers (array) and large numbers (array) are placed on the right and left of "Pivot (cell of interest)" which is a feature of Quicksort.

Trace reference If you look at the gifs on this site

  1. Take the middle pivot
  2. Swap the small number on the left and the large number on the right in order from the outside
  3. Change the scanning range from minimum to pivot and bring the pivot to the center. You can see that is repeated.

However, in this program p = a[-1] As, taking the pivot to the last number And l = [x for x in a[:-1] if x <= p] r = [x for x in a[:-1] if x > p] So, I divide it into a number larger than the pivot and a number smaller than the pivot, and join them with return (calling the recurrence function).

the first if len(a) in (0, 1): return a Returns if the number of characters is one or less, it is returned as the return value of the recursive function.

Retrace

Based on the above, try tracing with the previous random number

#output_____________________
[3, 7, 1, 6, 9, 8, 2, 10, 4]
[3, 1, 2]
[1]
[3]
[7, 6, 9, 8, 10]
[7, 6, 9, 8]
[7, 6]
[]
[7]
[9]
[]
>>[1, 2, 3, 4, 6, 7, 8, 9, 10]

Array [3, 7, 1, 6, 9, 8, 2, 10, 4] Pivot p = 4 Small array l = {3,1,2} Large array r = {7,6,9,8,10} And disassemble image.png

Revive the small array, p=2 l={1}、r={3} And disassembly image.png Each one has been disassembled, so confirm

If you restart the large array, this time p is the maximum at 10, so l={7,6,9,8} 、r={} Is disassembled image.png Then subdivide all the numbers image.png Returned as combined data image.png It is.

at the end

This time it was almost plagiarized, but I realized how I didn't understand it. It was really nice to have such an opportunity.

Recommended Posts

Python beginners organize quicksort
Python beginners organize heapsort
Python beginners organize bubble sort
quicksort in python
Beginners practice Python
Python beginner's note
Python Beginner's Guide (Functions)
Python beginners touch Pytorch (3)
python textbook for beginners
Python Dictionary Beginner's Guide
Python beginners touch Pytorch (1)
Python beginners touch Pytorch (2)
Python Beginner's Guide (Introduction)
OpenCV for Python beginners
Organize types in Python
Quicksort an array in Python 3
Learning flow for Python beginners
About python beginner's memorandum function
Python3 environment construction (for beginners)
Organize your Python development environment
3 Reasons Beginners to Start Python
Python #function 2 for super beginners
Python Beginner's Guide (Variables / Arrays)
Basic Python grammar for beginners
100 Pandas knocks for Python beginners
Python for super beginners Python #functions 1
Python #list for super beginners
Implementation of quicksort in Python
~ Tips for beginners to Python ③ ~
Python
Python Exercise for Beginners # 2 [for Statement / While Statement]
Python for super beginners Python # dictionary type 1 for super beginners
Machine learning summary by Python beginners
Python #index for super beginners, slices
Typing automation notes by Python beginners
<For beginners> python library <For machine learning>
QuickSort
Python #len function for super beginners
Beginners use Python for web scraping (1)
# 2 Python beginners challenge AtCoder! ABC085C --Otoshidama
Run unittests in Python (for beginners)
Memorandum of beginners Python "isdigit" movement
Beginners use Python for web scraping (4) ―― 1
Python #Hello World for super beginners
Python for super beginners Python # dictionary type 2 for super beginners
python beginners tried to find out
Learn the basics of Python ① Beginners
INSERT into MySQL with Python [For beginners]
[Python] Minutes of study meeting for beginners (7/15)
Answer to AtCoder Beginners Selection by Python3
[Episode 2] Beginners tried Numeron AI with python
[Episode 3] Beginners tried Numeron AI with python
Memorandum of python beginners About inclusion notation
Let's put together Python for super beginners
[Episode 0] Beginners tried Numeron AI with python
[Episode 1] Beginners tried Numeron AI with python
10 Python errors that are common to beginners
[Python] Read images with OpenCV (for beginners)
[Part1] Scraping with Python → Organize to csv!
Organize data divided by folder with Python
WebApi creation with Python (CRUD creation) For beginners