class numbers:
data=list();
def __init__(self):
for i in range(int(input("How many numbers do u wish to sort"))):
print "Enter element number",i+1;
self.data.append(int(input()))
print "The entered numbers are"
self.display()
def display(self):
print self.data
def bubble(self):
nos=self.data.__len__()
for i in range(nos):
print "in the loop the value of i is",i
for j in range(nos-1-i):
print "val j",j
if self.data[j]>self.data[j+1]:
self.data[j],self.data[j+1]=self.data[j+1],self.data[j
print "updated value of i is",i
print "Displaying the sorted list"
self.display()
def reset(self):
while(self.data.__len__()!=0):
self.data.pop()
for i in range(int(input("How many numbers do u wish to sort"))):
print "Enter element number",i+1;
self.data.append(int(input()))
print "The entered numbers are"
self.display()
def qcaller(self):
self.quicksort(0, self.data.__len__()-1)
print "The list is sorted"
self.display()
def quicksort(self,low,high):
if high>low:
mid=self.partition(low, high)
self.quicksort(low, mid)
self.quicksort(mid+1, high)
def partition(self,low,high):
j=high
i=low+1
pivot=self.data[low]
done=False
while not done:
while i<=j and self.data[i]<=pivot:
i+=1
while i<=j and self.data[j]>=pivot:
j-=1
if i>j:
done=True
else:
self.data[i],self.data[j]=self.data[j],self.data[i]
self.data[low]=self.data[j]
self.data[j]=pivot
return j
def icaller(self):
self.insertion(1)
print "Tne numbers have been sorted"
a.display()
def insertion(self,span):
j=span
while j<self.data.__len__():
i=j
temp=self.data[i]
while i-span >=0 and temp<self.data[i-span]:
self.data[i]=self.data[i-span]
i=i-span
self.data[i]=temp
j+=span
def shellsort(self):
span=self.data.__len__()/2
while span>=1:
self.insertion(span)
span/=2
print "The numbers have been sorted"
a.display()
def mcaller(self):
self.mergesort(0,self.data.__len__()-1)
print "The numbers have been sorted"
self.display()
def mergesort(self,low,high):
if high>low:
mid=(high+low)/2
self.mergesort(low,mid)
self.mergesort(mid+1,high)
self.merge(low,mid,high)
def merge(self,low,mid,high):
temp=list()
i=low
j=mid+1
while i<=mid and j<=high:
if self.data[i]<=self.data[j]:
temp.append(self.data[i])
i+=1
else:
temp.append(self.data[j])
j+=1
if i>mid:
while j<=high:
temp.append(self.data[j])
j+=1
else:
while i<=mid:
temp.append(self.data[i])
i+=1
for k in range(high,low-1,-1):
self.data[k]=temp.pop()
def heapsort(self):
self.data.append(self.data[0])
self.data[0]=self.data.__len__()-1
self.heapify(self.data[0])
for i in range(self.data[0]-1):
self.data[1],self.data[self.data[0]]=self.data[self.data[0]],self.data[1]
self.data[0]-=1
self.downadjust(1)
self.data.__delitem__(0)
print "Displaying the sorted numbers"
self.display()
def downadjust(self,i):
while True:
j=2*i
if j>self.data[0]:
break
if j+1<=self.data[0] and self.data[j+1]>self.data[j]:
j+=1
if self.data[j]<=self.data[i]:
break
else:
self.data[j],self.data[i]=self.data[i],self.data[j]
i=j
def heapify(self,totnos):
for k in range(totnos/2,0,-1):
self.downadjust(k)
def pset(self):
maxi=abs(self.data[0])
for i in range(1,self.data.__len__()):
maxi=max(maxi,abs(self.data[i]))
count=0
while maxi>0:
maxi/=10
count+=1
return count
def digitset(self,no,pval):
return(no/10**(pval)%10)
def radixsort(self):
tpass=self.pset()
temp=list(self.data)
for pval in range(tpass):
buckets=[[]for z in range(10)]
for i in range(temp.__len__()):
buckets[self.digitset(temp[i], pval)].append(temp[i])
temp=[]
for a in range(10):
temp.extend(buckets[a])
self.data=list(temp)
self.sc()
print "The numbers are sorted"
self.display()
def sc(self):
buckets=[[],[]]
for i in range(self.data.__len__()):
if self.data[i]>=0:
buckets[1].append(self.data[i])
else:
buckets[0].append(self.data[i])
self.data=[]
self.data.extend(buckets[0])
self.data.extend(buckets[1])
print "This is a program by Abhishek Munagekar"
print "This is program is for demonstrating the various sorting methods"
a=numbers()
while True:
print "Enter ur choice"
print "MENU\n1.Exit \t\t2.Re-enter values \t3.Display \t4.Bubblesort \n5.Quicksort \t6.Insertionsort \t7.Shellsort \t8.Mergesort"
print "9.Heapsort \t10.Radixsort"
ch=int(input())
if ch==1:
print "Program Terminated"
break
elif ch==2:
a.reset()
elif ch==3:
a.display()
elif ch==4:
a.bubble()
elif ch==5:
a.qcaller()
elif ch==6:
a.icaller()
elif ch==7:
a.shellsort()
elif ch==8:
a.mcaller()
elif ch ==9:
a.heapsort()
elif ch ==10:
a.radixsort()
else:
print "Invalid choice entered. Enter your choice again"
No comments:
Post a Comment