Run time error for quick and bubble sort.

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 1585 Views - Last Post: 20 March 2013 - 11:43 PM Rate Topic: -----

#1 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • 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  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • 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()

Was This Post Helpful? 0
  • +
  • -

#4 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • 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?
Was This Post Helpful? 0
  • +
  • -

#5 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

#6 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • 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

Was This Post Helpful? 0
  • +
  • -

#7 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • 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??
Was This Post Helpful? 1
  • +
  • -

#8 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • 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

Was This Post Helpful? 0
  • +
  • -

#9 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • 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()

Was This Post Helpful? 1
  • +
  • -

#10 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • 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

Was This Post Helpful? 0
  • +
  • -

#11 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#12 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • 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.
Was This Post Helpful? 0
  • +
  • -

#13 medaa  Icon User is offline

  • D.I.C Head

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

Re: Run time error for quick and bubble sort.

Posted 20 March 2013 - 11:34 PM

Sounds good.
Was This Post Helpful? 0
  • +
  • -

#14 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • 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.
Was This Post Helpful? 0
  • +
  • -

#15 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2