<reponame>RohanSahana/AlgorithmsAndDataStructure
# Selection Sort 
import sys 
a = [ 170, 40, 72, 90, 802, 24, 2, 66, 32]
string = "HACKTOBERFEST"
  
for i in range(len(a)): 
    min_idx = i 
    for j in range(i+1, len(a)): 
        if a[min_idx] > a[j]: 
            min_idx = j 
              
    a[i], a[min_idx] = a[min_idx], a[i] 

print ("Selection Sorted array: ") 
for i in range(len(a)): 
    print("%d \t" %a[i], sep=' ', end='', flush=True) 
    
# Bubble Sort 
def bubbleSort(a): 
    n = len(a) 
    for i in range(n-1): 
        for j in range(0, n-i-1): 
            if a[j] > a[j+1] : 
                a[j], a[j+1] = a[j+1], a[j] 
  

# Insertion Sort 
def insertionSort(a): 
    for i in range(1, len(a)): 
        key = a[i] 
        j = i-1
        while j >=0 and key < a[j] : 
            a[j+1] = a[j] 
            j -= 1
        a[j+1] = key 
    

# Heap Sort 
def heapify(a, n, i): 
    largest = i 
    l = 2 * i + 1    
    r = 2 * i + 2   
    if l < n and a[i] < a[l]: 
        largest = l 

    if r < n and a[largest] < a[r]: 
        largest = r 
  
    if largest != i: 
        a[i],a[largest] = a[largest],a[i]
        heapify(a, n, largest) 
  
def heapSort(a): 
    n = len(a) 
    for i in range(n // 2 - 1, -1, -1): 
        heapify(a, n, i) 
  
    for i in range(n-1, 0, -1): 
        a[i], a[0] = a[0], a[i]  
        heapify(a, i, 0) 

# Radix Sort 
def countingSort(a, exp1): 
    n = len(a) 
    output = [0] * (n) 
    count = [0] * (10) 
    for i in range(0, n): 
        index = (a[i]/exp1) 
        count[int((index)%10)] += 1

    for i in range(1,10): 
        count[i] += count[i-1] 
    i = n-1
    while i>=0: 
        index = (a[i]/exp1) 
        output[ count[ int((index)%10) ] - 1] = a[i] 
        count[int((index)%10)] -= 1
        i -= 1
    i = 0
    for i in range(0,len(a)): 
        a[i] = output[i] 

def radixSort(a):
    max1 = max(a)
    exp = 1
    while max1/exp > 0:
        countingSort(a,exp)
        exp *= 10

# Shell Sort 
def shellSort(a): 
    n = len(a) 
    gap = n/2
    while int(gap) > 0: 
        for i in range(int(gap),int(n)): 
            temp = a[i] 
            j = int(i) 
            while  int(j) >= int(gap) and a[int(j)-int(gap)] >temp: 
                a[j] = a[j-gap] 
                j -= gap 
            a[j] = temp 
        gap /= 2

# Counting sort 
def countSort(string): 
    output = [0 for i in range(256)] 
    count = [0 for i in range(256)] 
    ans = ["" for _ in string] 
    for i in string: 
        count[ord(i)] += 1
  
    for i in range(256): 
        count[i] += count[i-1] 
  
    for i in range(len(string)): 
        output[count[ord(string[i])]-1] = string[i] 
        count[ord(string[i])] -= 1
  
    for i in range(len(string)): 
        ans[i] = output[i] 
    return ans  
  
    
bubbleSort(a) 
print ("\nBubble Sorted array:") 
for i in range(len(a)): 
    print ("%d \t" %a[i], sep=' ', end='', flush=True)

insertionSort(a) 
print ("\nInsertion Sorted array:") 
for i in range(len(a)): 
    print ("%d\t" %a[i], sep=' ', end='', flush=True) 
    
heapSort(a) 
n = len(a) 
print ("\nHeap Sorted array:") 
for i in range(n): 
    print ("%d\t" %a[i], sep=' ', end='', flush=True)   
    
radixSort(a)
print ("\nRadix Sorted array:")
for i in range(len(a)):
    print("%d\t" %a[i], sep=' ', end='', flush=True)
    
shellSort(a) 
print ("\nShell Sorted array:") 
for i in range(n): 
    print("%d\t" %a[i], sep=' ', end='', flush=True)

b = countSort(string) 
print("\nSorted character array is %s" %(" ".join(b)))


# Selection Sort 
import sys 
a = [ 170, 40, 72, 90, 802, 24, 2, 66, 32]
string = "HACKTOBERFEST"
  
for i in range(len(a)): 
    min_idx = i 
    for j in range(i+1, len(a)): 
        if a[min_idx] > a[j]: 
            min_idx = j 
              
    a[i], a[min_idx] = a[min_idx], a[i] 

print ("Selection Sorted array: ") 
for i in range(len(a)): 
    print("%d \t" %a[i], sep=' ', end='', flush=True) 
    
# Bubble Sort 
def bubbleSort(a): 
    n = len(a) 
    for i in range(n-1): 
        for j in range(0, n-i-1): 
            if a[j] > a[j+1] : 
                a[j], a[j+1] = a[j+1], a[j] 
  

# Insertion Sort 
def insertionSort(a): 
    for i in range(1, len(a)): 
        key = a[i] 
        j = i-1
        while j >=0 and key < a[j] : 
            a[j+1] = a[j] 
            j -= 1
        a[j+1] = key 
    

# Heap Sort 
def heapify(a, n, i): 
    largest = i 
    l = 2 * i + 1    
    r = 2 * i + 2   
    if l < n and a[i] < a[l]: 
        largest = l 

    if r < n and a[largest] < a[r]: 
        largest = r 
  
    if largest != i: 
        a[i],a[largest] = a[largest],a[i]
        heapify(a, n, largest) 
  
def heapSort(a): 
    n = len(a) 
    for i in range(n // 2 - 1, -1, -1): 
        heapify(a, n, i) 
  
    for i in range(n-1, 0, -1): 
        a[i], a[0] = a[0], a[i]  
        heapify(a, i, 0) 

# Radix Sort 
def countingSort(a, exp1): 
    n = len(a) 
    output = [0] * (n) 
    count = [0] * (10) 
    for i in range(0, n): 
        index = (a[i]/exp1) 
        count[int((index)%10)] += 1

    for i in range(1,10): 
        count[i] += count[i-1] 
    i = n-1
    while i>=0: 
        index = (a[i]/exp1) 
        output[ count[ int((index)%10) ] - 1] = a[i] 
        count[int((index)%10)] -= 1
        i -= 1
    i = 0
    for i in range(0,len(a)): 
        a[i] = output[i] 

def radixSort(a):
    max1 = max(a)
    exp = 1
    while max1/exp > 0:
        countingSort(a,exp)
        exp *= 10

# Shell Sort 
def shellSort(a): 
    n = len(a) 
    gap = n/2
    while int(gap) > 0: 
        for i in range(int(gap),int(n)): 
            temp = a[i] 
            j = int(i) 
            while  int(j) >= int(gap) and a[int(j)-int(gap)] >temp: 
                a[j] = a[j-gap] 
                j -= gap 
            a[j] = temp 
        gap /= 2

# Counting sort 
def countSort(string): 
    output = [0 for i in range(256)] 
    count = [0 for i in range(256)] 
    ans = ["" for _ in string] 
    for i in string: 
        count[ord(i)] += 1
  
    for i in range(256): 
        count[i] += count[i-1] 
  
    for i in range(len(string)): 
        output[count[ord(string[i])]-1] = string[i] 
        count[ord(string[i])] -= 1
  
    for i in range(len(string)): 
        ans[i] = output[i] 
    return ans  
  
    
bubbleSort(a) 
print ("\nBubble Sorted array:") 
for i in range(len(a)): 
    print ("%d \t" %a[i], sep=' ', end='', flush=True)

insertionSort(a) 
print ("\nInsertion Sorted array:") 
for i in range(len(a)): 
    print ("%d\t" %a[i], sep=' ', end='', flush=True) 
    
heapSort(a) 
n = len(a) 
print ("\nHeap Sorted array:") 
for i in range(n): 
    print ("%d\t" %a[i], sep=' ', end='', flush=True)   
    
radixSort(a)
print ("\nRadix Sorted array:")
for i in range(len(a)):
    print("%d\t" %a[i], sep=' ', end='', flush=True)
    
shellSort(a) 
print ("\nShell Sorted array:") 
for i in range(n): 
    print("%d\t" %a[i], sep=' ', end='', flush=True)

b = countSort(string) 
print("\nSorted character array is %s" %(" ".join(b)))
# Selection Sort # Bubble Sort # Insertion Sort # Heap Sort # Radix Sort # Shell Sort # Counting sort