CODEWITHSUNDEEP
pythonalgorithmquicksortdata-partitioning
Madison John
Madison John

Reputation: 77

Algorithm does not sort array as expected

I got the following algorithm with [3, 7, 5 ,2, 1, 4, 8] input. It is said that is part of QuickSort and it constructs a partition position.. The output should be [3, 1, 2, 5, 7, 4, 8] enter image description here

I used the following python code:

def partition(x, s, d):
    v = x[s]
    i = s-1
    j = d+1
    while i < j:
        while True:
            i = i+1 
            if x[i] >=v:
                break
        while True:
            j = j-1 
            if x[j] <=v:
                break 
        if (i<j):
            x[i], x[j] = x[j], x[i]
            
    print (x)
    return j
    
    
x = [3, 7, 5, 2, 1, 4, 8]
partition(x, 1, 6)

I can't get [3, 1, 2, 5, 7, 4, 8] which is allegedly the right result here. Please help, I tried with different values for s and d which most probably stands for left and right.

Upvotes: 1

Views: 84

Answers (3)

Ram
Ram

Reputation: 4779

This is Partition Algorithm of Quicksort.

Since we use a while loop instead of a do.. while (This is what is mentioned in your algorithm REPEAT... UNTIL), we don't need to decrement s and increment d.

def partition(x, s, d):
    v = x[s]
    i = s
    j = d
    
    while i < j:
        while x[i] <= v:
            i += 1
        
        while x[j] >= v:
            j -= 1

        if (i<j):
            x[i], x[j] = x[j], x[i]
            
    print(x)
    return j
    
    
x = [3, 7, 5, 2, 1, 4, 8]
partition(x, 0, 6)


Output:

[3, 1, 2, 5, 7, 4, 8]

Upvotes: 2

LaytonGB
LaytonGB

Reputation: 1404

When i and j are defined, they are equal to the start index minus 1, and the end index plus 1. If these indexes are used they will be out of range so you will get an error. Hence, when the code arrives at the REPEAT ... UNTIL sections, the minus 1 and plus 1 are immediately undone. To avoid this issue I've used this code:

lis = [3,7,5,2,1,4,8]

def partition(x,s,d):
    v = x[s]
    i = s
    j = d
    while i < j:
        while x[i] <= v:
            i += 1
        while x[j] >= v:
            j -= 1
        if i < j:
            x[i], x[j] = x[j], x[i]
    return j
    
position = partition(lis, 0, 6)
print(position)
print(lis)

Output:

2
[3, 1, 2, 5, 7, 4, 8]

I believe the position can be used to partition the list and sort it further, but due to the lack of information I'm not sure how best to do that.

Thanks to the other answer I believe the confusion was arising from the REPEAT ... UNTIL condition statements. By making my statements <= rather than just < I've gained the desired output.

Upvotes: 1

Epsi95
Epsi95

Reputation: 9047

def partition(x, s, d):
    v = x[s]
    i = s-1
    j = d+1
    while i < j:
        while True:
            i = i+1 
            if x[i] >v: #--->
                break
        while True:
            j = j-1 
            if x[j] <v: #--->
                break
        if (i<j):
            x[i], x[j] = x[j], x[i]
            
    print (x)
    return j
    
    
x = [3, 7, 5, 2, 1, 4, 8]
partition(x, 0, len(x)-1) #---->

[3, 1, 2, 5, 7, 4, 8]

Upvotes: 0

Related Questions