I am interested in an algorithm that can sort a given list by the time of appearance in Python. For example: [1, 3, 1, 5, 1, 4, 4, 7] -> [1, 1, 1, 3, 5, 4, 4, 7]. It seems that the build-in function with a custom key will do this job:

mylist = [1, 3, 1, 5, 1, 4, 4, 7]
sorted(mylist, key = lambda x: mylist.index(x))

However, I am more interested in implementing this myself. Is there a simple way to do this?

CodePudding user response：

A really fun way:

mylist.reverse()
for x in reversed(mylist):
    mylist.remove(x)
    mylist.append(x)

A boring but efficient way:

from collections import Counter

mylist = list(Counter(mylist).elements())

CodePudding user response：

Here is a simple insertion sort-like algorithm that provides the correct output.

mylist = [1, 3, 1, 5, 1, 4, 4, 7]
def sort(lst):
    start = 0
    while start < len(lst):
        num = lst[start]
        end = len(lst) - 1
        while end > start:
            if lst[end] == num:
                del lst[end]
                start  = 1
                lst.insert(start,num)
            else:
                end -= 1
        start  = 1
    print(lst)
sort(mylist)

CodePudding user response：

A simple implementation can be done with the following algorithm:

1. Count the occurrence of each number and store it into a dictionary
2. Create another list holding the elements with their first appearance.
3. Print this list

And the code for this algorithm is:

lst = [1, 3, 1, 5, 1, 4, 4, 7]

d = {}
for e in lst:
    d[e] = d.get(e, 0)   1

ans_lst = []
for e in lst:
    while d[e]:
        ans_lst.append(e)
        d[e] -= 1
print(ans_lst) # outputs: [1, 1, 1, 3, 5, 4, 4, 7]

This solution is having worst case time complexity O(n)
Whereas, the sorted() function has worst case time complexity of O(nlogn)