Python - Recursive Date Sorting Algorithm

Question

My assignment states that I get a list of birthdays and that I have to arrange them chronologically. I must write my own, so I can't use Python's predefined functions, such this:

import datetime
d = ['09-2012', '04-2007', '11-2012', '05-2013', '12-2006', '05-2006', '08-2007']
sorted(d, key=lambda x: datetime.datetime.strptime(x, '%m-%Y'))

Here is what I'm thinking of doing.

Step 1: Red all dates and put them into a list dd/mm/yyyy

date_list = [[1,2,1991],[2,1,1991],[3,4,1992],[5,6,1993],[4,5,1992],[8,5,1993]]

For better visualization, I will rearrange them like so:

1 / 2 / 1991
2 / 1 / 1991
3 / 4 / 1992
5 / 6 / 1993
4 / 5 / 1992
8 / 5 / 1993

Step 2: Sort the entire list by year (col 2)

1 / 2 / 1991
2 / 1 / 1991
3 / 4 / 1992
4 / 5 / 1992
5 / 6 / 1993
8 / 5 / 1993

Step 3: For each unique year, sort that sublist by the column near it (col 1)

2 / 1 / 1991
1 / 2 / 1991
3 / 4 / 1992
4 / 5 / 1992
8 / 5 / 1993
5 / 6 / 1993

Step 4: Do the same for the sublist of each unique month of that year (col 0)

1 / 1 / 1991
2 / 2 / 1991
3 / 4 / 1992
4 / 5 / 1992
8 / 5 / 1993
5 / 6 / 1993

And that should be it. I've used the following functions to try and it:

#Sorts the sublist date_list[position..position+length] by the col
def insertion(date_list, position, length, col):
    for i in range (position + 1, pozition + lenght - 1):
        aux = date_list[i]
        j = i - 1

        while j >= 0 and aux[col] < date_list[j][col]:
            date_list[j+1] = date_list[j]
            j -= 1

        date_list[j+1] = aux

    return date_list

def sortDateList(date_list, position, lenght, col):
    # Nothing to do here
    if col < 0:
        return date_list

    # If it's the first sort, sort everything
    if col == 2:
        date_list = insertion(date_list, 0, len(date_list), 2)

    for i in range (position, position + length - 1):
        # Divides the list into sublists based on the column
        if date_list[i][col] == date_list[i][col]:
            length += 1
        else:
        # Sorts the sublist, then sorts it after the previous column in it
            date_list = insertion(date_list, position, length, col)
            date_list = sortDateList(date_list, position, length, col - 1)
            position += length
            length = 1

    date_list = insertion(date_list, position, length, col)

    return date_list

I'm not sure exactly what the problem is here, I'm pretty sure it's something really basic that slipped my mind, and I can't keep track of recursion in my brain that well. It gives me some index out of bound errors and such.

For debug, I've printed out info as such:

col position position + length
date_list[position:position+length] before insertion()
date_list[position:position+length] after  insertion()

Here is what the console gives me:

2 0 6
2 0 7
[[1, 2, 1991], [2, 1, 1991], [3, 4, 1992], [4, 5, 1992], [5, 6, 1993], [8, 5, 1993]]
[[1, 2, 1991], [2, 1, 1991], [3, 4, 1992], [4, 5, 1992], [5, 6, 1993], [8, 5, 1993]]
1 0 7
[[1, 2, 1991], [2, 1, 1991], [3, 4, 1992], [4, 5, 1992], [5, 6, 1993], [8, 5, 1993]]
[[2, 1, 1991], [1, 2, 1991], [3, 4, 1992], [4, 5, 1992], [8, 5, 1993], [5, 6, 1993]]
0 0 7
[[2, 1, 1991], [1, 2, 1991], [3, 4, 1992], [4, 5, 1992], [8, 5, 1993], [5, 6, 1993]]
[[1, 2, 1991], [2, 1, 1991], [3, 4, 1992], [4, 5, 1992], [5, 6, 1993], [8, 5, 1993]]
0 7 8
[]
[]
0 8 9
[]
[]
0 9 10
[]
[]
0 10 11
[]
[]
0 11 12

Any help is greatly appreciated!

Answer 1

Just write a simple sort algorithm and a compare function, such as this:

date_list = [[1,2,1991],[2,1,1991],[3,4,1992],[5,6,1993],[4,5,1992],[8,5,1993]]

# first compare years, if equal compare months, if equal compare days
def compare(date1,date2):
    if date1[2] != date2[2]:
        return date1[2]<date2[2]
    if date1[1] != date2[1]:
        return date1[1]<date2[1]
    return date1[0] < date2[0]

for i in range(len(date_list)):
    for j in range(i+1,len(date_list)):
        if not compare(date_list[i],date_list[j]):
            date_list[i],date_list[j] = date_list[j],date_list[i]

print date_list

The time complexity is O(n^2) but you can improve it by using a more efficient sort algorithm.

Answer 2

If you convert it to YYYYMMDD string format you can easily sort it. Try to sort string concatinated data instead of spiting it to 3 part.