Quick sort errors in Python language

Question

I am new to python so just to get familiar with the syntax, I am making the programs I have already made in C++ and Java.

def swap(p , q):
    temp = array[p]
    array[p] = array[q]
    array[q] = temp
def partition(beg , end):
    l = beg
    x = array[beg]
    for j in range(l+1,end) :
        if(array[j] <= x):
            l += 1
            swap(l , j)
    swap(l, beg)
    return l
def quick(beg , end):
    if(beg <= end):
        mid = partition(beg , end)
        quick(beg , mid - 1)
        quick(mid + 1 , end)

array = []
n=int(input("\nEnter the number of terms: "))
print("\nEnter the terms")
for i in range(0,n):
    val = int(input())
    array.append(val)
print("\nBefore Sorting: ")
print(array)
quick(0 , n)
print("\nAfter Sorting: ")
print(array)

This is the code that I made in Python for quick sort. It worked in c++ with the same range but it shows the following errors

**

Traceback (most recent call last):
- File "python", line 28, in
- File "python", line 17, in quick
- File "python", line 17, in quick
- File "python", line 17, in quick
- [Previous line repeated 990 more times]
- File "python", line 16, in quick
- File "python", line 8, in partition
- RecursionError: maximum recursion depth exceeded in comparison

Please help. Thank you.

This is probably unhelpful in solving this problem, but style tip: you can swap two values in Python without using a temporary value by doing array[a], array[b] = array[b], array[a] — Kevin
– Kevin, Commented Sep 25, 2017 at 17:40
Well, one obvious bug is that your partition function always returns (n - 1), since that is the value of i in return i refers to the global i, which is last set in the for loop, for i in range(0,n): , did you mean return l? But you really really shouldn't be relying on global state. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Sep 25, 2017 at 17:41
Python has a maximum number of times you can loop or call a function recursively. I believe the value changes from system to system but there is a way to modify it. Really it's best just to break a large chunk into smaller parts and then narrow the larger data into smaller and smaller data. — Preston Hager
– Preston Hager, Commented Sep 25, 2017 at 17:42
@PrestonHager It does, but the problem with this code is that it will recurse infinitely <edited to remove erroneous comment where I confused quick-sort and merge-sort>. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Sep 25, 2017 at 17:44

Jayson Joseph Chacko · Accepted Answer · 2017-09-25 17:59:56Z

1

You program has a number of errors related to boundary conditions. Here is the modified and working solution based on your code. Note that I have changed swap to use the python preferred approach.

def swap(p , q):
    array[p],array[q] = array[q],array[p]

def partition(beg , end):
    l = beg - 1
    x = array[end]
    for j in range(beg,end) :
        if(array[j] <= x):
            l += 1
            swap(l , j)
    swap(l+1, end)
    return l+1

def quick(beg , end):
    if(beg < end):
        mid = partition(beg , end)
        quick(beg , mid - 1)
        quick(mid + 1 , end)


array = []
n=int(input("\nEnter the number of terms: "))
print("\nEnter the terms")
for i in range(0,n):
    val = int(input())
    array.append(val)
print("\nBefore Sorting: ")
print(array)
quick(0 , n-1)
print("\nAfter Sorting: ")
print(array)

answered Sep 25, 2017 at 17:59

Jayson Joseph Chacko

2,4031 gold badge13 silver badges16 bronze badges

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

Comments

mypetlion · Accepted Answer · 2017-09-25 17:44:48Z

0

Probably because partition returns i. That seems to be your loop variable for taking in the original input. So when you call partition to get the mid in the quick function, you're getting the same value over and over again. In python, loop variables stick around after the loop is done running.

answered Sep 25, 2017 at 17:44

mypetlion

2,5445 gold badges21 silver badges22 bronze badges

Collectives™ on Stack Overflow

Quick sort errors in Python language

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related