1

For an assignment I have to create my own sorting algorithm to sort a list containing football scores.

The information is formatted as follows (with multiple sublists like this): 

['Netherlands', 7, 6, 0, 1, 12, 6, 6, 18]

First it should be sorted according to index 8, then if the numbers for index 8 are the same it should be sorted according to index 7, etcetera

I've managed to sort it according to index 8, but got stuck after that. So I'm using selection sort here:

def Sorting(List, sortVar):

    for index in range(len(List)):
        cur_pos = stats[index][sortVar]
        high = List[index]
        loc = index

        for i in range(index,len(List)):
            if stats[i][sortVar] > cur_pos:
                cur_pos = List[i][sortVar]
                high = List[i]
                loc = i

        temp = List[index]
        List[index] = high
        List[loc] = temp


    print("")
    print(List)
    return List

And then after this I've tried some things but gotten stuck. Might be a really simple question, but I'm really struggling. Thanks!

Edit: I've seen some posts explaining this, but I didn't understand them and they all used inbuilt sorting functions, which I'm not allowed to do...

Improve this question
13
  • It's unclear what you want from us here. What exactly is the desired input and output? What sorting algorithm do you want to implement? I assume you want to avoid Python builtin sorted()/list.sort? Commented Apr 24, 2017 at 12:23
  • 1
    Are you allowed to use sort or sorted with a tailored key? Commented Apr 24, 2017 at 12:24
  • 2
    @EricDuminil: I have to create my own sorting algorithm. Sounds ilke "nope". Commented Apr 24, 2017 at 12:27
  • Reverse all sublists, sort normally, re-reverse each sublist. Commented Apr 24, 2017 at 12:30
  • The input should be a list with 32 sublists of the form ['Netherlands', 7, 6, 0, 1, 12, 6, 6, 18] . The output should be this list sorted first on index 8, then if entries for index 8 are the same for index 1, etcetera. (Sorry hope this is clear, I'm very new to programming) I want to implement a sorting algorithm as the one I put in the original post, which they called: "selection sort" in my lectures. I cannot use sort or sorted. I hope this is a bit clearer @Chris_Rands? So in the end we want to know which country would have the highest rating. Commented Apr 24, 2017 at 12:34

2 Answers 2

Reset to default
2

Here's a basic bubble sort:

def bubble_sort(items):
    """ Implementation of bubble sort """
    for i in range(len(items)):
        for j in range(len(items) - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]     # Swap!

Here's a modified bubble sort. It just reverses both items before comparing them. Both compared elements must understand [::-1]:

def modified_bubble_sort(items):
    for i in range(len(items)):
        for j in range(len(items) - 1 - i):
            # Reverse the lists before comparing them
            if items[j][::-1] > items[j + 1][::-1]:
                items[j], items[j + 1] = items[j + 1], items[j]     # Swap!

It's not efficient because bubble sort is O(n**2) and the modified version keeps on reversing the same lists, but it's quite clear and concise.

Here's a test:

scores = [
    ['Netherlands', 7, 6, 0, 1, 12, 6, 6, 19],
    ['Netherlands', 7, 6, 0, 1, 12, 6, 6, 19],
    ['Netherlands', 7, 6, 0, 1, 12, 6, 7, 18],
    ['Netherlands', 7, 6, 0, 1, 12, 6, 6, 18],
    ['Spain', 7, 6, 0, 1, 12, 6, 7, 18]
]

modified_bubble_sort(scores)
print(scores)

Note that it modified the original list in place. It outputs:

[['Netherlands', 7, 6, 0, 1, 12, 6, 6, 18], ['Netherlands', 7, 6, 0, 1, 12, 6, 7, 18], ['Spain', 7, 6, 0, 1, 12, 6, 7, 18], ['Netherlands', 7, 6, 0, 1, 12, 6, 6, 19], ['Netherlands', 7, 6, 0, 1, 12, 6, 6, 19]]

Which is the same result as with:

print(sorted(scores, key=lambda l: l[::-1]))
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Whoops, I lost track of my post, but thanks for the answer!!
@Jayk: No problem. Please accept the answer if it solves your problem.
1

I'd say the easiest way (if you're allowed to use built-ins) is to reverse each sublist, sort numerically-lexicographically, then re-reverse each sublist.

def my_sort(l):
    # Reverse so you can sort numerically-lexicographically
    reversed_lists = [x[::-1] for x in l]

    # Sort "normally" (i.e., numerically-lexicographically)
    reversed_lists.sort()

    # Re-reverse each sublist so they fit your expected return format
    return [x[::-1] for x in reversed_lists]

See it in action here.

If you're not allowed to use built-ins, you will need to design the sorting bit yourself, but the logic remains the same.

You could also just use the key kwarg to sort the reverse sublists:

def my_sort(l):
    return list(sorted(l, key=lambda subl: subl[::-1]))
Improve this answer

5 Comments

I see how this works for sorting it on the basis of the first sorting parameter. However, I'm do not see how I should implement this for tiebreakers with other criteria without changing the order of the whole list and thus neglecting the previous sorting parameter(s)?
@Jayk "Tie breakers" are handled naturally by sorting.
You can see this when you check in the interpreter: [1, 2, 3] > [1, 2, 2] and [1, 2, 3, 'Spain'] > [1, 2, 3, 'Netherlands'].
How would you implement this when for the different indexes, there are different "rules". If the "tiebreaker" falls on say index 1 for Netherlands is smaller than for Spain, this means Netherlands goes up in ranking (change place in the list). But when the "tiebreaker" falls on index 2, the value that is bigger moves up in the list.
@Jayk That's what sorting is.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.