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:
    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 ()

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