Hướng dẫn sorting algorithms python

Timing Your Code

When comparing two sorting algorithms in Python, it’s always informative to look at how long each one takes to run. The specific time each algorithm takes will be partly determined by your hardware, but you can still use the proportional time between executions to help you decide which implementation is more time efficient.

In this section, you’ll focus on a practical way to measure the actual time it takes to run to your sorting algorithms using the timeit module. For more information on the different ways you can time the execution of code in Python, check out Python Timer Functions: Three Ways to Monitor Your Code.

Here’s a function you can use to time your algorithms:

 1from random import randint
 2from timeit import repeat
 3
 4def run_sorting_algorithm[algorithm, array]:
 5    # Set up the context and prepare the call to the specified
 6    # algorithm using the supplied array. Only import the
 7    # algorithm function if it's not the built-in `sorted[]`.
 8    setup_code = f"from __main__ import {algorithm}" \
 9        if algorithm != "sorted" else ""
10
11    stmt = f"{algorithm}[{array}]"
12
13    # Execute the code ten different times and return the time
14    # in seconds that each execution took
15    times = repeat[setup=setup_code, stmt=stmt, repeat=3, number=10]
16
17    # Finally, display the name of the algorithm and the
18    # minimum time it took to run
19    print[f"Algorithm: {algorithm}. Minimum execution time: {min[times]}"]

In this example, run_sorting_algorithm[] receives the name of the algorithm and the input array that needs to be sorted. Here’s a line-by-line explanation of how it works:

• Line 8 imports the name of the algorithm using the magic of Python’s f-strings. This is so that timeit.repeat[] knows where to call the algorithm from. Note that this is only necessary for the custom implementations used in this tutorial. If the algorithm specified is the built-in sorted[], then nothing will be imported.

• Line 11 prepares the call to the algorithm with the supplied array. This is the statement that will be executed and timed.

• Line 15 calls timeit.repeat[] with the setup code and the statement. This will call the specified sorting algorithm ten times, returning the number of seconds each one of these executions took.

• Line 19 identifies the shortest time returned and prints it along with the name of the algorithm.

Here’s an example of how to use run_sorting_algorithm[] to determine the time it takes to sort an array of ten thousand integer values using sorted[]:

21ARRAY_LENGTH = 10000
22
23if __name__ == "__main__":
24    # Generate an array of `ARRAY_LENGTH` items consisting
25    # of random integer values between 0 and 999
26    array = [randint[0, 1000] for i in range[ARRAY_LENGTH]]
27
28    # Call the function using the name of the sorting algorithm
29    # and the array you just created
30    run_sorting_algorithm[algorithm="sorted", array=array]

If you save the above code in a sorting.py file, then you can run it from the terminal and see its output:

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

Remember that the time in seconds of every experiment depends in part on the hardware you use, so you’ll likely see slightly different results when running the code.

Measuring Efficiency With Big O Notation

The specific time an algorithm takes to run isn’t enough information to get the full picture of its time complexity. To solve this problem, you can use Big O [pronounced “big oh”] notation. Big O is often used to compare different implementations and decide which one is the most efficient, skipping unnecessary details and focusing on what’s most important in the runtime of an algorithm.

The time in seconds required to run different algorithms can be influenced by several unrelated factors, including processor speed or available memory. Big O, on the other hand, provides a platform to express runtime complexity in hardware-agnostic terms. With Big O, you express complexity in terms of how quickly your algorithm’s runtime grows relative to the size of the input, especially as the input grows arbitrarily large.

Assuming that n is the size of the input to an algorithm, the Big O notation represents the relationship between n and the number of steps the algorithm takes to find a solution. Big O uses a capital letter “O” followed by this relationship inside parentheses. For example, O[n] represents algorithms that execute a number of steps proportional to the size of their input.

Although this tutorial isn’t going to dive very deep into the details of Big O notation, here are five examples of the runtime complexity of different algorithms:

This tutorial covers the Big O runtime complexity of each of the sorting algorithms discussed. It also includes a brief explanation of how to determine the runtime on each particular case. This will give you a better understanding of how to start using Big O to classify other algorithms.

Implementing Bubble Sort in Python

Here’s an implementation of a bubble sort algorithm in Python:

 1def bubble_sort[array]:
 2    n = len[array]
 3
 4    for i in range[n]:
 5        # Create a flag that will allow the function to
 6        # terminate early if there's nothing left to sort
 7        already_sorted = True
 8
 9        # Start looking at each item of the list one by one,
10        # comparing it with its adjacent value. With each
11        # iteration, the portion of the array that you look at
12        # shrinks because the remaining items have already been
13        # sorted.
14        for j in range[n - i - 1]:
15            if array[j] > array[j + 1]:
16                # If the item you're looking at is greater than its
17                # adjacent value, then swap them
18                array[j], array[j + 1] = array[j + 1], array[j]
19
20                # Since you had to swap two elements,
21                # set the `already_sorted` flag to `False` so the
22                # algorithm doesn't finish prematurely
23                already_sorted = False
24
25        # If there were no swaps during the last iteration,
26        # the array is already sorted, and you can terminate
27        if already_sorted:
28            break
29
30    return array

Since this implementation sorts the array in ascending order, each step “bubbles” the largest element to the end of the array. This means that each iteration takes fewer steps than the previous iteration because a continuously larger portion of the array is sorted.

The loops in lines 4 and 10 determine the way the algorithm runs through the list. Notice how j initially goes from the first element in the list to the element immediately before the last. During the second iteration, j runs until two items from the last, then three items from the last, and so on. At the end of each iteration, the end portion of the list will be sorted.

As the loops progress, line 15 compares each element with its adjacent value, and line 18 swaps them if they are in the incorrect order. This ensures a sorted list at the end of the function.

To properly analyze how the algorithm works, consider a list with values [8, 2, 6, 4, 5]. Assume you’re using bubble_sort[] from above. Here’s a figure illustrating what the array looks like at each iteration of the algorithm:

Now take a step-by-step look at what’s happening with the array as the algorithm progresses:

1. The code starts by comparing the first element, 8, with its adjacent element, 2. Since 8 > 2, the values are swapped, resulting in the following order: [2, 8, 6, 4, 5].

2. The algorithm then compares the second element, 8, with its adjacent element, 6. Since 8 > 6, the values are swapped, resulting in the following order: [2, 6, 8, 4, 5].

3. Next, the algorithm compares the third element, 8, with its adjacent element, 4. Since 8 > 4, it swaps the values as well, resulting in the following order: [2, 6, 4, 8, 5].

4. Finally, the algorithm compares the fourth element, 8, with its adjacent element, 5, and swaps them as well, resulting in [2, 6, 4, 5, 8]. At this point, the algorithm completed the first pass through the list [i = 0]. Notice how the value 8 bubbled up from its initial location to its correct position at the end of the list.

5. The second pass [i = 1] takes into account that the last element of the list is already positioned and focuses on the remaining four elements, [2, 6, 4, 5]. At the end of this pass, the value 6 finds its correct position. The third pass through the list positions the value 5, and so on until the list is sorted.

Measuring Bubble Sort’s Big O Runtime Complexity

Your implementation of bubble sort consists of two nested for loops in which the algorithm performs n - 1 comparisons, then n - 2 comparisons, and so on until the final comparison is done. This comes at a total of [n - 1] + [n - 2] + [n - 3] + … + 2 + 1 = n[n-1]/2 comparisons, which can also be written as ½n2 - ½n.

You learned earlier that Big O focuses on how the runtime grows in comparison to the size of the input. That means that, in order to turn the above equation into the Big O complexity of the algorithm, you need to remove the constants because they don’t change with the input size.

Doing so simplifies the notation to n2 - n. Since n2 grows much faster than n, this last term can be dropped as well, leaving bubble sort with an average- and worst-case complexity of O[n2].

In cases where the algorithm receives an array that’s already sorted—and assuming the implementation includes the already_sorted flag optimization explained before—the runtime complexity will come down to a much better O[n] because the algorithm will not need to visit any element more than once.

O[n], then, is the best-case runtime complexity of bubble sort. But keep in mind that best cases are an exception, and you should focus on the average case when comparing different algorithms.

Timing Your Bubble Sort Implementation

Using your run_sorting_algorithm[] from earlier in this tutorial, here’s the time it takes for bubble sort to process an array with ten thousand items. Line 8 replaces the name of the algorithm and everything else stays the same:

 1if __name__ == "__main__":
 2    # Generate an array of `ARRAY_LENGTH` items consisting
 3    # of random integer values between 0 and 999
 4    array = [randint[0, 1000] for i in range[ARRAY_LENGTH]]
 5
 6    # Call the function using the name of the sorting algorithm
 7    # and the array you just created
 8    run_sorting_algorithm[algorithm="bubble_sort", array=array]

You can now run the script to get the execution time of bubble_sort:

$ python sorting.py
Algorithm: bubble_sort. Minimum execution time: 73.21720498399998

It took 73 seconds to sort the array with ten thousand elements. This represents the fastest execution out of the ten repetitions that run_sorting_algorithm[] runs. Executing this script multiple times will produce similar results.

Analyzing the Strengths and Weaknesses of Bubble Sort

The main advantage of the bubble sort algorithm is its simplicity. It is straightforward to both implement and understand. This is probably the main reason why most computer science courses introduce the topic of sorting using bubble sort.

As you saw before, the disadvantage of bubble sort is that it is slow, with a runtime complexity of O[n2]. Unfortunately, this rules it out as a practical candidate for sorting large arrays.

Implementing Insertion Sort in Python

The insertion sort algorithm works exactly like the example with the deck of cards. Here’s the implementation in Python:

 1def insertion_sort[array]:
 2    # Loop from the second element of the array until
 3    # the last element
 4    for i in range[1, len[array]]:
 5        # This is the element we want to position in its
 6        # correct place
 7        key_item = array[i]
 8
 9        # Initialize the variable that will be used to
10        # find the correct position of the element referenced
11        # by `key_item`
12        j = i - 1
13
14        # Run through the list of items [the left
15        # portion of the array] and find the correct position
16        # of the element referenced by `key_item`. Do this only
17        # if `key_item` is smaller than its adjacent values.
18        while j >= 0 and array[j] > key_item:
19            # Shift the value one position to the left
20            # and reposition j to point to the next element
21            # [from right to left]
22            array[j + 1] = array[j]
23            j -= 1
24
25        # When you finish shifting the elements, you can position
26        # `key_item` in its correct location
27        array[j + 1] = key_item
28
29    return array

Unlike bubble sort, this implementation of insertion sort constructs the sorted list by pushing smaller items to the left. Let’s break down insertion_sort[] line by line:

• Line 4 sets up the loop that determines the key_item that the function will position during each iteration. Notice that the loop starts with the second item on the list and goes all the way to the last item.

• Line 7 initializes key_item with the item that the function is trying to place.

• Line 12 initializes a variable that will consecutively point to each element to the left of key item. These are the elements that will be consecutively compared with key_item.

• Line 18 compares key_item with each value to its left using a while loop, shifting the elements to make room to place key_item.

• Line 27 positions key_item in its correct place after the algorithm shifts all the larger values to the right.

Here’s a figure illustrating the different iterations of the algorithm when sorting the array [8, 2, 6, 4, 5]:

Now here’s a summary of the steps of the algorithm when sorting the array:

1. The algorithm starts with key_item = 2 and goes through the subarray to its left to find the correct position for it. In this case, the subarray is [8].

2. Since 2 < 8, the algorithm shifts element 8 one position to its right. The resultant array at this point is [8, 8, 6, 4, 5].

3. Since there are no more elements in the subarray, the key_item is now placed in its new position, and the final array is [2, 8, 6, 4, 5].

4. The second pass starts with key_item = 6 and goes through the subarray located to its left, in this case [2, 8].

5. Since 6 < 8, the algorithm shifts 8 to its right. The resultant array at this point is [2, 8, 8, 4, 5].

6. Since 6 > 2, the algorithm doesn’t need to keep going through the subarray, so it positions key_item and finishes the second pass. At this time, the resultant array is [2, 6, 8, 4, 5].

7. The third pass through the list puts the element 4 in its correct position, and the fourth pass places element 5 in the correct spot, leaving the array sorted.

Measuring Insertion Sort’s Big O Runtime Complexity

Similar to your bubble sort implementation, the insertion sort algorithm has a couple of nested loops that go over the list. The inner loop is pretty efficient because it only goes through the list until it finds the correct position of an element. That said, the algorithm still has an O[n2] runtime complexity on the average case.

The worst case happens when the supplied array is sorted in reverse order. In this case, the inner loop has to execute every comparison to put every element in its correct position. This still gives you an O[n2] runtime complexity.

The best case happens when the supplied array is already sorted. Here, the inner loop is never executed, resulting in an O[n] runtime complexity, just like the best case of bubble sort.

Although bubble sort and insertion sort have the same Big O runtime complexity, in practice, insertion sort is considerably more efficient than bubble sort. If you look at the implementation of both algorithms, then you can see how insertion sort has to make fewer comparisons to sort the list.

Timing Your Insertion Sort Implementation

To prove the assertion that insertion sort is more efficient than bubble sort, you can time the insertion sort algorithm and compare it with the results of bubble sort. To do this, you just need to replace the call to run_sorting_algorithm[] with the name of your insertion sort implementation:

 1if __name__ == "__main__":
 2    # Generate an array of `ARRAY_LENGTH` items consisting
 3    # of random integer values between 0 and 999
 4    array = [randint[0, 1000] for i in range[ARRAY_LENGTH]]
 5
 6    # Call the function using the name of the sorting algorithm
 7    # and the array we just created
 8    run_sorting_algorithm[algorithm="insertion_sort", array=array]

You can execute the script as before:

$ python sorting.py
Algorithm: insertion_sort. Minimum execution time: 56.71029764299999

Notice how the insertion sort implementation took around 17 fewer seconds than the bubble sort implementation to sort the same array. Even though they’re both O[n2] algorithms, insertion sort is more efficient.

Analyzing the Strengths and Weaknesses of Insertion Sort

Just like bubble sort, the insertion sort algorithm is very uncomplicated to implement. Even though insertion sort is an O[n2] algorithm, it’s also much more efficient in practice than other quadratic implementations such as bubble sort.

There are more powerful algorithms, including merge sort and Quicksort, but these implementations are recursive and usually fail to beat insertion sort when working on small lists. Some Quicksort implementations even use insertion sort internally if the list is small enough to provide a faster overall implementation. Timsort also uses insertion sort internally to sort small portions of the input array.

That said, insertion sort is not practical for large arrays, opening the door to algorithms that can scale in more efficient ways.

Implementing Merge Sort in Python

The implementation of the merge sort algorithm needs two different pieces:

1. A function that recursively splits the input in half
2. A function that merges both halves, producing a sorted array

Here’s the code to merge two different arrays:

 1def merge[left, right]:
 2    # If the first array is empty, then nothing needs
 3    # to be merged, and you can return the second array as the result
 4    if len[left] == 0:
 5        return right
 6
 7    # If the second array is empty, then nothing needs
 8    # to be merged, and you can return the first array as the result
 9    if len[right] == 0:
10        return left
11
12    result = []
13    index_left = index_right = 0
14
15    # Now go through both arrays until all the elements
16    # make it into the resultant array
17    while len[result]