Problem
Today I’ve been working on this algorithm to sort a list. It works with duplicated numbers. What do you think about it? How can I improve it? Does it already exist? If it does, what is its name?
a = [1,1,5,3,2,3,4,3,99,99] # The list I'm going to sort.
b = [None] * len(a)
x = 0
for number in a:
for num in a:
if number >= num:
x += 1
b[x-1] = number
x = 0
b = b[::-1]
print(b)
for number in b: #This part of the code is for the duplicated numbers.
if number == None:
print(b.index(number))
b[b.index(number)] = b[b.index(number) - 1]
b = b[::-1]
print(b)
Solution
You probably already know, but just for the record, there is of course a built-in sorted function:
>>> sorted([1, 1, 5, 3, 2, 3, 4, 3, 99, 99])
[1, 1, 2, 3, 3, 3, 4, 5, 99, 99]
I’m not sure if your algorithm has a name,
but in any case I’m afraid it’s not very good,
because it’s very inefficient.
First of all it’s quadratic: for each element in the input, it visits all other elements.
It has other inefficiencies too, for example the way it replaces the None values is also quadratic.
This is because for each value, it uses the index function of the list to find the index, and this operation scans the content of the list.
Finally, the list is reversed twice in the process, which could be avoided by a different use of indexes.
Still preserving the essence of your algorithm, consider this alternative implementation that fixes some of the above points, along with a few other improvements:
def mysort(input):
"""
>>> mysort([1, 1, 5, 3, 2, 3, 4, 3, 99, 99])
[1, 1, 2, 3, 3, 3, 4, 5, 99, 99]
"""
result = [None] * len(input)
for num in input:
x = 0
for other in input:
if num <= other:
x += 1
result[len(input) - x] = num
for index, num in enumerate(result):
if num is None:
result[index] = result[index - 1]
return result
But ultimately, it would be better to use an algorithm that is not quadratic.
I recommend to look into insert-sort and merge-sort for exercise.