[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

Revive the small array, p=2 l={1}、r={3} And disassembly 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 Then subdivide all the numbers Returned as combined data 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.