RSS

Tag Archives: algorithm

Bubble Sort Algorithm

A simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

bubble-sort-algorithm

Reference: Wikipedia

 
Leave a comment

Posted by on March 5, 2015 in General

 

Tags: ,

Heapsort Algorithm

A comparison-based sorting algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the smallest element and moving that to the sorted region.
Larger nodes don’t stay below smaller node parents. They are swapped with parents, and then recursively checked if another swap is needed, to keep larger numbers above smaller numbers on the heap binary tree.

heapsort-algorithm

Reference: Wikipedia

 
Leave a comment

Posted by on January 14, 2015 in General

 

Tags: ,

QuickSort Algorithm

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

The steps are:

  1. Pick an element, called a pivot, from the array.
  2. Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called thepartition operation.
  3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

quicksort-algorithm

Reference: Wikipedia

 
Leave a comment

Posted by on December 30, 2014 in General

 

Tags: ,

Selection Sort Algorithm

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

selection-sort-algorithm

Reference: Wikipedia

 
Leave a comment

Posted by on December 19, 2014 in General

 

Tags: ,

Insertion Sort Algorithm

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

insertion-sort-algorithm

Reference: Wikipedia

 
Leave a comment

Posted by on December 12, 2014 in General

 

Tags: ,

Metaphone

a phonetic algorithm, published by Lawrence Philips in 1990, for indexing words by their English pronunciation. It uses information about variations and inconsistencies in English spelling and pronunciation to produce a more accurate encoding, which does a better job of matching words and names which sound similar.

Source: Wikipedia: Metaphone

Why does this matter?

In real life, this algorithm can be used for voice translation as well as similar sounding names search.

 
Leave a comment

Posted by on November 25, 2014 in General

 

Tags: ,

Levenshtein Distance

a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other.

Source: Wikipedia: Levenshtein Distance

Why does this matter?

Levenshtein distance is a form of approximate string matching. In real life application, Levenshtein distance can be used in spell checking, correction in OCR system (Optical Character Recognition), record linkage, auto suggest words in smart phone and many more.

 
Leave a comment

Posted by on July 29, 2014 in General

 

Tags: ,

 
%d bloggers like this: