hi i got this program how do i sort this....thanx alot
http://www.ee.umanitoba.ca/~pcard/371/assignment1.py

## All 5 Replies

hi there, i was using quicksort method
but when it comes to leng() it gives me this error
and i have no idea how to fix it

C:\Python24>python quicksort.py 100
Traceback (most recent call last):
File "quicksort.py", line 55, in ?
end = len(list)-1
TypeError: len() of unsized object

Give me an example of your list.
Also, wouldn't use list as variable name since list() is built-in function, just as len().

im using quicksort algorithm but it seems to have a problem somethin is gone wrong with my prog. any help is greatly appreciated.... thanx

``````#!/usr/bin/python
from sys import *
import random # for generating random numbers
import time # for timing each sort function with time.clock()
class Item:
def __init__(self,data,next):
self.data = data
self.next = next

def setNext(self,next):
self.next = next
def getNext(self):
return self.next
def getData(self):
return self.data
class List:
def __init__(self):
self.top = None
self.num = 0

def push(self,data):
self.top = Item(data,self.top)
self.num += 1
def howMany(self):
return self.num
def pop(self):
if self.top == None:
return None
d = self.top.getData()
self.top = self.top.getNext()
self.num-=1
return d
if n == 0:
self.push(n)
return
nx = self.top
for x in range(n):
l = nx
nx = nx.getNext()
if nx == None: break
l.next = Item(data,nx)
self.num+=1
def rem(self,n):
if n==0: # First item in list
d=self.top.getData()
if self.top == None: # No list ?
return None
self.top = self.top.getNext()
self.num-=1
return d

nx = self.top
for x in range(n):
l = nx
nx = nx.getNext()
if nx == None:
return None
d = nx.getData()
l.setNext(nx.getNext())
self.num-=1
return d
def val(self,n):
if n==0:
return self.top.getData()
nx = self.top
for x in range(n):
nx = nx.getNext()
if nx == None: return None
return nx.getData()

def printMe(self):
print '[',
n = self.top
while n != None:
d = n.getData()
print "%d," %(d),
n = n.getNext()
print ']'
def printMe2(self):
print '[',
for d in range(self.num):
d = self.val(d)
print "%d," %(d),
print ']'
#print self.num
print self.howMany()
#print r
print l.howMany()
#print int(sys.argv[1])

print r
#sort

#Partition Function for use within quick sort algorithm
def partition(self,r,start,end):

star=0
end=self.howMany-1
pivot = r[end] # Partition around the last value
bottom = start-1 # Start outside the area to be partitioned
top = end # Ditto
done = False
while not done: # Until all elements are partitioned...
while not done: # Until we find an out of place element...
bottom = bottom+1 # ... move the bottom up.
if bottom == top: # If we hit the top...
done = True # ... we are done.
break
if list[bottom] > pivot: # Is the bottom out of place?
list[top] = list[bottom] # Then put it at the top...
break # ... and start searching from the top.
while not done: # Until we find an out of place element...
top = top-1 # ... move the top down.

if top == bottom: # If we hit the bottom...
done = True # ... we are done.
break
if r[top] < pivot: # Is the top out of place?
r[bottom] = r[top] # Then put it at the bottom...
break # ...and start searching from the bottom.
r[top] = pivot # Put the pivot in its place.

def quick_sort(self):
start=0
end=r-1
if start < end: # If there are two or more elements...
split = self.partition(r,start,end) # ... partition the sublist...
self.quick_sort(r, start, split-1) # ... and sort both halves.
self.quick_sort(r,split+1, end)
else:
return

def sort(self):
self.quick_sort(r, 0, self.howMany() - 1)

import random
import sys
def sortTest(size=100):
print "Checking to see if list is sorted:",
sorted = True
l = List()

for s in range(size):
l.push(random.randint(1,1000))
l.sort()
for s in range(size-1):
one = l.val(s)
two = l.val(s+1)
if one>two :
sorted = False
break
print sorted

if __name__ == "__main__":

r = random.randint(0,int(sys.argv[1]))

print "Running module tests..."
l = List()
print "Pushing values"
for d in range(r):
l.push(random.randint(0,r))
l.printMe()
for d in range(0,r,3):
l.printMe2()
print "Popping values"
for d in range(r/3):
l.pop()
l.printMe()
print "How Many:",
print l.howMany()
for d in range(0,r,3):
l.rem(d)
l.printMe2()
print 'Sorting list'

l.sort()

l.printMe()
print "Running sort test"
sortTest()``````