Sort a list using selection sort

Question

I have a list of lists, that I want to sort based on the first element of the lists in ascending order. If the first elements of the list are the same, they should be sorted on the basis of the second element.

So far I have been able to sort based on only the first elements of the list. I have used insertion sort for sorting them. How do I sort the list based on second element if first elements are same?

def sort_list ():
    # An example of the list to be sorted
    original_list = [['Glenn', 'Stevens'],
                    ['Phil', 'Wayne'],
                    ['Peter', 'Martin'],
                    ['Phil', 'Turville'],
                    ['Chris', 'Turville']]

    sorted_list = list(original_list)

    for index in range(1, len(sorted_list)):           
        pos = index                                 
        while pos > 0 and sorted_list[pos - 1][0] > sorted_list[pos][0]:    
            sorted_list[pos-1], sorted_list[pos] = sorted_list[pos], sorted_list[pos-1]
            pos -= 1                            

    return sorted_list

uhh… the built-in list.sort already does this. Use sorted if you don't want to destroy original_list — inspectorG4dget
– inspectorG4dget, Commented Jan 27, 2013 at 9:02
The function should be an implementation of insertion sort so I can't use the list.sort method. I also need the original list unchanged. — SUB0DH
– SUB0DH, Commented Jan 27, 2013 at 9:10
sorted_list = list(original_list) is better written as sorted_list = original_list[:] — Burhan Khalid
– Burhan Khalid, Commented Jan 27, 2013 at 9:17

Igor Chubin · Accepted Answer · 2013-01-27 10:43:01Z

2

If you want to use your own function for sorting, you can do it.

To check the second elements if the first are equal just write

   (sorted_list[pos - 1][0] > sorted_list[pos][0] 
or (sorted_list[pos - 1][0] == sorted_list[pos][0] 
    and sorted_list[pos - 1][1] > sorted_list[pos][1]))

instead of

sorted_list[pos - 1][0] > sorted_list[pos][0]

Actually you could write it shorter:

sorted_list[pos - 1] > sorted_list[pos]

That is exactly what you need.

When python compare lists, it compares their elemts starting from the first [0]:

>>> a=[1,2]
>>> b=[1,1]
>>> a<b
False
>>> a=[1,2]
>>> b=[1,3]
>>> a<b
True
>>> a=[1,2]
>>> b=[2,1]
>>> a<b
True

edited Jan 27, 2013 at 10:43

answered Jan 27, 2013 at 9:13

Igor Chubin

65.2k14 gold badges132 silver badges149 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

SUB0DH Over a year ago

Looks like a lot to write on a single line. Anyways, thanks for the code.

Paul Hankin · Accepted Answer · 2013-01-27 09:41:07Z

List comparison already works the way you want (it's called lexical order): the first items are compared and if they're equal, then the second and subsequent items are compared.

That means you can sort your list with a single line:

original_list.sort()

If you have to implement your own sort, you should implement it in a general way, passing in a key function (like the built-in sorted function).

def insertion_sort(xs, key=(lambda x: x)):
    result = list(xs)
    for i in xrange(len(result)):
        for pos in xrange(i, 0, -1):
            if key(result[pos-1]) <= key(result[pos]):
                break
            result[pos-1], result[pos] = result[pos], result[pos-1]
    return result

Now you can sort by the first element of each sublist:

print insertion_sort(xs, key=(lambda x: x[0]))

Or by lexical order:

print insertion_sort(xs)

Collectives™ on Stack Overflow

Sort a list using selection sort

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related