Define a function to sort a list of strings by the first 4 characters of the string? (Without using-CodePudding

I have a list of strings like this

source_1 = [
"2012 18  B",
"2015 19  B",
"2007 948 D",
"2018 179 C"]

I want to define a function (without using the python sort method) to sort these strings so that the output will be:

    source_1 = [
"2007 948 D",
"2012 18  B",
"2015 19  B",
"2018 179 C"]

So far I have come up with this but it's too inefficient?:

def sorttimestamp(arr):   
sorted = []
for s in arr:
        restof = s[-6:]
        timestamp = s[:10]

        sorted.append(timestamp)
        for i in range(len(sorted)):
                for j in range(i   1, len(sorted)):
                        if sorted[i] > sorted[j]:
                                sorted[i], sorted[j] = sorted[j], sorted[i]
return sorted

CodePudding user response：

You can use sorted with key function as you like:

source_1 = [
"2012 18  B",
"2012 11  B",
"2015 19  B",
"2015 19  A",
"2007 100 D",
"2007 948 D",
"2018 179 C",
"2018 179 D"]

res = sorted(source_1, key=lambda x: (x.split()[0], x.split()[1], x.split()[2]))
print(res)

Output:

['2007 100 D',
 '2007 948 D',
 '2012 11  B',
 '2012 18  B',
 '2015 19  A',
 '2015 19  B',
 '2018 179 C',
 '2018 179 D']

CodePudding user response：

If you can't use a built-in function, try out quick sort to reduce your time complexity from O(n^2) to O(nlogn).

CodePudding user response：

You could try using the insertion sort algorithm. It works best on relatively small datasets.

I'd still be using the builtin sorted() function, though, if efficiency is what's needed. It has a worst case complexity of O(n*log(n)), iirc, while this insertion sort I am proposing features a linear complexity at best, but a quadratic one on average / worst cases:

def insertion_sort(arr):
    """Algorithm main function."""
    # iterate through elements 1 through n-1
    for i in range(1, len(arr)):
        temp = arr[i]
        j = i - 1

        # make room for temp
        # for descending order sorting, replace < with > below
        while j >= 0 and temp < arr[j]:
            arr[j   1] = arr[j]
            j -= 1        
        # place temp at its correct place
        arr[j   1] = temp    
    return arr