Last time Question to find the maximum value ** for a given value ** as a conditional search (There is an answer, but (sweat) is studied in Python I wrote it afterwards, but this time *** sort *** is explained and C ++ code is written, I thought that it was Python as usual, but I could not fix it by myself, it was posted by google As a memorandum to the code that is.
int compareFunc(const void * voidA, const void * voidB) {
int * intA = (int *)(voidA);
int * intB = (int *)(voidB);
return *intA - *intB;
}
const int ARRAY_SIZE = 10;
int intArray[ARRAY_SIZE] = {87,28,100,78,84,98,75,70,81,68};
qsort(intArray, ARRAY_SIZE, sizeof(int), compareFunc);
It was implemented in the qsort function.
Reference site → Quick Sort
test35.py
#!/usr/bin/env python
#coding:utf-8
def quicksort(seq):
if len(seq) < 1: #Returns itself if the given seq array is less than one
return seq
pivot = seq[0] #seq array to pivot[0]Substitute the th * When recursed, the leftmost array th is assigned to pivot
left = [] #left array Created to accumulate more and more "I wonder if the understanding here is different"
right = [] #right array same
for x in range(1, len(seq)): #Repeat for lengths from 1 excluding 0 in the seq sequence
if seq[x] <= pivot: #First seq sequence[1]Is smaller than pivot?
left.append(seq[x]) #If it is small, store it in the right left array of the array in the center of pivot
else:
right.append(seq[x]) #If it is large, store it in the left right array of the array in the center of pivot.
left = quicksort(left) ###Assigning the stored left array to the left variable
right = quicksort(right) ###Same as above
foo = [pivot] ###* The problem is here, but pivot is an array that is called recursively.[0]Since it is the second value, is it a collection of it? ??
return left + foo + right
seq = [87,28,100,78,84,98,75,70,81,68]
mx = quicksort(seq)
print(mx)
・ ・ ・(Terminal execution result)
>>> from test35 import quicksort
[28, 68, 70, 75, 78, 81, 84, 87, 98, 100]
>>>
Since it was too difficult to understand, I will check the inside with a print statement in the pivot assignment part, change the *** return part ***, execute it and check what is returned
test35.py
#!/usr/bin/env python
#coding:utf-8
def quicksort(seq):
if len(seq) < 1:
return seq
pivot = seq[0]
print(pivot)
left = []
right = []
for x in range(1, len(seq)):
if seq[x] <= pivot:
left.append(seq[x])
else:
right.append(seq[x])
left = quicksort(left)
right = quicksort(right)
foo = [pivot]
#return left + foo + right
return left
seq = [87,28,100,78,84,98,75,70,81,68]
mx = quicksort(seq)
print(mx)
・ ・ ・(Execution result)
>>> from test35 import quicksort
87
28
78
75
70
68
84
81
100
98
[]
>>>
Yeah, why? ?? I'm sure I'm not storing it on the left[87,28,100 ...]And so on
I was expecting it. The pivot part is printed first, but I can understand it somehow.
pivot is of the given array[0]Since the second element is assigned, it comes out as it is.
I thought this was strange and tried shifting with return foo + right, but Results only
・ ・ ・(Execution result)
>>> from test35 import quicksort
[87, 100]
>>>
Oh, maybe the last given sequence is back? What is pivot? Mystery is.
Finally, when I try with return foo, Results only
>>> from test35 import quicksort
[87]
>>>
Yeah, after all the last given array[0]Only the second element is returned.
It was explained like this on the reference site.
This is an implementation example that sorts the list in ascending order. The pivot is the first element of the list, the elements with lower values are stored in the left list, the elements with higher values are stored in the right list, and the list is finally combined around the pivot.
I understand the output result as advised in the comments. I'm sorry for all the questions.
Recommended Posts