[PYTHON] Quicksort without using sort
Good evening! (^^)! Yesterday I was trying to put my child to sleep I fell asleep as it was (laughs).
Now, let's sort in ascending order with Quicksort. This was another interesting idea. This time we will use while. I wrote a simple guy as a review.
test.py
x = 10
pc = 5
# x >If it is a pc, go inside while and execute the process
# !(x > pc)Then the while statement is pass!
while x > pc:
x -= 1
print(x)
print("result is ",x)
As you can see, as long as x> pc, it goes around in the while statement, X = x -1 is executed each time. After that, when x = 6, I put it in the while statement, Since x-= 1 is set in the processing inside, the relationship of x> pc is broken because x = 5 is set. In the next process, you have to exit the while statement. .. Just in case, I will post the execution result.
Execution result.py
9
8
7
6
5
result is 5
From the above, the miso of the while statement is as long as it corresponds to the conditional statement. The point is that the process can be repeated.
Why do you use this? That's the story. Let's get into the main subject (Remember while will come up later).
This time we will use this array X.
Whatever the median value in this array, I would like to sort by this one.
?? ?? ?? What do you compare with? ?? ??
Yes, I'm sorry.
Compare the leftmost value with the median.
For the time being, 1 vs. 5 The median value of 5 is clearly larger.
Then next.
8 vs. 5! This is obviously bigger than 8.
Yes Stop !!.
Finding a value greater than the median of First step ends here.
Second step works to find ** less than the median ** from the right edge.
Then let's go from the end.
5 vs. 9 !
Stay is okay. Next!
5 vs. 3 !
The median is larger, isn't it?
It's OK. I found.
Step 2 is finished.
The next step is to flip the values found in Step 1 and Step 2 respectively.
- Step 1: Find a value ** greater than the median **
- Step 2: Find a value ** smaller than the median **
The image is here.
I made a deficit after the change, but what about?
You can sort it like that, it's important, atmosphere (laughs)
So what do you do next?
Repeat Step 1 and Step 2. However, Lptr + = 1, Rptr-= 1.
Yes, try to get closer to the median and repeat the same thing.
????why?
Well, well, let's do it.
Specifically, X [2] vs X [4] and X [4] vs X [6].
X [2] vs X [4] is bingo, but in the case of X [4] vs X [6],
Now that X [4] <X [6] holds, execute the following X [4] vs X [** 5 **].
Now it's time to exchange (laughs)
All values to the left of the median 5 are less than 5,
An array greater than 5 is completed to the right of the median.
Let's drop the movement so far into the code. For example, the value that goes from the left side by the median is x [Lptr], What about the median argument from the right as x [Rptr]?
- Lptr = Left pointer / Rptr = Right pointer No sense (laughs) !?
test.py
#Array
x = [1,8,7,4,5,2,6,3,9]
#Center pointer
cen = len(x)//2
Lptr = 0
Rptr = len(x)-1
# x[Lptr]Pointer Lptr increments as long as is less than the median
while x[Lptr] < x[cen]:
Lptr += 1
# x[Rptr]The pointer Rptr is a decrement as long as is greater than the median
while x[cen] < x[Rptr]:
Rptr -= 1
#Just in case, Lptr<Trigger to be Rptr
if Lptr < Rptr:
#Turn the value over
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
Let's run it.
#Before execution
#[1,8,7,4,5,2,6,3,9]
#After execution
[1,3,7,4,5,2,6,8,9]
That? 3 and 8 just flipped over (laughs) Really.
Looking for values greater than / less than the median You can only express the work of turning over once in the above. If the above description is while Lptr <Rptr, as long as this relationship is maintained It repeats the above description (remember! Explanation of while at the beginning !!).
test.py
x = [1,8,7,4,5,2,6,3,9]
cen = len(x)//2
Lptr = 0
Rptr = len(x)-1
#Pointer position Lptr<As long as you maintain the Rptr relationship
#Continues processing the contents of the while.
while Lptr < Rptr:
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
if Lptr < Rptr:
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
#When the work of turning over is completed, do the following work
#Let's start the next comparison.
Lptr += 1
Rptr -= 1
print(x)
The execution result is as follows.
Execution result.py
#Before execution
#[1,8,7,4,5,2,6,3,9]
[1,3,2,4,5,7,6,8,9]
Yeah! (^^)! Less than 5 to the left of the median 5 The value to the right of the median 5 was greater than 5 (* ´ 艸 ｀) What do you do? Next (laughs)
First, after performing the above processing Where did Lptr and Rptr arrive?
test.py
while Lptr < Rptr:
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
Since Lptr + = 1 when Lptr = 3, Lptr = 4 When Rptr = 5, Rptr-= 1, so Rptr = 4 Lptr = Rptr = 4, and Lptr <Rptr, which was the condition of the while statement, became This will break it, so exit the while statement. Just in case, let's do it.
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 4 Rptr = 4
I see. For the time being, let's make a diagram.
How about an additional little Izil as below?
test.py
x = [1,8,7,4,5,2,6,3,9]
cen = len(x)//2
Lptr = 0
Rptr = len(x)-1
#↓ "="Add!!
while Lptr <= Rptr: # Lptr ==Rptr also enters the process inside while
#The following while is skipped.
#<===from here
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
#<==So far
# Lptr ==Rptr also enters the process inside while
#↓ "="Add!!
if Lptr <= Rptr:
#x[4],x[4] = x[4],x[4]So harmless
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
#This is important!!Increment and decrement respectively!
Lptr += 1
Rptr -= 1
print(x,f"Lptr = {Lptr}",f" Rptr = {Rptr}")
"=" Has been added to some parts. As a result, the execution result will be as follows.
Execution result.py
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 5 Rptr = 3
The positions of Lptr and Rptr have been reversed.
Now, let's take the array x given in this state,
Region 1: x [0] ~ Rptr (= x [3])
Area 2: Lptr (= x [5]) ~ x [8]
What happens if I divide them and perform the same processing as before?
Yes, it's recursion.
It looks like something will be born !? (laughs)
I've changed the description to make recursion easier to use.
test.py
#left :Leftmost as the initial value
#right:Rightmost as the initial value
def quick_sort(x,left,right):
Lptr = left
Rptr = right
cen = (left+right)//2
while Lptr <= Rptr:
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
if Lptr <= Rptr:
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
Lptr += 1
Rptr -= 1
print(x,f"Lptr = {Lptr}",f" Rptr = {Rptr}")
if __name__ =="__main__":
x = [1,8,7,4,5,2,6,3,9]
#Array to use x
#The initial value of left is the left end, so enter 0
#Since the initial value of right is the right end, len(x)-Enter 1
quick_sort(x,0,len(x)-1)
The image of recursion from now on is as follows.
Area with left, Rptr as left, right (green),
The area (blue) where Lptr and right are left and right seems to move.
How about such a description?
quick_sort.py
def quick_sort(x,left,right):
Lptr = left
Rptr = right
cen = (left+right)//2
while Lptr <= Rptr:
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
if Lptr <= Rptr:
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
Lptr += 1
Rptr -= 1
print(x,f"Lptr = {Lptr}",f" Rptr = {Rptr}")
#Left as shown in the figure above<If the relationship of Rptr is established
#Sort the left area recursively
if left < Rptr:
quick_sort(x,left,Rptr)
#Lptr as shown in the figure above<If the right relationship holds
#Sort the right area recursively
if Lptr < right:
quick_sort(x,Lptr,right)
if __name__ =="__main__":
x = [1,8,7,4,5,2,6,3,9]
quick_sort(x,0,len(x)-1)
The execution result is here.
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 5 Rptr = 3
[1, 2, 3, 4, 5, 7, 6, 8, 9] Lptr = 2 Rptr = 1
[1, 2, 3, 4, 5, 7, 6, 8, 9] Lptr = 1 Rptr = -1
[1, 2, 3, 4, 5, 7, 6, 8, 9] Lptr = 3 Rptr = 1
[1, 2, 3, 4, 5, 6, 7, 8, 9] Lptr = 6 Rptr = 5
[1, 2, 3, 4, 5, 6, 7, 8, 9] Lptr = 8 Rptr = 6
If you look at the last line, it's sorted. What should I do about the progress of the process, should I do it (; ´ ･ ω ･)
Recommended Posts