algorithms

KO | EN

gitlite — search

#javascript #python #hacktoberfest #react #ai #typescript #llm #go #golang #android #machine-learning #rust #deep-learning #linux

★ 17 Open GitHub ↗

Implementations of most commonly used algorithms in various languages. Thanks a ton to the wiki's which provided pesudo codes

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

>Implementation of commonly used algorithms.

Searching and sorting alogrithms implemented in:

* Python

* Ruby

* Perl

* Java

* JS

===

##Pesudocodes of the Alogrithms :

#Binary search O(log n)
		
##Recursive 
		BinarySearch(A[0..N-1], value, low, high) {
			if (high < low)
				return not_found
			mid = (low + high) / 2
			if (A[mid] > value)
				return BinarySearch(A, value, low, mid-1)
			else if (A[mid] < value)
				return BinarySearch(A, value, mid+1, high)
			else
				return mid
		}

#I List of sorting algorithms with complexity O( n^2 )

#0. Bubble Sort :

repeat
			hasChanged := false
			decrement itemCount
			repeat with index from 1 to itemCount
			if (item at index) > (item at (index + 1))
				swap (item at index) with (item at (index + 1))
            hasChanged := true
		until hasChanged = false

#1. Insertion Sort :

function insertionSort(array A)
			for i from 1 to length[A]-1 do
				value := A[i] 
				j := i-1
				while j >= 0 and A[j] > value do
					A[j+1] := A[j]
					j := j-1
				done
				A[j+1] = value
		done

#2. Selection Sort :

function selectionSort(array A)
			max = length(A) - 1

for i from 0 to max
				key = A[i]
				keyj = i

for j from i+1 to max
				 if A[j] < key
						key = A[j]
						keyj = j

lst[keyj] = A[i]
			 lst[i] = key
		 done

## II Algorithms with complexity as O(n log n)

#0. Heap Sort :

function heapSort(a, count) is
		input: an unordered array a of length count
 
		(first place a in max-heap order)
		heapify(a, count)
 
		end := count - 1
		while end > 0 do
			(swap the root(maximum value) of the heap with the
			last element of the heap)
			swap(a[end], a[0])
			(put the heap back in max-heap order)
			siftDown(a, 0, end-1)
			(decrement the size of the heap so that the previous
			max value will stay in its proper place)
		end := end - 1
 
		function heapify(a,count) is
		(start is assigned the index in a of the last parent node)
		start := (count - 2) / 2
   
		while start ≥ 0 do
			 (sift down the node at index start to the proper place
			such that all nodes below the start index are in heap
			order)
			siftDown(a, start, count-1)
			start := start - 1
		(after sifting down the root all nodes/elements are in heap order)
 
		function siftDown(a, start, end) is
		(end represents the limit of how far down the heap to sift)
		root := start

while root * 2 + 1 ≤ end do       (While the root has at least one child)
			child := root * 2 + 1           (root*2+1 points to the left child)
			(If the child has a sibling and the child's value is less than its sibling's...)
			if child + 1 ≤ end and a[child] < a[child + 1] then
				child := child + 1           (... then point to the right child instead)
			if a[root] < a[child] then     (out of max-heap order)
				swap(a[root], a[child])
				root := child                (repeat to continue sifting down the child now)
			else
				 return

# 1. Merge Sort:

function mergesort(m)
		var list left, right, result
		if length(m) ≤ 1
			return m
		else
			 var middle = length(m) / 2
			for each x in m up to middle - 1
				add x to left
			for each x in m at and after middle
				add x to right
			left = mergesort(left)
			right = mergesort(right)
			if last(left) ≤ first(right) 
				append right to left
				return left
			result = merge(left, right)
			return result

function merge(left,right)
		var list result
		while length(left) > 0 and length(right) > 0
			if first(left) ≤ first(right)
				append first(left) to result
				 left = rest(left)
			 else
				append first(right) to result
				right = rest(right)
		if length(left) > 0 
			append rest(left) to result
		if length(right) > 0 
			append rest(right) to result
		return result

# 2. Quick Sort:
 
		function quicksort(array)
			var list lessOrEqual, greater
			if length(array) ≤ 1  
				return array  
			pivot := select a pivot value
			for each x in array
				if x ≤ pivot then add x to lessOrEqual
				if x > pivot then add x to greater
			return concatenate(quicksort(lessOrEqual), pivot, quicksort(greater))

##III Alogrithm with O(n log^2 n)

#0. Shell Sort

input: an array a of length n with array elements numbered 0 to n − 1

inc ← round(n/2)
		while inc > 0 do:
			for i = inc .. n − 1 do:
			 temp ← a[i]
				j ← i
				while j ≥ inc and a[j − inc] > temp do:
					a[j] ← a[j − inc]
					j ← j − inc
				a[j] ← temp
			inc ← round(inc / 2.2)

algorithms

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README