ads (1).py

# -*- coding: utf-8 -*-
"""ADS.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1Di4l_arMLT8_lqqsqgHw6YVB3BhKGEdb

Selection sort for list of integers with size 100.
"""

import time
import random
start = time.time()
def selectionSort(array):
  n = len(array)
  for i in range(n):
    # Initially, assume the first element of the unsorted part as the minimum.
    minimum = i

    for j in range(i+1, n):
      if (array[j] < array[minimum]):
        # Update position of minimum element if a smaller element is found.
        minimum = j

    # Swap the minimum element with the first element of the unsorted part.     
    temp = array[i]
    array[i] = array[minimum]
    array[minimum] = temp
    
  return array
# Driver code
#array = [13, 4, 9, 5, 3, 16, 12,3,4,4]
array = random.sample(range(10,1000), 100)
# array = list(range(1,100))
print(array)
print(selectionSort(array))
end = time.time()
print ("Execution time for selection sort:", end - start)



"""Insertion sort for list of integers with size 100

"""

import time
import random
start = time.time()
def insertion_sort(arr):
    for i in range(1, len(arr)):
        # Set key:
        key = arr[i]

        j = i - 1
        while j >= 0 and arr[j] > key:
            # Swap:
            arr[j + 1] = arr[j]
            arr[j] = key
            
            # Decrement 'j':
            j -= 1

    return arr
# Driver code
#array = [13, 4, 9, 5, 3, 16, 12,3,4,4]
# array = list(range(1,100))
array = random.sample(range(10,1000), 100)
print(insertion_sort(array))
end = time.time()
print ("Time elapsed of insertion sort:", end - start)

"""Bubble sort for list of integers with size 100. """

import time
import random
start = time.time()
def bubbleSort(arr):
	n = len(arr)

	# Traverse through all array elements
	for i in range(n-1):
	# range(n) also work but outer loop will repeat one time more than needed.

		# Last i elements are already in place
		for j in range(0, n-i-1):

			# traverse the array from 0 to n-i-1
			# Swap if the element found is greater
			# than the next element
			if arr[j] > arr[j + 1] :
				arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Driver code
#array = [13, 4, 9, 5, 3, 16, 12,3,4,4]
# array = list(range(1,100))
array = random.sample(range(10,1000), 100)
#print(bubbleSort(array))
end = time.time()
print ("Execution time for selection sort:", end - start)

#Merge sort for list of integers with size 100
import time
start = time.time()
def mergeSort(array):
    
    if len(array)>1:
      # Finding the mid of the array
        mid = len(array)//2
      # Dividing the array elements
        lefthalf = array[:mid]
        righthalf =array[mid:]
    # Recursive call on each half
    # Sorting the first half
        mergeSort(lefthalf)
    # Sorting the second half    
        mergeSort(righthalf)

        i=j=k=0       
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                array[k]=lefthalf[i]
                i=i+1
            else:
                array[k]=righthalf[j]
                j=j+1
            k=k+1

        # Checking if any element was left
        while i < len(lefthalf):
            array[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            array[k]=righthalf[j]
            j=j+1
            k=k+1
    
# Driver code
# array = [13, 4, 9, 5, 3, 16, 12,3,4,4]
array = list(range(1,100))
mergeSort(array)
end = time.time()
print(array)
print ("Execution time for Merge sort:", end - start)

# Quick sorting for list integers of size 100
import time
start = time.time()
def partition(start, end, array):
      
    # Initializing pivot's index to start
    pivot_index = start 
    pivot = array[pivot_index]
      
    # This loop runs till start pointer crosses end pointer, and when it does we swap the pivot with element on end pointer
    while start < end:
          
        # Increment the start pointer till it finds an  element greater than  pivot 
        while start < len(array) and array[start] <= pivot:
            start += 1
              
        # Decrement the end pointer till it finds an element less than pivot
        while array[end] > pivot:
            end -= 1
          
        # If start and end have not crossed each other,swap the numbers on start and end
        if(start < end):
            array[start], array[end] = array[end], array[start]
      
    # Swap pivot element with element on end pointer. This puts pivot on its correct sorted place.
    array[end], array[pivot_index] = array[pivot_index], array[end]
     
    # Returning end pointer to divide the array into 2
    return end
      
# The main function that implements QuickSort 
def quick_sort(start, end, array):
      
    if (start < end):
          
        # p is partitioning index, array[p] is at right place
        p = partition(start, end, array)
          
        # Sort elements before partition and after partition
        quick_sort(start, p - 1, array)
        quick_sort(p + 1, end, array)
          
# Driver code
# array = [ 13, 4, 9, 5, 3, 16, 12,3,4,4]
array = list(range(1,100))
quick_sort(0, len(array) - 1, array)
  
print(f'Sorted array: {array}')
end = time.time()
print ("Execution time for Merge sort:", end - start)

"""Selection sort for list of strings with size 8"""

import time
start = time.time()
def selectionSort(array):
  n = len(array)
  for i in range(n):
    # Initially, assume the first element of the unsorted part as the minimum.
    minimum = i

    for j in range(i+1, n):
      if (array[j] < array[minimum]):
        # Update position of minimum element if a smaller element is found.
        minimum = j

    # Swap the minimum element with the first element of the unsorted part.     
    temp = array[i]
    array[i] = array[minimum]
    array[minimum] = temp
    
  return array
# Driver code
array = ["cherry","jackfruit","apple","mango","lemon","iceapple","banana"]
print(selectionSort(array))
end = time.time()
print ("Execution time for selection sort:", end - start)

"""Insertion sort for list of strings with size 8"""

import time
start = time.time()
def insertion_sort(arr):
    for i in range(1, len(arr)):
        # Set key:
        key = arr[i]

        j = i - 1
        while j >= 0 and arr[j] > key:
            # Swap:
            arr[j + 1] = arr[j]
            arr[j] = key
            
            # Decrement 'j':
            j -= 1

    return arr
# Driver code
array = ["cherry","jackfruit","apple","mango","lemon","iceapple","banana"]
print(insertion_sort(array))
end = time.time()
print ("Time elapsed of insertion sort:", end - start)

"""Bubble Sort for list of strings with size 8"""

import time
start = time.time()
def bubbleSort(arr):
	n = len(arr)

	# Traverse through all array elements
	for i in range(n-1):
	# range(n) also work but outer loop will repeat one time more than needed.

		# Last i elements are already in place
		for j in range(0, n-i-1):

			# traverse the array from 0 to n-i-1
			# Swap if the element found is greater
			# than the next element
			if arr[j] > arr[j + 1] :
				arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Driver code
array = ["cherry","jackfruit","apple","mango","lemon","iceapple","banana"]
print(bubbleSort(array))
end = time.time()
print ("Execution time for selection sort:", end - start)

import time
start = time.time()
def selectionSort(array):
  n = len(array)
  for i in range(n):
    # Initially, assume the first element of the unsorted part as the minimum.
    minimum = i

    for j in range(i+1, n):
      if (array[j] < array[minimum]):
        # Update position of minimum element if a smaller element is found.
        minimum = j

    # Swap the minimum element with the first element of the unsorted part.     
    temp = array[i]
    array[i] = array[minimum]
    array[minimum] = temp
    
  return array
# Driver code
array = [1.3,  0.1,  0.2,  0.3,  0.4,  0.5,  0.6,  0.11,  0.13,  0.9, 0.45, 0.33, 0.456, 0.234, 0.12]
print(selectionSort(array))
end = time.time()
print ("Execution time for selection sort:", end - start)

import time
start = time.time()
def insertion_sort(arr):
    for i in range(1, len(arr)):
        # Set key:
        key = arr[i]

        j = i - 1
        while j >= 0 and arr[j] > key:
            # Swap:
            arr[j + 1] = arr[j]
            arr[j] = key
            
            # Decrement 'j':
            j -= 1

    return arr
# Driver code
array = [1.3,  0.1,  0.2,  0.3,  0.4,  0.5,  0.6,  0.11,  0.13,  0.9, 0.45, 0.33, 0.456, 0.234, 0.12]
print(insertion_sort(array))
end = time.time()
print ("Time elapsed of insertion sort:", end - start)

import time
start = time.time()
def bubbleSort(arr):
	n = len(arr)

	# Traverse through all array elements
	for i in range(n-1):
	# range(n) also work but outer loop will repeat one time more than needed.

		# Last i elements are already in place
		for j in range(0, n-i-1):

			# traverse the array from 0 to n-i-1
			# Swap if the element found is greater
			# than the next element
			if arr[j] > arr[j + 1] :
				arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Driver code
array = [1.3,  0.1,  0.2,  0.3,  0.4,  0.5,  0.6,  0.11,  0.13,  0.9, 0.45, 0.33, 0.456, 0.234, 0.12]
print(bubbleSort(array))
end = time.time()
print ("Execution time for selection sort:", end - start)

import time
start = time.time()
def selectionSort(array):
  n = len(array)
  for i in range(n):
    # Initially, assume the first element of the unsorted part as the minimum.
    minimum = i

    for j in range(i+1, n):
      if (array[j] < array[minimum]):
        # Update position of minimum element if a smaller element is found.
        minimum = j

    # Swap the minimum element with the first element of the unsorted part.     
    temp = array[i]
    array[i] = array[minimum]
    array[minimum] = temp
    
  return array
# Driver code
array = [('Saranya',84), ('Surya',92) , ('Joy',88) , ('Sree',86), ('Ritha',89)]
print(selectionSort(array))
end = time.time()
print ("Execution time for selection sort:", end - start)

import time
start = time.time()
def insertion_sort(arr):
    for i in range(1, len(arr)):
        # Set key:
        key = arr[i]

        j = i - 1
        while j >= 0 and arr[j] > key:
            # Swap:
            arr[j + 1] = arr[j]
            arr[j] = key
            
            # Decrement 'j':
            j -= 1

    return arr
# Driver code
array = [('Saranya',84), ('Surya',92) , ('Joy',88) , ('Sree',86), ('Ritha',89)]
print(insertion_sort(array))
end = time.time()
print ("Time elapsed of insertion sort:", end - start)

import time
start = time.time()
def bubbleSort(arr):
	n = len(arr)

	# Traverse through all array elements
	for i in range(n-1):
	# range(n) also work but outer loop will repeat one time more than needed.

		# Last i elements are already in place
		for j in range(0, n-i-1):

			# traverse the array from 0 to n-i-1
			# Swap if the element found is greater
			# than the next element
			if arr[j] > arr[j + 1] :
				arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Driver code
array = [('Saranya',84), ('Surya',92) , ('Joy',88) , ('Sree',86), ('Ritha',89)]
bubblesort(array)

for k in range(len(array)):
    print(array[k],",")

end = time.time()
print ("Execution time for selection sort:", end - start)

#Merge sort for list of strings with size 8
import time
start = time.time()
def mergeSort(array):
    
    if len(array)>1:
      # Finding the mid of the array
        mid = len(array)//2
      # Dividing the array elements
        lefthalf = array[:mid]
        righthalf =array[mid:]
    # Recursive call on each half
    # Sorting the first half
        mergeSort(lefthalf)
    # Sorting the second half    
        mergeSort(righthalf)

        i=j=k=0       
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                array[k]=lefthalf[i]
                i=i+1
            else:
                array[k]=righthalf[j]
                j=j+1
            k=k+1

        # Checking if any element was left
        while i < len(lefthalf):
            array[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            array[k]=righthalf[j]
            j=j+1
            k=k+1
    
# Driver code
array = ["cherry","jackfruit","apple","mango","lemon","iceapple","banana","orange"]
mergeSort(array)
end = time.time()
print(array)
print ("Execution time for Merge sort:", end - start)

import time
start = time.time()
def mergeSort(array):
    
    if len(array)>1:
      # Finding the mid of the array
        mid = len(array)//2
      # Dividing the array elements
        lefthalf = array[:mid]
        righthalf =array[mid:]
    # Recursive call on each half
    # Sorting the first half
        mergeSort(lefthalf)
    # Sorting the second half    
        mergeSort(righthalf)

        i=j=k=0       
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                array[k]=lefthalf[i]
                i=i+1
            else:
                array[k]=righthalf[j]
                j=j+1
            k=k+1

        # Checking if any element was left
        while i < len(lefthalf):
            array[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            array[k]=righthalf[j]
            j=j+1
            k=k+1
    
# Driver code
array = [1.3,  0.1,  0.2,  0.3,  0.4,  0.5,  0.6,  0.11,  0.13,  0.9, 0.45, 0.33, 0.456, 0.234, 0.12]
mergeSort(array)
end = time.time()
print(array)
print ("Execution time for Merge sort:", end - start)

import time
start = time.time()
def mergeSort(array):
    
    if len(array)>1:
      # Finding the mid of the array
        mid = len(array)//2
      # Dividing the array elements
        lefthalf = array[:mid]
        righthalf =array[mid:]
    # Recursive call on each half
    # Sorting the first half
        mergeSort(lefthalf)
    # Sorting the second half    
        mergeSort(righthalf)

        i=j=k=0       
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                array[k]=lefthalf[i]
                i=i+1
            else:
                array[k]=righthalf[j]
                j=j+1
            k=k+1

        # Checking if any element was left
        while i < len(lefthalf):
            array[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            array[k]=righthalf[j]
            j=j+1
            k=k+1
    
# Driver code
array = [[('Saranya',84), ('Surya',92) , ('Joy',88) , ('Sree',86), ('Ritha',89)]]
mergeSort(array)
end = time.time()
print(array)
print ("Execution time for Merge sort:", end - start)



# Quick sorting for list of strings
import time
start = time.time()
def partition(start, end, array):
      
    # Initializing pivot's index to start
    pivot_index = start 
    pivot = array[pivot_index]
      
    # This loop runs till start pointer crosses end pointer, and when it does we swap the pivot with element on end pointer
    while start < end:
          
        # Increment the start pointer till it finds an  element greater than  pivot 
        while start < len(array) and array[start] <= pivot:
            start += 1
              
        # Decrement the end pointer till it finds an element less than pivot
        while array[end] > pivot:
            end -= 1
          
        # If start and end have not crossed each other,swap the numbers on start and end
        if(start < end):
            array[start], array[end] = array[end], array[start]
      
    # Swap pivot element with element on end pointer. This puts pivot on its correct sorted place.
    array[end], array[pivot_index] = array[pivot_index], array[end]
     
    # Returning end pointer to divide the array into 2
    return end
      
# The main function that implements QuickSort 
def quick_sort(start, end, array):
      
    if (start < end):
          
        # p is partitioning index, array[p] is at right place
        p = partition(start, end, array)
          
        # Sort elements before partition and after partition
        quick_sort(start, p - 1, array)
        quick_sort(p + 1, end, array)
          
# Driver code
array = [ "cherry","jackfruit","apple","mango","lemon","iceapple","banana","orange" ]
quick_sort(0, len(array) - 1, array)
  
print(f'Sorted array: {array}')
end = time.time()
print ("Execution time for Merge sort:", end - start)

# Quick sorting for list of float values
import time
start = time.time()
def partition(start, end, array):
      
    # Initializing pivot's index to start
    pivot_index = start 
    pivot = array[pivot_index]
      
    # This loop runs till start pointer crosses end pointer, and when it does we swap the pivot with element on end pointer
    while start < end:
          
        # Increment the start pointer till it finds an  element greater than  pivot 
        while start < len(array) and array[start] <= pivot:
            start += 1
              
        # Decrement the end pointer till it finds an element less than pivot
        while array[end] > pivot:
            end -= 1
          
        # If start and end have not crossed each other,swap the numbers on start and end
        if(start < end):
            array[start], array[end] = array[end], array[start]
      
    # Swap pivot element with element on end pointer. This puts pivot on its correct sorted place.
    array[end], array[pivot_index] = array[pivot_index], array[end]
     
    # Returning end pointer to divide the array into 2
    return end
      
# The main function that implements QuickSort 
def quick_sort(start, end, array):
      
    if (start < end):
          
        # p is partitioning index, array[p] is at right place
        p = partition(start, end, array)
          
        # Sort elements before partition and after partition
        quick_sort(start, p - 1, array)
        quick_sort(p + 1, end, array)
          
# Driver code
array = [ 1.3,  0.1,  0.2,  0.3,  0.4,  0.5,  0.6,  0.11,  0.13,  0.9, 0.45, 0.33, 0.456, 0.234, 0.12 ]
quick_sort(0, len(array) - 1, array)
  
print(f'Sorted array: {array}')
end = time.time()
print ("Execution time for Merge sort:", end - start)

import time
start = time.time()
def partition(start, end, array):
      
    # Initializing pivot's index to start
    pivot_index = start 
    pivot = array[pivot_index]
      
    # This loop runs till start pointer crosses end pointer, and when it does we swap the pivot with element on end pointer
    while start < end:
          
        # Increment the start pointer till it finds an  element greater than  pivot 
        while start < len(array) and array[start] <= pivot:
            start += 1
              
        # Decrement the end pointer till it finds an element less than pivot
        while array[end] > pivot:
            end -= 1
          
        # If start and end have not crossed each other,swap the numbers on start and end
        if(start < end):
            array[start], array[end] = array[end], array[start]
      
    # Swap pivot element with element on end pointer. This puts pivot on its correct sorted place.
    array[end], array[pivot_index] = array[pivot_index], array[end]
     
    # Returning end pointer to divide the array into 2
    return end
      
# The main function that implements QuickSort 
def quick_sort(start, end, array):
      
    if (start < end):
          
        # p is partitioning index, array[p] is at right place
        p = partition(start, end, array)
          
        # Sort elements before partition and after partition
        quick_sort(start, p - 1, array)
        quick_sort(p + 1, end, array)
          
# Driver code
array = [ [('Saranya',84), ('Surya',92) , ('Joy',88) , ('Sree',86), ('Ritha',89)]]
quick_sort(0, len(array) - 1, array)
  
print(f'Sorted array: {array}')
end = time.time()
print ("Execution time for selection sort:", end - start)