From a book that programmers can learn ... (Python): About sorting

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.

Problem: Quicksort C ++ answer code
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.

Self (borrowed Code) Python that sorts and returns the given array by quicksort

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

Return left only

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

From a book that programmers can learn ... (Python): About sorting
From a book that programmers can learn ... (Python): Pointer
From a book that programmers can learn (Python): Decoding messages
From a book that programmers can learn (Python): Find the mode
From a book that programmers can learn ... (Python): Review of arrays
From a book that programmers can learn (Python): Statistical processing-deviation value
From a book that programmers can learn (Python): Conditional search (maximum value)
From a book that programmers can learn (Python): Class declaration (public / private, etc.)
From a book that programmers can learn ... Collect small problem parts
From a book that programmers can learn: Verification of rune checksum (fixed length)
From a book that programmers can learn ... Verification of rune checksum (variable length) Part 2
From a book that programmers can learn: Converting characters that represent numbers to integer types
From a book that makes the programmer's way of thinking interesting (Python)
8 services that even beginners can learn Python (from beginners to advanced users)
About psd-tools, a library that can process psd files in Python
Try using APSW, a Python library that SQLite can get serious about
"Python Kit" that calls a Python script from Swift
I made a Docker image that can call FBX SDK Python from Node.js
Programmer's way of thinking is from XX book (Python)
"A book that understands Flask from scratch" Reading memo
Programmer's way of thinking is from XX book (Python)
A mechanism to call a Ruby method from Python that can be done in 200 lines
A memo that reads data from dashDB with Python & Spark
A Python program in "A book that gently teaches difficult programming"
python Condition extraction from a list that I often forget
A memorandum about correlation [Python]
A memorandum about Python mock
A Python program that aggregates time usage from icalendar data
A note about [python] __debug__
[Python] Make a graph that can be moved around with Plotly
I made a package that can compare morphological analyzers with Python
Make a Kindle book that images mathematical formulas from TeX files
Created a library for python that can easily handle morpheme division
I made a shuffle that can be reset (reverted) with Python
[Python algorithm] A program that outputs Sudoku answers from a depth-first search
[python] I made a class that can write a file tree quickly
Call a Python function from p5.js.
Touch a Python object from Elixir
Python: A Note About Classes 1 "Abstract"
About Python, from and import, as
python / Make a dict from a list.
A note about mock (Python mock library)
I created a template for a Python project that can be used universally
[Python] A program that finds a pair that can be divided by a specified value
A story about a beginner making a VTuber notification bot from scratch in Python
Extract lines that match the conditions from a text file with python
About "spleeter" that can separate vocals and musical instruments from music data
[Python] I made a utility that can access dict type like a path
I made a simple timer that can be started from the terminal
Build a Python virtual environment that anyone can understand September 2016 (pyenv + virutalenv)
I made a module PyNanaco that can charge nanaco credit with python
[Python] Creating a tool that can list, select, and execute python files with tkinter & about the part that got caught
A story about converting HTML to PDF with WeasyPrint + matplotlib and embedding graphs [Beginners learn python with a reference book]
Spiral book in Python! Python with a spiral book! (Chapter 14 ~)
[Python] A program that creates stairs with #
Send a message from Python to Slack
A Java programmer studied Python. (About type)
# 5 [python3] Extract characters from a character string
[Python] Sorting collection types as a reference
Create a deb file from a python package
[Python] Create a LineBot that runs regularly