1. Preamble
By sorting, we mean storing a population of data in order from largest to smallest or from smallest to largest according to the characteristics of the individual data.
Sorting is common in application development, such as displaying items by price, popularity, and number of purchases .......
The first slightly difficult algorithm for a beginning programmer to understand at first would be the bubbling algorithm of the sorting algorithm.
When I first started learning, my "brain" was almost wrapped up in the world of 2 loops. At that time, the teacher asked us to memorize the mnemonic for bubbling, which was a bit funny, but at that time, the level of knowledge was only a little bit, so the mnemonic was probably the best way to learn.
As the body of knowledge is slowly built up, the understanding of bubbling sort will naturally move from a formal to an essential understanding.
In this article, we start with the essence of bubbling sort, not just to understand it formally, but to do so in essence.
2. The bubble-sort algorithm
The so-called bubbling sort algorithm is essentially a maximum and minimum value algorithm.
So, you can leave bubbling sort aside for now and start by talking about the maximum algorithm.
In order to better understand the nature of the algorithm, it is not recommended to use functions already built into Python directly when writing algorithms. For examplemax()、min()……
To find the maximum value, there are various ideas, the most common of which are:
Pendulum method Comparison of two adjacent numbers
as a sequence of numbersnums=[3,1,8,9,12,32,7]
2.1 Staging method
Algorithmic thinking:
Find a ring, pick up a random number from the array and stand in the ring as the boss.
The boss doesn't mean you can be the boss just because you want to be, it depends on whether the other brothers are convinced or not. So, one by one, the other numbered brothers will mount the ring and the number on the ring to compare, the principle is that the big one stays, the small one leaves.
If you are looking for a maximum, the big one stays and the small one leaves.
Conversely, if you are looking for a minimum value, the small ones stay and the big ones leave.
You're on your side and you're in the ring. The last one left in the ring is the real boss.
nums = [3, 1, 8, 9, 12, 32, 7]
# The first number in the ring
m = nums[0]
# Other numbers are not convinced
for i in range(1, len(nums)):
# PK process, the big one stays in the ring #
if nums[i] > m:
m = nums[i]
# The last one left in the ring is the greatest #
print("The maximum value is:", m)It's simple, isn't it, if, after finding a maximum, you then find the maximum again in the remaining numbers, and so on, what happens at the end?
Eventually it is possible to get all the numbers in order! This is the most essential truth of sorting, finding and ordering.
Make a slight change to the code above and deposit the maximum value into another list each time you find it.
nums = [3, 1, 8, 9, 12, 32, 7]
# The first number in the ring
ms=[]
for _ in range(len(nums)):
m = nums[0]
for i in range(1, len(nums)):
if nums[i] > m:
m = nums[i]
# The largest value found in sequence is put into a new array.
(m)
# The maximum value found by removing it from the original series is to be found again in the next round in the series without it, without removing it, no matter how many times you find it, it will still be it
(m)
print(ms)
'''
Output results
[32, 12, 9, 8, 7, 3, 1]
'''We can see that all the numbers in the original array are sorted. But the above sorting algorithm is not perfect:
Another new space is opened, and obviously the space complexity is increased. The maximum value of the original series is found and then deleted, in order not to interfere with the remaining numbers to continue to find the maximum value. When all the numbers are sorted, the original series is also destroyed.
Is it possible to do the sorting in the original array without opening a new space? Sure.
You can find the maximum value and move backward! The original series logically shrinks from right to left.
nums = [3, 1, 8, 9, 12, 32, 7]
# The first number in the ring
nums_len = len(nums)
for _ in range(len(nums)):
m = nums[0]
for i in range(1, nums_len):
if nums[i] > m:
m = nums[i]
# Maximum value found, move last
(m)
(m)
# This is key, narrowing down the end of the original series #
nums_len = nums_len - 1
print(nums)
'''
Output result.
[32, 12, 9, 8, 7, 3, 1]
'''On top of the original array, the above code accomplishes the same sorting.
In the final analysis, the idea of the above sorting is to keep looking for the maximum value ah, looking for the maximum value ...... to find the last number, we naturally sorted.
So the inner loop in the algorithm structure is the core logic to find the maximum value, while the outer layer is to control how many times to find ah find ah find.
The above sorting algorithm which we can also call as bubbling sort algorithm has time complexity = number of outer loops X number of inner loops. If there are n numbers, then the outer loop n-1 times, the inner loop n-1 times, in the big O representation, the constants can be ignored, the time complexity should be O (n<sup>2</sup>).
2.2 Comparison of two adjacent numbers
If there are 7 numbers, to find the maximum value inside, there is a program is to compare the rows of two adjacent numbers, if the front is larger than the back of the number, then exchange positions, otherwise the position does not move. On the physical education class, the teacher lined up with this way, the taller and shorter exchange position, until you can not exchange for this.
nums = [3, 1, 8, 9, 12, 32, 7]
for i in range(len(nums)-1):
# Compare 2 neighboring numbers
if nums[i] > nums[i + 1]:
# If the preceding number is greater than the following number, exchange
nums[i], nums[i + 1] = nums[i + 1], nums[i]
# Obviously, the number in the last position of the series is the largest #
print(nums[len(nums) - 1])
'''
Output Result
32
'''The above code also implements finding the maximum value.
The same idea as before, if you look for the first maximum value, and then continue to look for the maximum value in the remaining numbers, keep looking and looking, you will find that the last all the numbers are in good order.
In the above to find the maximum value of the logical basis, and then nested in the outside of a repeat syntax, so that the logic to find the maximum value of the search round after round, the outer layer of repetition as long as not less than the length of the figures in the array, you can complete the sorting work, even if the outer layer of repetition is greater than the length of the figures in the array, just do some more useless work.
nums = [3, 1, 8, 9, 12, 32, 7]
# 100 repeated in the outer layer means that the maximum is found 100 times, which is just to illustrate the point, that is, to keep looking for the maximum, which, obviously, is not necessary to find 100 times.
for j in range(100):
for i in range(len(nums)-1):
# Compare 2 neighboring numbers
if nums[i] > nums[i + 1]:
# If the preceding number is greater than the following number, exchange
nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(nums)The above code is the bubble sort algorithm implementation. In fact, the bubble sort is to find the maximum value of a round, and then continue to find the maximum value of the idea. The above algorithm can be some optimization, such as the maximum value has been found there is no need to participate in the subsequent search for the maximum value to go.
Obviously, the maximum number of rounds to find the maximum value is the length of the array minus 1. With 5 numbers, the first 4 are found, so naturally everyone is in order.
nums = [3, 1, 8, 9, 12, 32, 7]
# How many times do you find the maximum, minus 1?
for j in range(len(nums)-1):
for i in range(len(nums)-1-j):
# Compare 2 neighboring numbers
if nums[i] > nums[i + 1]:
# If the preceding number is greater than the following number, exchange
nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(nums)When learning the bubbling sort algorithm, don't be intimidated by the outer and inner loop structure, the core is to understand the maximization algorithm. The time complexity of the above bubbling sort algorithm is also O(n<sup>2</sup>).
3. Selection sorting algorithm
**Selective sorting algorithm is a variant of bubble sort, still looking for the largest (small) value algorithm, **bubble sort is all the way to compare all the way to exchange, why, because do not know which number in the array is the largest (small) value, so you can only keep comparing the non-stop exchange.
Selection sorting has a philosophy that is superior to bubbling, swapping only when swapping is needed.
So the question for a selection sort algorithm is when do you need to swap?
Selection sort starts by assuming that the first number is the minimum, and then looking for any smaller than that assumption in the numbers that follow. It is not the case that if you find a smaller one, you exchange it, because it is possible that there is a smaller one, and only when all the subsequent numbers have been found is it determined that an exchange is to be made.
Still use the ring algorithm implementation to find the largest (smallest) value and swap positions when found.
nums = [6, 2, 5, 9, 12, 1, 7]
# The ring! Pretend the first number is the minimum.
mi = nums[0]
# Assumed minimum numerical position
mi_idx = 0
# Location of the true minimum number
real_idx = mi_idx
for i in range(mi_idx + 1, len(nums)):
if nums[i] < mi:
mi = nums[i]
# Memorize the position of the smaller number, not the swap
real_idx = i
# If there is a smaller
if real_idx != mi_idx:
# Exchange
nums[real_idx], nums[mi_idx] = nums[mi_idx], nums[real_idx]
print(nums)
'''
Output results
[1, 2, 5, 9, 12, 6, 7]
'''The above code is the core logic of selective sorting, which implements moving the smallest number to the top.
Then, based on the above logic, continue to find the minimum value in subsequent numbers and move ahead. Find it a few more times and you're done! The essence is still the same as the bubbling algorithm, keep finding the maximum (small) value.
nums = [6, 2, 5, 9, 12, 1, 7]
for j in range(len(nums)-1):
mi = nums[j]
# Assumed minimum numerical position
mi_idx = j
# Location of the true minimum number
real_idx = mi_idx
for i in range(mi_idx + 1, len(nums)):
if nums[i] < mi:
mi = nums[i]
# Remember the location of smaller numbers
real_idx = i
# If there is a smaller
if real_idx != mi_idx:
# Exchange
nums[real_idx], nums[mi_idx] = nums[mi_idx], nums[real_idx]
print(nums)
'''
Output results.
[1, 2, 5, 6, 7, 9, 12]
'''The time complexity of selection sort is the same as that of bubbling sort O(n<sup>2</sup>).
4. Insertion sorting
When playing cards, we just got the hand of cards is disordered, in the process of organizing the cards and let the cards step by step to become orderly process is the idea of insertion algorithm.
The core idea of insertion sort:
Divide the original series logically (by dividing it on the original series according to the starting and ending positions) into two series, the front series being ordered and the back series being unordered.
At the beginning, the previous series (later referred to as the front series) has only one unique number, the first number of the original series. It is obviously sorted!
Take the numbers out of the back column one by one in turn and compare them with the numbers in the front column, making sure that the whole front column is still in order after insertion into the front column.
As above, get the number 1 from the back of the list and compare it with the number 3 in the front, if it is sorted from largest to smallest, then 1 is directly after 3, if it is sorted from smallest to largest, then 1 is in front of 3.
Here, in order from smallest to largest.
From the description as above, it is clear that the core logic of insertion sort is:
Compare: The numbers in the last column are compared with the numbers in the first column, which is no different from bubble and select. Shift: If the number in the first column is larger than the number in the second column, then it needs to be shifted backward. Can also be exchanged with the bubble sort. Insert: For the latter column of numbers in the first column to find the appropriate position, insert this data.
Code implementation of insertion sort:
Pre-pointer and post-pointer schemes are used here.
The front pointer is used to locate the number in the front array, oriented from right to left.
The back pointer is used to locate the digit in the back digit, oriented from left to right.
The position of the front pointer initially precedes the front array, and the position of the back pointer initially precedes the back array.
nums = [3, 1, 8, 9, 12, 32, 7]
# After that the pointer points to the second number in the original array, so the index number starts at 1.
for back_idx in range(1, len(nums)):
# The relationship between forward and backward pointers.
front_idx = back_idx - 1
# Temporary variable, when comparing, the number in the first column may have to be shifted backward, you need to save the number pointed to by the back pointer ahead of time
tmp = nums[back_idx]
# Comparison with numbers in previous series
while front_idx >= 0 and tmp < nums[front_idx]:
# Shift
nums[front_idx + 1] = nums[front_idx]
front_idx -= 1
if front_idx != back_idx - 1:
# Insert
nums[front_idx + 1] = tmp
print(nums)
'''
Output results
[1,3,7,8,9,12,32]
'''The above code uses shift and insert operations, and can also use swap operations. In case of swap operation, initially, the front and back pointers can point to the same location.
nums = [3, 1, 8, 9, 12, 32, 7]
for back_idx in range(1, len(nums)):
for front_idx in range(back_idx, 0, -1):
if nums[front_idx] < nums[front_idx - 1]:
nums[front_idx], nums[front_idx - 1] = nums[front_idx - 1], nums[front_idx]
else:
break
print(nums)The back pointer is used to select numbers in the back column, and the front pointer is used to compare and exchange neighboring numbers in the front column. Same as bubble sort.
Here's an optimization over bubble sort, which requires comparing all two adjacent numbers in the array, regardless of whether the comparison is necessary.
But the insertion is not the same, because the insertion is assumed to be the previous array is ordered, so if the latter pointer points to a number than the last number of the previous array are larger, obviously, is not necessary to compare the following numbers ` ` is not necessary to compare with the previous number, directly to the end of the previous array.
The time complexity of insertion sort is still O(n<sup>2</sup>).
5. Rapid sorting
Quick sort is an interesting sorting algorithm, the core idea of quick sort:
Idea of partition: global to local, or rough to perfect process of gradual refinement.
Similar to figure drawing.
Start by drawing an outline of what it will look like!
Then gradually refine it so that it really is what it is!
Quick sort is the same idea; at first, the array is made to appear coarsely ordered, and through gradual iteration, it is made to appear truly ordered.
Dichotomous Idea: Choose a number (base) in the series as the center of reference, and those numbers in the series that are larger than the base are placed on the left (right), and those that are smaller than the base are placed on the right (left).
After the first bisection: the entire series has an ordered outline over the base, and then the bisection operation continues to be completed on the numbers in the first and second parts of the base.
The quick sort is described here using the left and right pointer approach:
The left pointer initially points to the leftmost number. The right pointer initially points to the rightmost digit.
Select here8 As a base for the first bisection, there is no specific requirement for the choice of base, as long as it is a number in the series, don't be shy, choose any number. Here the ratio of8 Smaller move to8 The left side of the8 big move8 The right side.
The process of shifting:
The left pointer keeps moving to the right until it encounters a number greater than or equal to the base, and the right pointer keeps moving to the left until it encounters a number less than or equal to the base. The left pointer and the right pointer are exchanged.
As shown above, the left pointer will finally stop at the number8 The right hand will stop at the number7 Location.
Swap the digits of the left and right pointer positions.
And so on, continuing to move pointers and swap.
After the first bisection, the entire array will become as shown below:
When the left and right pointers are reunited, the first bisection process ends here. Taking the base8 As the dividing line, divide the original series into two parts, continue to use the above dichotomous idea on the former and latter series . Obviously, using recursion is the most direct and effective choice.
The following first dichotomous code:
nums = [3, 1, 8, 32, 2, 9, 7]
def quick_sort(nums):
# Left pointer
left = 0
# Right pointer
right = len(nums) - 1
# Base, which can be any number, usually the first number in the series is chosen
base_n = 8
while left < right:
# The left pointer moves to the right to the point where the number of digits at the left pointer position is greater than or equal to the base number.
while nums[left] < base_n and left < right:
left += 1
while nums[right] > base_n and right > left:
right -= 1
# Exchange
nums[left], nums[right] = nums[right], nums[left]
quick_sort(nums)
print(nums)Output results:
[3, 1, 7, 2, 8, 9, 32]
Same result as the demo flowchart above.
Multiple bisection using recursion:
nums = [3, 1, 8, 32, 2, 9, 7]
def quick_sort(nums, start, end):
if start >= end:
return
# Left pointer
left = start
# Right pointer
right = end
# Base
base_n = nums[start]
while left < right:
while nums[right] > base_n and right > left:
right -= 1
# The left pointer moves to the right to the point where the number of digits at the left pointer position is greater than or equal to the base number.
while nums[left] < base_n and left < right:
left += 1
# Exchange
nums[left], nums[right] = nums[right], nums[left]
# Left column
quick_sort(nums, start, left - 1)
# The right-hand column
quick_sort(nums, right + 1, end)
quick_sort(nums, 0, len(nums) - 1)
print(nums)
'''
Output results
[1, 2, 3, 7, 8, 9, 32]
'''Fast sort has a time complexity of O(nlogn) and a space complexity of O(nlogn).
6. Summary
There are many other sorting algorithms besides bubble, select, insert, and quick sort algorithms, bubble, select , insert algorithms are very similar and have their similar comparison, exchange logic. Quick sort uses the concept of partitioning, which can reduce the time complexity from.
This article on Python sorting algorithm of the bubbling sort is introduced to this article, more related Python bubbling sort content please search for my previous articles or continue to browse the following related articles I hope you will support me more in the future!