# Chapter 6: Sorting Techniques¶

## Example 1, page no. 155¶

In [2]:
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],

Enter the number of elements : 3
Enter 3 elements:
15
10
5
Unsorted list is :
15 10 5
After pass 1 elements are :
10 5 15
After pass 2 elements are :
5 10 15
Sorted list is :
5 10 15


## Example 2, page no. 157¶

In [4]:
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


Enter the number of elements: 3

Enter the elements: 15
10
5

Sorted array is:  5 10 15


## Example 3, page no. 160¶

In [5]:
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],

Enter the number of elements: 3
Enter element 1: 15
Enter element 2: 10
Enter element 3: 5

Unsorted list is:  15 10 5
After pass 1 elements are:  5 15 10
After pass 2 elements are:  5 10 15
Sorted list is:  5 10 15


## Example 4, page no. 161¶

In [ ]:
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

Enter the number of elements:

## Example 5, page no. 166¶

In [7]:
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],

Enter the number of elements: 3
Enter element 1: 15
Enter element 2: 10
Enter element 3: 5

Unsorted list is:  15 10 5
Pass 1, Element inserted in proper place: 10  10 15 5
Pass 2, Element inserted in proper place: 5  5 10 15
Sorted list is:  5 10 15


## Example 6, page no. 169¶

In [8]:
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],

Enter the number of elements : 3
Enter element 1 : 15
Enter element 2 : 10
Enter element 3 : 5
Unsorted list is :  15 10 5
Enter maximum increment (odd value) : 3

Increment=3
15 10 5
Increment=1
5 10 15
Sorted list is :  5 10 15


## Example 7, page no. 173¶

In [9]:
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)

Enter the number of elements : 3
Enter element 1: 15
Enter element 2: 10
Enter element 3: 5

Unsorted list:  15 10 5 0 2

Sublist:  15 10
-> Pivot Placed is 15 ->
5 10 0 1

Sublist:  5
-> Pivot Placed is 5 ->
5 0 -1
1 1
3 2

Sorted List:  5 10 15


## Example 8, page no. 177¶

In [11]:
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],


Enter the number of elements in list1: 2

Take the elements in sorted order
Enter element 1 : 10
Enter element 2 : 15

Enter the number of elements in list2:
5

Take the elements in sorted order :

Enter element 1: 1
Enter element 2: 2
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5

List 1:  10 15
List 2:  1 2 3 4 5
Merged list:
1 2 3 4 5 10 15


## Example 9, page no. 179¶

In [1]:
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],

Enter the number of elements: 3
Enter element 1: 15
Enter element 2: 10
Enter element 3: 5

Unsorted list is:  15 10 5
Size=1
Elements are:
15 10 5
Size=2
Elements are:
15 10 5
Sorted list is: 10 15 5


## Example 10, page no. 181¶

In [2]:
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],

Enter the number of elements:
3
Enter element 1: 15
Enter element 2: 10
Enter element 3: 5

Unsorted list is:  15 10 5 [15, 10, 5]
[10.0, 15.0, 5]

Sorted list is : 5.0 10.0 15.0


## Example 11, page no. 184¶

In [2]:
from numpy import zeros
class node:
self.info = info

start = None

def display():
global start
p = start
while(p != None):
print p.info,
print ""

def large_dig(p):
large = 0
ndig = 0
while (p!=None):
if (p.info > large):
large = p.info
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

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] = p
print "\nmindig=%d maxdig=%d\n" %(mindig, maxdig)
start = front[mindig]
for i in range(mindig,maxdig):
if (rear[i+1]!=None):
else:
rear[i+1]=rear[i];
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
if (start == None):
start = tmp
print start.info
else:
q = start
print q.info
print "\nUnsorted list is: ",
display()
print "\nSorted list is: "
display ()

Enter the number of elements in the list: 3
Enter element 1: 15
15
Enter element 2: 10
Enter element 3: 12
10

Unsorted list is:  15 10 12

Largest Element is 15

Number of digits in it are 2

PASS 1 : Examining 1th digit from right

mindig=0 maxdig=5

New list :  10 12 15

PASS 2 : Examining 2th digit from right

mindig=1 maxdig=1

New list :  10 12 15

Sorted list is:
10 12 15


## Example 12, Page no. 197¶

In [ ]:
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()

Enter number of elements:
In [ ]: