MAX = 20
arr = []
print "Enter the number of elements : ",
n = int(raw_input())
print "Enter %d elements: " %n
for i in range(n):
arr.append(int(raw_input()))
print "Unsorted list is : "
for i in range(n):
print arr[i],
for i in range(n):
xchanges=0
for j in range(n-1-i):
if (arr[j] > arr[j+1]):
arr[j], arr[j+1] = arr[j+1],arr[j]
xchanges+=1
if (xchanges == 0):
break
print "\nAfter pass %d elements are : " %(i+1)
for k in range(n):
print arr[k],
print "\nSorted list is : "
for i in range(n):
print arr[i],
def bubblesort(a, n):
for i in range(1,n):
for j in range(0,n-1):
if (a[j] > a[j+1]):
a[j], a[j+1] = a[j+1], a[j]
a = []
print "\nEnter the number of elements: ",
n = int(raw_input())
l = n;
print "\nEnter the elements: ",
while(l>0):
a.append(int(raw_input()))
l -= 1
bubblesort(a,n);
print "\nSorted array is: ",
l = 0
while(l < n):
print a[l],
l += 1
arr = []
print "\nEnter the number of elements: ",
n = int(raw_input())
for i in range(n):
print "Enter element %d: " %(i+1),
arr.append(int(raw_input()))
print "\nUnsorted list is: ",
for i in range(n):
print arr[i],
for i in range(0,n-1):
smallest = i
for k in range(i+1,n):
if (arr[smallest] > arr[k]):
smallest = k
if (i != smallest):
arr[i], arr[smallest] = arr[smallest], arr[i]
print "\nAfter pass %d elements are: " %(i+1),
for j in range(n):
print arr[j],
print "\nSorted list is: ",
for i in range(n):
print arr[i],
def selectionsort(a, n):
for i in range(n-1):
for j in range(i+1, n):
if (a[i]>a[j]):
a[i], a[j] = a[j],a[i]
a = []
print "\nEnter the number of elements: ",
n = int(raw_input())
l = n
print "\nEnter the elements: ",
while(l > 0):
a.append(int(raw_input()))
l -= 1
selectionsort(a, n)
print "\nSorted array: ",
l = 0
while(l < n):
print a[l],
l += 1
arr = []
print "\nEnter the number of elements: ",
n = int(raw_input())
for i in range(n):
print "Enter element %d: " %(i+1),
arr.append(int(raw_input()))
print "\nUnsorted list is: ",
for i in range(n):
print arr[i],
for j in range (1, n):
k=arr[j]
i = j-1
while (i>=0):
if k < arr[i]:
arr[i+1]=arr[i]
i-=1
arr[i+1]=k
print "\nPass %d, Element inserted in proper place: %d " %(j,k),
for i in range(n):
print arr[i],
print "\nSorted list is: ",
for i in range(n):
print arr[i],
arr = []
print "Enter the number of elements : ",
n = int(raw_input())
for i in range(n):
print "Enter element %d : " %(i+1),
arr.append(int(raw_input()))
print "Unsorted list is : ",
for i in range(n):
print arr[i],
print "\nEnter maximum increment (odd value) : ",
incr = int(raw_input())
while(incr>=1):
for j in range(incr,n):
k = arr[j]
i = j-incr
while (i>=0 and k < arr[i]):
arr[i+incr] = arr[i]
i = i-incr
arr[i+incr] = k
print "\nIncrement=%d " %incr
for i in range(n):
print arr[i],
incr = incr-2
print "\nSorted list is : ",
for i in range(n):
print arr[i],
def display(arr, low, up):
for i in range(low, up):
print arr[i],
def quick(arr, low, up):
left = low
right = up
piv = low
pivot_placed = False
print low, up
if (low>=up):
return
print "\nSublist: ",
display(arr,low,up)
while(pivot_placed == False):
while(arr[piv] <= arr[right] and piv != right):
right=right-1
if (piv==right):
pivot_placed = True
if (arr[piv] > arr[right]):
arr[piv], arr[right] = arr[right], arr[piv]
piv=right
while(arr[piv]>=arr[left] and left != piv):
left=left+1
if (piv==left):
pivot_placed = True
if (arr[piv] < arr[left]):
arr[piv], arr[left] = arr[left], arr[piv]
piv = left
print "\n-> Pivot Placed is %d -> " %arr[piv]
display(arr,low,up)
quick(arr,low,piv-1)
quick(arr,piv+1,up)
arr = []
print "\nEnter the number of elements : ",
n = int(raw_input())
for i in range(n):
print "Enter element %d: " %(i+1),
arr.append(int(raw_input()))
print "\nUnsorted list: ",
display(arr, 0, n)
quick(arr,0, n-1)
print "\nSorted List: ",
display(arr, 0, n)
arr1 = []
arr2 = []
arr3 = []
print "\nEnter the number of elements in list1: ",
max1 = int(raw_input())
print "\nTake the elements in sorted order \n",
for i in range(max1):
print "Enter element %d : " %(i+1),
arr1.append(int(raw_input()))
print "\nEnter the number of elements in list2: "
max2 = int(raw_input())
print "\nTake the elements in sorted order :\n"
for i in range(max2):
print "Enter element %d: "%(i+1),
arr2.append(int(raw_input()))
i = 0
j = 0
while((i < max1) and (j < max2)):
if (arr1[i] < arr2[j]):
arr3.append(arr1[i])
i += 1
else:
arr3.append(arr2[j])
j += 1
while(i < max1):
arr3.append(arr1[i])
i += 1
while(j < max2):
arr3.append(arr2[j])
j += 1
print "\nList 1: ",
for i in range(max1):
print arr1[i],
print "\nList 2: ",
for i in range(max2):
print arr2[i],
print "\nMerged list: "
for i in range(max1+max2):
print arr3[i],
arr = []
temp = []
print "\nEnter the number of elements: ",
n = int(raw_input())
for i in range(n):
print "Enter element %d: " %(i+1),
arr.append(int(raw_input()))
print "\nUnsorted list is: ",
for i in range(n):
print arr[i],
size = 1
while size < n:
l1 = 0
k = 0
while(l1+size<n):
h1 = l1 + (size - 1)
l2 = h1 + 1
h2 = l2 + (size - 1)
if (h2>=n):
h2 = n-1
i=l1
j=l2
while(i<=h1 and j<=h2 ):
if (arr[i]<=arr[j]):
temp.append(arr[i])
i += 1
else:
temp.append(arr[j])
j += 1
while(i<=h1):
temp.append(arr[i])
i += 1
while(j<=h2):
temp.append(arr[j])
j += 1
l1 = h2+1
for i in range (l1, n):
temp.append(arr[i])
for i in range(0):
arr[i]=temp[i]
print "\nSize=%d \nElements are: " %size
for i in range(n):
print arr[i],
size = size * 2
arr = temp
print "\nSorted list is:",
for i in range(n):
print arr[i],
from numpy import zeros
array = []
def merge(low, mid, high):
global array
temp = zeros(len(array))
i = low;
j = mid +1 ;
k = low ;
print array
while((i<=mid) and (j<=high)):
if (array[i]<=array[j]):
temp[k] = array[i]
k += 1
i += 1
else:
temp[k] = array[j]
k += 1
j += 1
while(i<=mid):
temp[k] = array[i]
k += 1
i += 1
while(j<=high):
temp[k] = array[j]
k += 1
j += 1
for i in range(low,high+1):
array[i] = temp[i]
def merge_sort(low, high):
if (low != high):
mid = (low+high)/2;
merge_sort(low , mid)
merge_sort(mid+1, high)
merge(low, mid, high)
print "\nEnter the number of elements: "
n = int(raw_input())
for i in range(n):
print "Enter element %d: " %(i+1),
array.append(int(raw_input()))
print "\nUnsorted list is: ",
for i in range(n):
print array[i],
merge_sort(0, n-1)
print "\nSorted list is :",
for i in range(n):
print array[i],
from numpy import zeros
class node:
def __init__(self, info=None, link=None):
self.info = info
self.link = link
start = None
def display():
global start
p = start
while(p != None):
print p.info,
p = p.link
print ""
def large_dig(p):
large = 0
ndig = 0
while (p!=None):
if (p.info > large):
large = p.info
p = p.link
print "\nLargest Element is %d" %large
while (large!=0):
ndig += 1
large = large/10
print "\nNumber of digits in it are %d " %ndig
return ndig
def digit(number, k):
digit = 0
for i in range (1, k+1):
digit = number % 10 ;
number = number /10 ;
return digit
def radix_sort():
global start
rear = []
front = []
least_sig=1;
most_sig=large_dig(start);
for k in range(least_sig, most_sig+1):
print "\nPASS %d : Examining %dth digit from right" %(k,k)
for i in range(0,10):
rear.append(None)
front.append(None)
maxdig=0
mindig=9
p = start
while(p!=None):
dig = digit(p.info, k)
if (dig>maxdig):
maxdig=dig
if (dig<mindig):
mindig=dig
if (front[dig] == None):
front[dig] = p
else:
rear[dig].link = p
rear[dig] = p
p = p.link
print "\nmindig=%d maxdig=%d\n" %(mindig, maxdig)
start = front[mindig]
for i in range(mindig,maxdig):
if (rear[i+1]!=None):
rear[i].link = front[i+1]
else:
rear[i+1]=rear[i];
rear[maxdig].link = None
print "\nNew list : ",
display()
q = node()
print "Enter the number of elements in the list: ",
n = int(raw_input())
for i in range(n):
print "Enter element %d: " %(i+1),
item = int(raw_input())
tmp = node()
tmp.info = item
tmp.link = None
if (start == None):
start = tmp
print start.info
else:
q = start
while(q.link != None):
q = q.link
print q.info
q.link = tmp
print "\nUnsorted list is: ",
display()
radix_sort()
print "\nSorted list is: "
display ()
arr = []
n = None
def display():
global n
for i in range(n):
print arr[i],
def insert(num, loc):
while(loc>0):
par = (loc-1)/2;
if (num<=arr[par]):
arr[loc] = num
return
arr[loc] = arr[par]
loc=par
arr[0] = num
def create_heap():
global n
for i in range(n):
arr.append(i)
def del_root(last):
i=0
arr[i], arr[last] = arr[last], arr[i]
left = 2*i+1
right = 2*i+2
while(right<last):
if (arr[i]>=arr[left] and arr[i]>=arr[right]):
return
if (arr[right]<=arr[left]):
arr[i], arr[left] = arr[left], arr[i]
else:
arr[i], arr[right] = arr[right], arr[i]
i=right;
left=2*i+1;
right=2*i+2;
if (left==last-1 and arr[i]<arr[left]):
arr[i], arr[left] = arr[left], arr[i]
def heap_sort():
global n
last = n-1
while(last>0):
del_root(last)
last -= 1
print "Enter number of elements: ",
n = int(raw_input())
for i in range(n):
print "Enter element %d: " %(i+1),
arr.append(int(raw_input()))
print "\nEntered list is: ",
display()
create_heap()
print "\nHeap is: ",
display()
heap_sort()
print "\nSorted list is: ",
display()