Data Structures & Algorithms - implemented in python

bubble_sort.py

# Bubble sort

def swap(arr, idx1, idx2):
  temp = arr[idx1]
  arr[idx1] = arr[idx2]
  arr[idx2] =  temp

def bubbleSort(arr):
  for i in range(0, len(arr)):
    swapped = False

    for j in range(0, len(arr) - 1):
      if arr[j] > arr[j + 1]:
        swap(arr, j, j + 1)
        swapped = True

    if swapped == False:
      break

test = [24, 63, 14, 56, 8, 32, 83, 17]
print(test)
bubbleSort(test)
print(test)

checkSyntax.js

function checkSyntax(str) {
    const track = [];
    const sync = {"{":"}", "[":"]", "(":")"}
    str = str.split("");
    for(let ch of str) {
        if(sync.hasOwnProperty(ch)) track.push(ch);
        else if(Object.values(sync).includes(ch)) {
            if(sync[track.pop()] !== ch) return false;
        }
    }
    return true;
}

insertion_sort.py

# Insertion sort

def swap(arr, idx1, idx2):
  temp = arr[idx1]
  arr[idx1] = arr[idx2]
  arr[idx2] =  temp

def insertionSort(arr):
  holePosition = 0
  valueToInsert = 0

  for i in range(0, len(arr)):
    valueToInsert = arr[i]
    holePosition = i

    while holePosition > 0 and arr[holePosition - 1] > valueToInsert:
      arr[holePosition] = arr[holePosition - 1]
      holePosition = holePosition - 1

    arr[holePosition] = valueToInsert

test = [24, 63, 14, 56, 8, 32, 83, 17]
print(test)
insertionSort(test)
print(test)

merge_sort.py

# Merge sort

def mergeSort(arr):
  if len(arr) == 1:
    return arr
  
  arr1 = mergeSort(arr[:len(arr)/2])
  arr2 = mergeSort(arr[len(arr)/2:])

  return merge(arr1, arr2)

def merge(arr1, arr2):
  tempArr = []
  while (len(arr1) and len(arr2)):
    if(arr1[0] > arr2[0]):
      tempArr.append(arr2[0])
      arr2.pop(0)
    else:
      tempArr.append(arr1[0])
      arr1.pop(0)

  while len(arr1):
    tempArr.append(arr1[0])
    arr1.pop(0)

  while len(arr2):
    tempArr.append(arr2[0])
    arr2.pop(0)

  return tempArr

test = [24, 63, 14, 56, 8, 32, 83, 17]
print(test)
mergeSort(test)
print(mergeSort(test))

newton_raphson.py

# a simple illustration of how to calculate newton raphson

def newton_raphson(initial_guess, eps, f, f1):
  x = f(initial_guess)
  while abs(x) < eps:
    x = x - f(x) / f1(x)
  return x

def f(x):
  return x*2

def f1(x):
  return x/2

print(newton_raphson(1.2, 0.5, f, f1))

quick_sort.py

# Quick Sort

def swap(arr, idx1, idx2):
  temp = arr[idx1]
  arr[idx1] = arr[idx2]
  arr[idx2] =  temp

def quickSort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quickSort(less) + [pivot] + quickSort(greater)

test = [24, 63, 14, 56, 8, 32, 83, 17]
print(test)
print(quickSort(test))

search_method.py

# a simple illustration of how to implement search method

def search_method(left, right, f, eps):
  x1 = f(left)
  x2 = f(right)
  while(x1*x2 >= 0):
    x1 = x2
    x2 = x2 + eps
  return [x1, x2]

selection_sort.py

# Selection sort

def swap(arr, idx1, idx2):
  temp = arr[idx1]
  arr[idx1] = arr[idx2]
  arr[idx2] =  temp

def selectionSort(arr):
  for i in range(0, len(arr)):
    min = i

    # Check minimum element
    for j in range(i + 1, len(arr)):
      if(arr[j] < arr[min]):
        min = j
      
    if min != i:
      swap(arr, min, i)


test = [24, 63, 14, 56, 8, 32, 83, 17]
print(test)
selectionSort(test)
print(test)

standard_deviation.py

# a simple illustration of how to calculate mean, standard deviation

import math


def mean(arr = []):
  sum = 0
  for x in arr:
    sum += x
  
  return sum/len(arr)

# print(mean([1,3 ,4])) # uncomment this line to test mean

def variance(arr = []):
  variances = []
  sum_of_variances = 0
  mean_of_arr = mean(arr)
  for x in arr:
    variances.append((x - mean_of_arr)**2)
  for v in variances:
    sum_of_variances += v
  return sum_of_variances

def stdDeviation(arr = []):
  return math.sqrt(variance(arr))

# print(stdDeviation([1, 42, 23, 445, 23, 23])) # uncomment this line to test deviation