Showing posts with label sort. Show all posts
Showing posts with label sort. Show all posts

Interpolation Search

def interpolationSearch(arr, lo, hi, x):

if (lo <= hi and x >= arr[lo] and x <= arr[hi]):

pos = lo + ((hi - lo) // (arr[hi] - arr[lo]) *

(x - arr[lo]))

if arr[pos] == x:

return pos

if arr[pos] < x:

return interpolationSearch(arr, pos + 1,

hi, x)

if arr[pos] > x:

return interpolationSearch(arr, lo,

pos - 1, x)

return -1

arr = [10, 12, 13, 16, 18, 19, 20,

21, 22, 23, 24, 33, 35, 42, 47]

n = len(arr)

x = 18

index = interpolationSearch(arr, 0, n - 1, x)

if index != -1:

print("Element found at index", index)

else:

print("Element not found")


Stooge Sort

def stoogesort(arr, l, h):

if l >= h:

return

if arr[l]>arr[h]:

t = arr[l]

arr[l] = arr[h]

arr[h] = t

if h-l + 1 > 2:

t = (int)((h-l + 1)/3)

stoogesort(arr, l, (h-t))

stoogesort(arr, l + t, (h))

stoogesort(arr, l, (h-t))

arr = [2, 4, 5, 3, 1]

n = len(arr)

stoogesort(arr, 0, n-1)

for i in range(0, n):

print(arr[i], end = ' ')


Program for Brick Sort

def oddEvenSort(arr, n):

    isSorted = 0

    while isSorted == 0:

        isSorted = 1

        temp = 0

        for i in range(1, n-1, 2):

            if arr[i] > arr[i+1]:

                arr[i], arr[i+1] = arr[i+1], arr[i]

                isSorted = 0

                  

        for i in range(0, n-1, 2):

            if arr[i] > arr[i+1]:

                arr[i], arr[i+1] = arr[i+1], arr[i]

                isSorted = 0

    return

arr = [34, 2, 10, -9]

n = len(arr)

oddEvenSort(arr, n);

for i in range(0, n):

    print(arr[i], end =" ")

      


Program for Recursive Insertion Sort

def insertionSortRecursive(arr, n):

if n <= 1:

return

insertionSortRecursive(arr, n - 1)

last = arr[n - 1]

j = n - 2

while (j >= 0 and arr[j] > last):

arr[j + 1] = arr[j]

j = j - 1

arr[j + 1] = last

if __name__ == '__main__':

A = [-7, 11, 6, 0, -3, 5, 10, 2]

n = len(A)

insertionSortRecursive(A, n)

print(A)


Pigeonhole Sort

def pigeonhole_sort(a):

my_min = min(a)

my_max = max(a)

size = my_max - my_min + 1

holes = [0] * size

for x in a:

assert type(x) is int, "integers only please"

holes[x - my_min] += 1

i = 0

for count in range(size):

while holes[count] > 0:

holes[count] -= 1

a[i] = count + my_min

i += 1

a = [8, 3, 2, 7, 4, 6, 8]

print("Sorted order is : ", end =" ")

pigeonhole_sort(a)

for i in range(0, len(a)):

print(a[i], end =" ")


Program for BogoSort or Permutation Sort

import random

def bogoSort(a):

n = len(a)

while (is_sorted(a)== False):

shuffle(a)

def is_sorted(a):

n = len(a)

for i in range(0, n-1):

if (a[i] > a[i+1] ):

return False

return True

def shuffle(a):

n = len(a)

for i in range (0,n):

r = random.randint(0,n-1)

a[i], a[r] = a[r], a[i]

a = [3, 2, 4, 1, 0, 5]

bogoSort(a)

print("Sorted array :")

for i in range(len(a)):

print ("%d" %a[i]),


Program for Recursive Topological Sorting

from collections import defaultdict

class Graph:

def __init__(self,vertices):

self.graph = defaultdict(list) 

self.V = vertices 

def addEdge(self,u,v):

self.graph[u].append(v)

def topologicalSortUtil(self,v,visited,stack):

visited[v] = True

for i in self.graph[v]:

if visited[i] == False:

self.topologicalSortUtil(i,visited,stack)

stack.insert(0,v)

def topologicalSort(self):

visited = [False]*self.V

stack =[]

for i in range(self.V):

if visited[i] == False:

self.topologicalSortUtil(i,visited,stack)

print (stack)

g= Graph(6)

g.addEdge(5, 2);

g.addEdge(5, 0);

g.addEdge(4, 0);

g.addEdge(4, 1);

g.addEdge(2, 3);

g.addEdge(3, 1);

print ("Following is a Topological Sort of the given graph")

g.topologicalSort()


Heap Sort in Python

from heapq import heappop, heappush    

def heapsort(list1):  

     heap = []  

     for ele in list1:  

         heappush(heap, ele)    

     sort = []     

     while heap:  

         sort.append(heappop(heap))     

     return sort     

list1 = [27, 21, 55, 15, 60, 4, 11, 17, 2, 87]  

print(heapsort(list1))  

Bubble Sort in Python

def bubble_sort(list1):  

    for i in range(0,len(list1)-1):  

        for j in range(len(list1)-1):  

            if(list1[j]>list1[j+1]):  

                temp = list1[j]  

                list1[j] = list1[j+1]  

                list1[j+1] = temp  

    return list1  

list1 = [5, 3, 8, 6, 7, 2]  

print("The unsorted list is: ", list1)  

print("The sorted list is: ", bubble_sort(list1))  


Program for Cocktail Sort

def cocktailSort(a):

n = len(a)

swapped = True

start = 0

end = n-1

while (swapped==True):

swapped = False

for i in range (start, end):

if (a[i] > a[i+1]) :

a[i], a[i+1]= a[i+1], a[i]

swapped=True

if (swapped==False):

break

swapped = False

end = end-1

for i in range(end-1, start-1,-1):

if (a[i] > a[i+1]):

a[i], a[i+1] = a[i+1], a[i]

swapped = True

start = start+1

a = [5, 1, 4, 2, 8, 0, 2 ,6,7]

cocktailSort(a)

print("Sorted array is:")

for i in range(len(a)):

print ("%d" %a[i]),


Program for Gnome Sort

def gnomeSort( arr, n):

index = 0

while index < n:

if index == 0:

index = index + 1

if arr[index] >= arr[index - 1]:

index = index + 1

else:

arr[index], arr[index-1] = arr[index-1], arr[index]

index = index - 1

return arr

arr = [ 34, 2, 10, -9]

n = len(arr)

arr = gnomeSort(arr, n)

print ("Sorted seqquence after applying Gnome Sort :")

for i in arr:

print (i)