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
#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
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
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)