Algorithm does not sort array as expected

Question

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]

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.

I agree with the comment that was just removed that the 2nd parameter here should be a zero, else you don't sort the first number.. — Surt
– Surt, Commented Jul 8, 2021 at 11:55
I removed my comment because if the second parameter is 0 line 6, UNTIL x[i] >= v has an index out of range error. @Surt — LaytonGB
– LaytonGB, Commented Jul 8, 2021 at 11:58
@LaytonGB I thought so too, but the algorithm actually increment before checking the index. — Surt
– Surt, Commented Jul 8, 2021 at 12:01

Ram · Accepted Answer · 2021-07-08 12:28:52Z

2

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]

edited Jul 8, 2021 at 12:28

answered Jul 8, 2021 at 12:06

Ram

4,7892 gold badges17 silver badges23 bronze badges

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

Comments

LaytonGB · Accepted Answer · 2021-07-08 12:11:11Z

1

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.

edited Jul 8, 2021 at 12:11

answered Jul 8, 2021 at 12:03

LaytonGB

1,4041 gold badge10 silver badges23 bronze badges

1 Comment

Surt Over a year ago

Doing away with the silliness of -1 also works. And you don't need the aux, the OPs swap should be good.

Epsi95 · Accepted Answer · 2021-07-08 12:10:38Z

0

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]

answered Jul 8, 2021 at 12:10

Epsi95

9,1071 gold badge19 silver badges37 bronze badges

Collectives™ on Stack Overflow

Algorithm does not sort array as expected

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related