Trouble sorting list of lists in Python with Insertion Sort

I am currently making a Python program which takes in the name of a grocery item, the aisle it’s on, its location along the aisle, and the price. It holds the data in a list of lists, with each inner list containing 4 elements. The program attempts to create the optimal route through the aisles, with traversal on odd aisles going up (location 1 to loc. N) and traversal on even aisles going down (loc. N to 1). The code is below:

def sort_aisles(data):
    for item in range(1, len(data)):
        key = data[item]
        j = item - 1

        while j >= 0 and key[1] < data[j][1]:
            print('start first while loop', data)
            print()
            if data[j][1] == data[j + 1][1]:
                if int(data[item][1]) % 2 == 0:
                    # even
                    while j >= 0 and key[2] > data[j][2]:
                        print('start even while loop', data)
                        print()
                        data[j + 1] = data[j]
                        j = j - 1
                        print('end even while loop', data)
                        print()
                else:
                    # odd
                    while j >= 0 and key[2] < data[j][2]:
                        print('start odd while loop', data)
                        print()
                        data[j + 1] = data[j]
                        j = j - 1
                        print('end odd while loop', data)
                        print()
            data[j + 1] = data[j]
            j = j - 1

        data[j + 1] = key
        print('end first while loop', data)
        print()
    return data


def display_route(data):
    total = 0
    for item in range(len(data)):
        total += float(data[item][3])
        print('{:<15} Aisle {:>2} Location {:>2} + {:>6.2f} = {:>6.2f}'.format(data[item][0].title(), data[item][1], data[item][2], float(data[item][3]), total))


def main():
    # Prompt
    data = []
    input_data = input('Name, aisle, location, price? ')
    data.append(input_data.split(','))
    print()
    while input_data.lower() != 'done':
        input_data = input('Name, aisle, location, price? ')
        data.append(input_data.split(','))
        print()
    data.pop()
    # Remove whitespace
    data = [[element.strip() for element in items] for items in data]
    # Testing
    sorted_data = sort_aisles(data)
    display_route(sorted_data)


if __name__ == '__main__':
    main()

Here is a more specific prompt:

Idea:

Go down aisle 1 from location 1 to N, then up
- aisle 2 from location N to 1, et cetera.
Store can have any number of aisles and any number of loc. per aisle.
Odd aisles traverse from loc. 1 to N, even from loc. N to 1.

Algorithm:

Prompt for:
- item name
- aisle number
- location number
- price
until done is entered (don’t include done)
user enters commas between each value
may be additional spaces before/after commas
keep list of lists (items); each item in list will have name, aisle, loc. and price
data[n][1] = nth aisle, data[m][2] = mth loc.
sort list of items
- odd aisles sort by ascending location
- even sort by descending location

My issue is with sorting. I am using a nested insertion sort currently, but it does not sort as I expect. The example input I have been using to test is as follows:

Name, aisle, location, price? peanut butter, 3, 5, 1.75

Name, aisle, location, price? fuji apples, 2, 8, 1.50

Name, aisle, location, price? bananas, 2, 1, 2.00

Name, aisle, location, price? potato chips , 3, 3, 2.50

Name, aisle, location, price? cookies,10,5,0.75

Name, aisle, location, price? done

Fuji Apples Aisle 2 Location 8 + 1.50 = 1.50

Bananas Aisle 2 Location 1 + 2.00 = 3.50

Potato Chips Aisle 3 Location 3 + 2.50 = 6.00

Peanut Butter Aisle 3 Location 5 + 1.75 = 7.75

Cookies Aisle 10 Location 5 + 0.75 = 8.50

I attempted to use print statements to display what is going on within each loop, but they ended up confusing me more. Here is a pastebin link with the debug information: https://pastebin.com/JWpTPkjJ

For example, the fifth line states it is the end of the first while loop, however the while loop had just output that message previously.

As for what I have tried, initially I had two functions: one which sorted the aisles first using a single insertion sort, which worked wonderfully, and one which sorted locations afterwards using essentially the same code as is in the first if statement in the sort_aisles function. The locations did not sort properly and even caused the cookies on aisle 10 to jump to the top for some reason, so I merged them together, which at least moved the cookies to its rightful spot, but ruined the ordering of the previous items.

I am certain the issue lies in my algorithm for sorting, but I have not been able to figure out what is going wrong. Any help with fixing the sorting algorithm would be much appreciated. Apologies if the post is a bit long, but I felt all of the details were important.

Answer

So, we want to sort the items in one direction (ascending) on odd aisles and in the other (descending) on even aisles. This means we need to sort by the location number on odd aisles, and the negative of the location number on even aisles. Then we need to take each aisle and sort them by aisle number.

We can do this by writing a key function for the .sort() method. For each item in the list being sorted, the key function returns a value that will sort the items in the correct order. Since we want the items sorted by aisle first, then by the location in that aisle (either ascending or descending), our key function will return two values: the aisle number, and the location number (negated in the case of even aisles).

The aisle is the second number [1] in your record and the location in the aisle is the third item [2]. So:

def shop_sequence(record):
    return record[1], record[2] if record[1] % 2 else -record[2]

Now we just sort using that key function:

data.sort(key=shop_sequence)

Advertisement

Answer