Detailed sorting algorithm (implemented in Python)
Python's built-in sorting algorithm#
Like many other high-level programming languages, the Python language provides the ability to use the sorted() function to use data out of the box. Example:
>>> li =[9,5,3,6,7]>>>sorted(li)[3,5,6,7,9]
Bubble Sort#
Bubble sort is one of the most straightforward sorting algorithms. Its name comes from the way the algorithm works: after every convenience, the largest element in the list will "bubble" to the correct position.
Bubble sorting involves traversing a list, comparing elements at once, and exchanging irregular adjacent items.
Python implements bubble sort##
def bublle_sort(array):
n =len(array)for i inrange(n):
# Create a flag
already_sorted = True
for j inrange(n - i -1):if array[j]> array[j+1]:
array[j], array[j+1]= array[j+1], array[j]
already_sorted = False
if already_sorted:breakreturn array
Time complexity: O(
).
Insertion sort#
Like bubble sort, insertion sort algorithm is easy to implement and understand. But unlike bubble sorting, it builds a sorted list element at a time by comparing each item with the rest of the list and inserting it in the correct position. This "insertion" process names the algorithm.
A good analogy to explain insertion sort is the way you sort a deck of cards. Imagine that you have a set of cards in your hand and want to arrange them in order. First, compare one card with the rest until you find the correct position. At that time, you need to insert the card into the correct position, and then restart to make a new card, and repeat until all the cards in your hand are sorted.
Python implements insertion sort##
def insertion_sort(array):for i inrange(1,len(array)):
key_item = array[i]
j = i -1while j >=0 and array[j]> key_item:
array[j +1]= array[j]
j -=1
array[j +1]= key_item
return arry
Time complexity: O(
).
Merge Sort##
Merge sort is a very effective sorting algorithm. It is based on the divide and conquer method, which is a powerful algorithm technique for solving complex problems.
In order to correctly understand divide and conquer, you should first understand the concept of recursion. Recursion involves breaking down the problem into smaller sub-problems until they are small enough to be unsolvable. In programming, recursion is usually represented by a function that calls itself.
Divide and conquer algorithms usually follow the same structure:
- The original input is divided into several parts, and each part represents a sub-problem, which is similar to the original input but simpler.
- Each sub-problem is solved recursively.
- The solutions to all sub-problems are combined into an overall solution.
In the case of merge sorting, the divide and conquer method divides the set of input values into two equal parts, sorts each half recursively, and finally merges the two sorted parts into a sorted list.
Python implementation merge##
def merge(left, right):iflen(left)==0:return right
iflen(right)==0:return left
result =[]
index_left = index_right =0whilelen(result)<len(left)+len(right):if left[index_left]<= right[index_right]:
result.append(left[index_left])
index_right +=1else:
result.append(right[index_right])
index_left +=1if index_right ==len(right):
result += left[index_left:]breakif index_left ==len(left):
result += right[index_right:]breakreturn result
def merge_sort(array):iflen(array)<2:return array
midpoint =len(array)// 2returnmerge(
left=merge_sort(array[:midpoint]),
right=merge_sort(array[midpoint:]))
Time complexity: O(
)
Quick sort#
Just like merge sort, the quick sort algorithm uses the principle of divide and conquer to divide the input array into two lists, the first contains small items and the second contains large items. Then, the algorithm will sort the two lists recursively until the resulting list is completely sorted.
Dividing the input list is called partitioning the list. Quicksort first selects a pivot element, and then partitions the list around that pivot, placing each smaller element into a low array and each larger element into a high array.
Place each element from the low list to the left of the PivotTable, and place each element from the high list to the right of the PivotTable, and position it exactly where you need it in the final sorted list. This means that the function can now recursively recursively recursively go from low to high until the entire list is sorted.
Python implements quick sort##
rom random import randint
def quicksort(array):
# If the input array contains fewer than two elements,
# then return it as the result of the functioniflen(array)<2:return array
low, same, high =[],[],[]
# Select your `pivot` element randomly
pivot = array[randint(0,len(array)-1)]for item in array:
# Elements that are smaller than the `pivot` go to
# the `low` list. Elements that are larger than
# ` pivot` go to the `high` list. Elements that are
# equal to `pivot` go to the `same` list.if item < pivot:
low.append(item)
elif item == pivot:
same.append(item)
elif item > pivot:
high.append(item)
# The final result combines the sorted `low` list
# with the `same` list and the sorted `high` list
returnquicksort(low)+ same +quicksort(high)
Time complexity: O(
)
Timsort algorithm
Timsort algorithm is considered to be a hybrid sorting algorithm because it uses the best of both worlds combination of insertion sort and merge sort. Timsort is close to the Python community because it was created by Tim Peters in 2002 and used as the standard sorting algorithm for the Python language.
The main feature of Timsort is that it utilizes sorted elements that exist in most real data sets. These are called natural operations. Then, the algorithm traverses the list, collects the elements into the run, and merges them into a sorted list.
Python implements Timsort
In this section, you will create a barebones Python implementation that illustrates all parts of the Timsort algorithm. If you are interested, you can also check Timsort's original C implementation.
def insertion_sort(array, left=0, right=None):if right is None:
right =len(array)-1
# Loop from the element indicated by
# ` left` until the element indicated by `right`for i inrange(left +1, right +1):
# This is the element we want to position in its
# correct place
key_item = array[i]
# Initialize the variable that will be used to
# find the correct position of the element referenced
# by `key_item`
j = i -1
# Run through the list ofitems(the left
# portion of the array) and find the correct position
# of the element referenced by `key_item`. Do this only
# if the `key_item` is smaller than its adjacent values.while j >= left and array[j]> key_item:
# Shift the value one position to the left
# and reposition `j` to point to the next element
# ( from right to left)
array[j +1]= array[j]
j -=1
# When you finish shifting the elements, position
# the `key_item`in its correct location
array[j +1]= key_item
return array
This modified implementation adds two left and right parameters, which indicate which part of the array should be sorted. This allows the Timsort algorithm to sort part of the array. Modifying functions instead of creating new ones means that it can be used for both insertion sort and Timsort.
def timsort(array):
min_run =32
n =len(array)
# Start by slicing and sorting small portions of the
# input array. The size of these slices is defined by
# your `min_run` size.for i inrange(0, n, min_run):insertion_sort(array, i,min((i + min_run -1), n -1))
# Now you can start merging the sorted slices.
# Start from`min_run`, doubling the size on
# each iteration until you surpass the length of
# the array.
size = min_run
while size < n:
# Determine the arrays that will
# be merged together
for start inrange(0, n, size *2):
# Compute the `midpoint`(where the first array ends
# and the second starts) and the `endpoint`(where
# the second array ends)
midpoint = start + size -1
end =min((start + size *2-1),(n-1))
# Merge the two subarrays.
# The `left` array should go from`start` to
# ` midpoint + 1`,while the `right` array should
# go from`midpoint + 1` to `end + 1`.
merged_array =merge(
left=array[start:midpoint +1],
right=array[midpoint +1:end +1])
# Finally, put the merged array back into
# your array
array[start:start +len(merged_array)]= merged_array
# Each iteration should double the size of your arrays
size *=2return array
This modified implementation adds two left and right parameters, which indicate which part of the array should be sorted. This allows the Timsort algorithm to sort part of the array. Modifying functions instead of creating new ones means that it can be used for both insertion sort and Timsort.
Recommended Posts