Comb Sorting Program

Question

I am trying to write a program in python which should sort a list within a list.

Examples -

List before sorting: [[2, 1], [2, 2], [3, 3], [3, 1], [1, 1], [1, 2]] 
List after sorting: [[1, 1], [1, 2], [2, 1], [2, 2], [3, 1], [3, 3]]

List before sorting: [[3, 3], [2, 2], [1, 2], [2, 1], [3, 1], [1, 1]]
List after sorting: [[1, 1], [2, 1], [1, 2], [2, 2], [3, 1], [3, 3]]

List before sorting: [[1, 1], [3, 3], [2, 1], [2, 2], [1, 2], [3, 1]]
List after sorting: [[1, 1], [1, 2], [2, 1], [2, 2], [3, 1], [3, 3]]

My code:

import math

def combsort(list1):
    gap = len(list1)
    shrink = 1.3
    sorted = False

    while sorted == False:
        gap = gap/shrink
        if gap > 1:
            sorted = False
        else:
            gap = 1
            sorted = True

        i = 0
        while i + gap < gap:
            distance1 = math.sqrt(list1[i[0]]**2 + list1[i[1]]**2)
            distance2 = math.sqrt(list1[i+gap[0]]**2 + list1[i+gap[1]]**2)
            if distance1 > distance2:
                temporary = list1[i]
                list1[i] = list1[i + gap]
                temporary = list1[i + gap]
                sorted = False
            i = i + 1

list1 = [[2, 1], [2, 2], [3, 3], [3, 1], [1, 1], [1, 2]] 
combsort(list1)
print(list1)

My code doesn't work and prints out the exact same list. Any help?

This is what I was given to follow:

Comb sort is a variation of bubble sort that generally performs more efficient sorting. It accomplishes this by moving low values near the end of the list further toward the front of the list than bubble sort would during early iterations.

implement a function called combsort that does the following:

Takes as input a 2D list that contains information representing x/y points in 2D space. Each item in the list will be a list with 2 items an x and a y coordinate. For example, the list could be [ [0, 1],[2, 1], [3, 3], [1, 1], … ]

List item Performs an in-place sort (i.e., does not create a new list, but modifies the original) using the comb sort algorithm that sorts the 2D list such that points with lower 2 Euclidean distance to the origin (0, 0) appear earlier in the list. In this case, you are comparing distances instead of directly comparing list values – it may be useful to implement and use a distance calculation function. Note – the Euclidean distance of a point (x, y) from the origin (0, 0) can be calculated with the following equation: distance(x,y) = �! + �!

Does not return a value. As the input list is sorted in place, it will be modified directly and these modifications will be reflected outside the function, so a return value is not needed.

Please explain the logic behind your desired order; for example, why does [1,2] sometimes come before [2,1] but not always? — Scott Hunter, Apr 08 '17 at 00:11
@ScottHunter I thought this was a typo, but it is indeed correct. Since the distance is how they're sorted, `[1,2]` and `[2,1]` are equivalent values, and thus their order depends on initial position. — River, Apr 08 '17 at 00:32
If `i` is any integer value greater than `-1`, the code inside the `while i + gap < gap:` loop can never execute. — martineau, Apr 08 '17 at 01:05
@River: Although the clarity of my feelings to you isn't important, I did it to specify the reason in more mathematical terms. — martineau, Apr 08 '17 at 01:15

score 0 · Answer 1 · answered Apr 08 '17 at 00:10

0

The while loop never gets executed because its condition cannot be true:

while i + gap < gap:

Hint: use more print statements or a debugger to check the values of things while the program is running.

answered Apr 08 '17 at 00:10

RecencyEffect

736
7
18

score 0 · Answer 2 · edited May 23 '17 at 12:17

0

The error is in your while statement, it should be:

while i + gap < len(list1):

as shown in the pseudocode here. Currently the while loop is never even entered... which hides your other problems (see below).

You are indexing into a 2-D list wrong:

list1[i[0]] #get first item in list `i` and use that number to index into list1
list1[i][0] #get the ith sublist in list1 and get its first item

You need to make sure you use integers for your list indices:

gap = int(gap/shrink)

And for the grand finale....you swapped the order of your assignment, ruining your swap logic

temporary = list1[i + gap] #wrong
list1[i + gap] = temporary #should be this

You can also do this without the use of temporary in Python:

list1[i+gap], list1[i] = list1[i], list1[i+gap]

After all these changes, the code works as expected:

>>>combsort([[3, 3], [2, 2], [1, 2], [2, 1], [3, 1], [1, 1]])
[[1, 1], [2, 1], [1, 2], [2, 2], [3, 1], [3, 3]]

edited May 23 '17 at 12:17

Community

1
1

answered Apr 08 '17 at 00:12

River

8,585
14
54
67

I've done everything. Except I don't understanding the indexing into a 2-d list part? Can you please explain that part more? – User9123 Apr 08 '17 at 00:43
If you have 2D list, it is just like any other list. Take `list1` as an example. If we want the first item, we say `x = list1[0]`, just as with a 1D list. However in this case, `x` is *itself* a list. If we want the first item in that, we do the same as with `list1` and say `y = x[0]`. Subbing `list1[0]` for `x` (they are the same after all), gets us `y = list1[0][0]`, or "`y` is the first item in the first item of `list1`". Note that this assumes the first item of `list1` is also a list. – River Apr 08 '17 at 00:54
Now look at what it would mean if we do what you did with `list1[i[0]]`. The innermost item you have is `i[0]`. This means "get the first item of list `i`". But `i` is not a list so this will error. If `i` *were* a list, then `list1[i[0]]` would mean "Use this first item of `i` to index into `list1`". E.g. if `i = [2,3,4]`, `i[0] = 2` and so `list1[i[0]]` is `list1[2]`, or the third item of `list1`. Note that this assumes `i[0]` is an integer, otherwise it can't be used to index into a list, and will also give you an error. – River Apr 08 '17 at 01:00
I separated them. Still not working? I get an error code on the distance2. distance1 = math.sqrt(list1[i][0]**2 + list1[i][1]**2) distance2 = math.sqrt(list1[i]+gap[0]**2 + list1[i]+gap[1]**2) – User9123 Apr 08 '17 at 01:27
@User9123 You want `list1[i+gap][0]` (and similar for second part). `gap` is not a list as `gap[0]` assumes, so that's why you get the error. – River Apr 08 '17 at 01:29
@User9123 also if this post solved your problem, you can accept it using the check mark next to it – River Apr 23 '17 at 17:13

Comb Sorting Program

2 Answers2