CODEWITHSUNDEEP
pythonpython-3.xsorting
Fouad Boukredine
Fouad Boukredine

Reputation: 1633

Insertion sort in python with negative numbers at the end of the list

I used the sorting algorithm to sort numbers like positives first and then negatives (swapping in place, you can use variables but without using any container variables. Just assume we don't have more memory space for extra containers). So the sorted positive numbers first, then the sorted negatives.

I did it, but I needed another for loop for the negatives to sort and insert them at the end of the list.

My question: is there a way to modify the first loop to achieve the same result? (ie: use only 1 for loop)

for example:

x = [9, -3, 2, -7, -4, -1, 5, 4]

The output should be:

[2, 4, 5, 9, -7, -4, -3, -1]

Here is my solution (but I used 2 for loops, and I want to only use 1):

def insertion_sort(data):
    for i in range(1, len(data)):
        e = i
        while e > 0 and data[e - 1] > data[e]:
            data[e - 1], data[e] = data[e], data[e - 1]
            e -= 1
    for i in range(1, len(data)):
        e = i
        while e > 0 and data[e - 1] < 0:
            if data[e] < 0:
                if data[e - 1] < data[e]:
                    data[e - 1], data[e] = data[e], data[e - 1]
            data[e - 1], data[e] = data[e], data[e - 1]
            e -= 1
    print(data)

Upvotes: 2

Views: 770

Answers (2)

Hemerson Tacon
Hemerson Tacon

Reputation: 2522

You just need to find the pivot value when the numbers start to be positives

def insertion_sort(data):

    pivot = -1
    for i in range(1, len(data)):
        e = i
        while e > 0 and data[e - 1] > data[e]:
            data[e - 1], data[e] = data[e], data[e - 1]
            if data[e] >= 0 and data[e-1] < 0:
                pivot = e
            e -= 1

    data[-pivot:], data[:-pivot] = data[:pivot], data[pivot:]
    print(data)

Upvotes: 2

slider
slider

Reputation: 12990

You can define a function is_greater as follows:

def is_greater(x, y):
    if (x < 0 and y < 0) or (x >= 0 and y >= 0):
        return x > y
    return x < 0

Then you can use this instead of normal int comparison in your first loop:

def insertion_sort(data):
    for i in range(1, len(data)):
        e = i
        while e > 0 and is_greater(data[e - 1], data[e]):
            data[e - 1], data[e] = data[e], data[e - 1]
            e -= 1
    print(data)

insertion_sort(d)

Output

[2, 4, 5, 9, -7, -4, -3, -1]

Upvotes: 2

Related Questions