My approach to sorting algorithm

Question

For practicing purposes, I had the idea of making a sorting algorithm in Python.

My approach to it was to iterate through a given unsorted list to find the shortest number in it, add the number to a second list, remove shortest number from unsorted list, do that until the unsorted list is empty and return the sorted list.

How could my code be improved?

from math import inf
from random import randint

def my_sort(my_list):
    """
    Iterate through list and find shortest number, add
    shortest number to list until there are none left,
    return sorted list (shortest to highest).
    """
    unsorted_list = [*my_list]
    sorted_list = []
    for item in my_list:
        shortest_num = inf
        for num in unsorted_list:
            if num < shortest_num:
                shortest_num = num
        unsorted_list.remove(shortest_num)
        sorted_list.append(shortest_num)
    return sorted_list

# Randomly generate a list of 20 numbers ranging from -20 to 20
random_list = [randint(-20, 20) for i in range(20)]

print(random_list)
print(my_sort(random_list))

Answer 1

First I got same approach than previous answers (@Roland Illig & Luapulu) that are very similar.

But then I remembered Item 72 of Effective Python (Brett Slatkin's book):

72: Consider Searching Sorted Sequences with bisect. Python’s built-in bisect module provides better ways to accomplish these types of searches through ordered lists. You can use the bisect_left function to do an efficient binary search through any sequence of sorted items. The index it returns will either be where the item is already present in the list or where you’d want to insert the item in the list to keep it in sorted order

from bisect import bisect_left
def my_sort_2(my_list):
    sorted_list = []
    for value in my_list:
        index = bisect_left(sorted_list, value)
        sorted_list.insert(index, value)
    return sorted_list

bisect is part of standard lib since Python 2.1:

This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive comparison operations, this can be an improvement over the more common approach. The module is called bisect because it uses a basic bisection algorithm to do its work.

bisect.bisect_left(a, x, lo=0, hi=len(a)) Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.

And now it's time to check performance of available solutions for the list of 20 numbers:

• Min time with my_sort =0.0126 ms
• Min time with my_sort_luapulu =0.0114 ms
• Min time with my_sort_roland =0.0105 ms
• Min time with my_sort_2 =0.0048 ms

According just to this case, improvement in my machine with Python 3.8 is (compared to my_sort, from original question):

• Luapulu takes - 9,4% time
• Roland Illig takes - 16,4% time
• My proposal takes -61,7% time, What's a real difference for a list of 20

---

Note: this part has been edited, after learning from comments received, the way to make a complexity analysis (please let me know if I am wrong):

Nº steps required for a list of n elements: \$ n \cdot (\frac n2 \cdot \frac 12 + \frac n2) \$ = \$ n^2 \cdot \frac 34 \$

• bisect_left takes \$ \frac 12 \$ of sorted list length \$ \frac n2 \$
• insert in sorted list is \$ \frac n2 \$

So you neither should use this solution for sorting large data, as for large numbers it has also a time complexity of \$ \mathcal O(n^2) \$

Thanks all for make me see that my previous time analysis was wrong.

Note: Code used to check answers on my windows PC:

def print_min_time(description, func, *args, setup='pass'):
    min_time = min(timeit.repeat(lambda: func(*args), setup))
    print(f'Min time with {description} ={min_time/1000} ms')

random_list = [randint(-20, 20) for i in range(20)]
print_min_time('my_sort', my_sort, random_list, setup='from math import inf')
print_min_time('my_sort_2', my_sort_2, random_list, setup='from bisect import bisect_left')
print_min_time('my_sort_luapulu', my_sort_luapulu, random_list)
print_min_time('my_sort_roland', my_sort_roland, random_list)

Answer 2

Since the goal is the best possible implementation of this algorithm, I'd suggest the following. However, faster algorithms do exist.

1. To conform to PEP8 make sure you have two blank lines after your imports and surrounding function definitions.
2. Since, you aren't editing each item, but rather adding and removing items until the list is sorted, I'd use the while keyword.
3. The builtin min function is faster than looping through yourself. If you want to make your own minimum function as an exercise you can always do that and replace min with your own my_min say

My Code:

def my_sort2(my_list):
    unsorted_list = [*my_list]
    sorted_list = []
    while len(unsorted_list) > 0:
        shortest_num = min(unsorted_list)
        sorted_list.append(shortest_num)
        unsorted_list.remove(shortest_num)
    return sorted_list

When timing mysort2 vs your mysort, I get a 12% improvement on my machine.

Timing code: (Not the nicest but it does the job)

t1 = inf
t2 = inf
for _ in range(1000):
    t1 = min(t1, timeit.timeit(
        stmt=f'my_sort(random_list)',
        setup=f'from __main__ import my_sort, random_list',
        number=100))
    t2 = min(t2, timeit.timeit(
        stmt=f'my_sort2(random_list)',
        setup=f'from __main__ import my_sort2, random_list',
        number=100))

Answer 3

Your code looks well-formatted, it's easy to read and to follow, and the explanation you gave matches the code exactly. Well done. :)

for item in my_list:

This statement looks strange since in the body of this for loop, you neither use item nor my_list. You can express the idea of that code more directly:

for _ in range(len(my_list)):

The variable _ is just a normal variable, and you could even access its value. By convention though, the variable _ means an unused variable.

Or, alternatively, you could express it even shorter:

while len(unsorted_list) > 0:

This wording matches the body of the loop, where you remove an element from unsorted_list in each iteration. This is good. It's still quite long though, therefore the idiomatic way to test whether a list is empty is:

while unsorted_list:

This makes your code:

def my_sort(my_list):
    unsorted_list = [*my_list]
    sorted_list = []
    while unsorted_list:
        shortest_num = inf
        for num in unsorted_list:
            if num < shortest_num:
                shortest_num = num
        unsorted_list.remove(shortest_num)
        sorted_list.append(shortest_num)
    return sorted_list

This code can be made much shorter since Python has a built-in function called min. By using it you can transform your code to:

def my_sort(my_list):
    unsorted_list = [*my_list]
    sorted_list = []
    while unsorted_list:
        shortest_num = min(unsorted_list)
        unsorted_list.remove(shortest_num)
        sorted_list.append(shortest_num)
    return sorted_list

This is already much shorter than before, and you don't need to import math.inf anymore, which is good, since it was a placeholder anyway that was not really necessary from a high-level point of view.

This is about as elegant as it gets. You should not use this sorting algorithm for sorting large data since for a list of \$n\$ elements it requires \$ n + n \cdot (\frac n2 + \frac n2 + 1) \$ steps, or a bit more compressed, it has the time complexity \$\mathcal O(n^2)\$. There are faster sorting algorithms out there. These are more complicated to implement, but once they are implemented and tested, they are as easy to use as your algorithm.

Regarding the variable names: shortest_num should better be smallest_num, since 0 is shorter than -12345, and you probably didn't mean that. Your documentation comment should be more like:

"""
Return a sorted copy of the given list, from smallest to largest.
"""

# Sorting is done by repeatedly removing the smallest
# number from the list and adding it to the sorted list.

Note how I split the comment into two separate parts. The upper half in the """ triple quotes """ is meant to document the behavior of the code, while the lower half explains the implementation. For the code that uses this sorting function, it doesn't matter how the list is sorted, it just matters that it is sorted.