I'll really forget
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.
[@ 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.
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
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.
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.
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