# Run time error for quick and bubble sort.

• (2 Pages)
• 1
• 2

## 15 Replies - 2531 Views - Last Post: 20 March 2013 - 11:43 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=316101&amp;s=d35974d3be15f04fcd8260cf1f602457&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

# Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:00 AM

```import random
import time

def quick_sort(alist):
quick_sort_helper(alist,0,len(alist)-1)

# a recursive quick sort method
def quick_sort_helper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
quick_sort_helper(alist,first,splitpoint-1)
quick_sort_helper(alist,splitpoint+1,last)

# to partition the given list by
# (1) picking the first int as the pivot value
# (2) re-arrange all integers accoding to the pivot value
def partition(alist,first,last):
pivotvalue = alist[first]

leftmark = first+1
rightmark = last

done = False
while not done:

while leftmark <= rightmark and \
alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and \
rightmark >= leftmark:
rightmark = rightmark -1

if rightmark < leftmark:
done = True
else:
# exchange integers pointed by the
# leftmark and rightmarks
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp

temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp

return rightmark

def bubble_sort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]

def do_quick_sort(alist):
integer = random.randint(0, 1000)
quick_sort(alist)
def do_bubble_sort(seq):
integer = random.randint(0, 1000)
bubble_sort(alist)

def main():

alist=list(range(1,1000))

start1=time.time()
quick=do_quick_sort(alist)
end1=time.time()
time_interval1=end1-start1
print("Quick sort:",time_interval1)

start2=time.time()
bubble=do_bubble_sort(alist)
end2=time.time()
time_interval2=end2-start2
print("Bubble sort:",time_interval2)

main()
```

So im trying to test which sorting method is better but its not working.
I keep getting this error: builtins.RuntimeError: maximum recursion depth exceeded in comparison because of this line quick=do_quick_sort(alist) and this line bubble=do_bubble_sort(alist)
Can I please get some help.
I dont know if this will help be these are the steps I was given:
1. Generate a list with n randomly chosen integers by using
random.randint(x,y)
2. Use list2 = list(list1) to reproduce the list you got from step 1.
3. Use the code we give on next page to count the runtime of each
sorting function.
4. Print the runtime for each sorting function on screen.
5. Change n to some different values and redo this experiment.

Is This A Good Question/Topic? 0

## Replies To: Run time error for quick and bubble sort.

### #2 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 04:34 PM

It would help if you started by looking at the error and examine what it says and what it means. On my system, the default recursion depth is 975. That means I can make a function recursively call itself 975 times before resolving without any problem. Your function is exceeding your system's default recursion depth. This likely means that you're making way too many recursive calls.

### #3 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 04:55 PM

okay so I adjusted my range for a list.
Can you help me with this point: Use list2 = list(list1) to reproduce the list you got from step 1
where would I put this exactly?

Heres the new code:
```import random
import time

def quick_sort(alist):
quick_sort_helper(alist,0,len(alist)-1)

# a recursive quick sort method
def quick_sort_helper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
quick_sort_helper(alist,first,splitpoint-1)
quick_sort_helper(alist,splitpoint+1,last)

# to partition the given list by
# (1) picking the first int as the pivot value
# (2) re-arrange all integers accoding to the pivot value
def partition(alist,first,last):
pivotvalue = alist[first]

leftmark = first+1
rightmark = last

done = False
while not done:

while leftmark <= rightmark and \
alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and \
rightmark >= leftmark:
rightmark = rightmark -1

if rightmark < leftmark:
done = True
else:
# exchange integers pointed by the
# leftmark and rightmarks
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp

temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp

return rightmark

def bubble_sort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]

def do_quick_sort(list1):
integer = random.randint(0,900)
quick_sort(list1)
def do_bubble_sort(list1):
integer = random.randint(0,900)
bubble_sort(list1)

def main():

list1=list(range(1,900))

start1=time.time()
quick=do_quick_sort(list1)
end1=time.time()
time_interval1=end1-start1
print("Quick sort:",time_interval1)

start2=time.time()
bubble=do_bubble_sort(list1)
end2=time.time()
time_interval2=end2-start2
print("Bubble sort:",time_interval2)

main()
```

### #4 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 04:57 PM

I'm not a fan of simply giving you code. So, let's back up. Do you know WHY you need to make a copy of the list?

### #5 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 06:08 PM

Well my guess is your making a new list so you can sort it and find a new element.

### #6 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:11 PM

I think you have the right idea. To say it more clearly, the reason you need 2 lists is because you're running 1 sort then then other. If you only have 1 list then the second sort method will be given a pre-sorted list. That's not a very fair comparison, don't you think? Both sort methods should be given identical, unsorted lists. Knowing this, where do you think that line should go?

This post has been edited by atraub: 20 March 2013 - 11:12 PM

### #7 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:18 PM

So here's a wild guess, maybe list1 is passed to quick sort and list2 is passed to bubble sort, this way they both receive the same list??

### #8 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:21 PM

that's correct! so that means, all you need to do is make list2 at some point before list1 gets sorted

EDIT:
You probably don't want to do it in a place where it'll affect your timing though

This post has been edited by atraub: 20 March 2013 - 11:23 PM

### #9 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:26 PM

so like this:
```import random
import time

def quick_sort(alist):
quick_sort_helper(alist,0,len(alist)-1)

# a recursive quick sort method
def quick_sort_helper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
quick_sort_helper(alist,first,splitpoint-1)
quick_sort_helper(alist,splitpoint+1,last)

# to partition the given list by
# (1) picking the first int as the pivot value
# (2) re-arrange all integers accoding to the pivot value
def partition(alist,first,last):
pivotvalue = alist[first]

leftmark = first+1
rightmark = last

done = False
while not done:

while leftmark <= rightmark and \
alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and \
rightmark >= leftmark:
rightmark = rightmark -1

if rightmark < leftmark:
done = True
else:
# exchange integers pointed by the
# leftmark and rightmarks
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp

temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp

return rightmark

def bubble_sort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]

def do_quick_sort(list1):
integer = random.randint(0,900)
quick_sort(list1)
def do_bubble_sort(list2):
integer = random.randint(0,900)
bubble_sort(list2)

def main():

list1=list(range(1,900))
list2=list(list1)

start1=time.time()
quick=do_quick_sort(list1)
end1=time.time()
time_interval1=end1-start1
print("Quick sort:",time_interval1)

start2=time.time()
bubble=do_bubble_sort(list2)
end2=time.time()
time_interval2=end2-start2
print("Bubble sort:",time_interval2)

main()
```

### #10 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:27 PM

Looks good to me.

On an additional note, if you're ever interested, Python provides a module called timeit which is a more precise way of measuring the time it takes to run code.

This post has been edited by atraub: 20 March 2013 - 11:29 PM

### #11 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:29 PM

Thanks a lot, wonderful at explaining!! Ps. Is bubble actually slower or faster, my program is saying its faster?

### #12 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:32 PM

Bubble should be pretty slow, you may want to re-examine some stuff. I'll take a look too.

### #13 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:34 PM

Sounds good.

### #14 atraub

• Pythoneer

Reputation: 828
• Posts: 2,235
• Joined: 23-December 08

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:39 PM

Actually, because of the recursive nature of quick sort, it might be a bit slower.

### #15 medaa

Reputation: 6
• Posts: 106
• Joined: 24-October 12

## Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:41 PM

Okay, cause I can't find anything that looks odd