Question

Write a program to sort a list of integers using Insertion sort, Mergesort and Quicksort. First take as input the size ‘n’ of the array, then read in the ‘n’ input integers that need to be sorted.

Answer 1

Insertion Sort

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

arr = [12, 11, 13, 5, 6]
insertionSort(arr)
for i in range(len(arr)):
    print ("% d" % arr[i])

Merge Sort

def mergeSort(arr):
    if len(arr) > 1:
  
         
        mid = len(arr)//2
  
       
        L = arr[:mid]
  
                R = arr[mid:]
  
       
        mergeSort(L)
 
        mergeSort(R)
  
        i = j = k = 0
  
        
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
  
        
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
  
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
  

  
  
def printList(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()
  
if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6, 7]
    print("Given array is", end="\n")
    printList(arr)
    mergeSort(arr)
    print("Sorted array is: ", end="\n")
    printList(arr)

Quick Sort

def partition(array, low, high):

  pivot = array[high]

  i = low - 1


  for j in range(low, high):
    if array[j] <= pivot:
      
      i = i + 1

      (array[i], array[j]) = (array[j], array[i])

  (array[i + 1], array[high]) = (array[high], array[i + 1])

  return i + 1

def quickSort(array, low, high):
  if low < high:


    pi = partition(array, low, high)

    quickSort(array, low, pi - 1)

    quickSort(array, pi + 1, high)




data = [8, 7, 2, 1, 0, 9, 6]
print("Unsorted Array")
print(data)


size = len(data)


quickSort(data, 0, size - 1)


print('Sorted Array in Ascending Order:')
print(data)