As we saw with binary search, certain data structures such as a binary search tree can help improve the efficiency of searches. From linear search to binary search, we improved our search efficiency from O(n) to O(logn). We now present a new data structure, called a hash table, that will increase our efficiency to O(1), […]

A binary search algorithm (or binary chop) is a technique for finding a particular value in a linear array, by ruling out half of the data at each step, widely but not exclusively used in computer science.
A binary search finds the median, makes a comparison to determine whether the desired value comes before or […]

Data transmission and storage cost money. The more information being dealt with, the more it costs. In spite of this, most digital data are not stored in the most compact form. Rather, they are stored in whatever way makes them easiest to use, such as: ASCII text from word processors, binary code that can be […]

Heapsort is one of the best general-purpose sorting algorithms, a comparison sort and part of the selection sort family.
Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime. The primary advantage of the heap sort is its efficiency. The execution time […]

Pick an element from the array (the pivot), partition the remaining elements into those greater than and less than this pivot, and recursively sort the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.
Quick-sort is a randomized sorting […]

Selection sort performs sorting by repeatedly putting the largest element in the unprocessed portion of the array to the end of the this unprocessed portion until the whole array is sorted.
In a loop, the highest element from the unsorted zone is selected (hence the name Selection Sort) and placed at the end of the unsorted […]

In an ancient city in India, so the legend goes, monks in a temple have to move a pile of 64 sacred disks from one location to another. The disks are fragile; only one can be carried at a time. A disk may not be placed on top of a smaller, less valuable disk.
And, there […]

Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted. It inserts each element of the array into its proper position.
Run time is O(n^2) because of moves. Insertion sort is an example of an incremental algorithm; it builds the sorted […]

Backtracking method tries to find a solution by trying one of several choices. If the choice proves incorrect, computation backtracks or restarts at the point of choice and tries another choice.
Scope: The most widespread use of backtracking is in the execution of regular expressions. For example, the simple pattern “a*a” will fail to match the […]

A Las Vegas algorithm is a randomized algorithm that always gives the correct answer. Because of its nondeterministic nature, the run-time of a Las Vegas algorithm is a random variable.
An example of such an algorithm would be the randomized quickSort algorithm, it takes a random pivot point but at the end you get sorted data.
Scope: […]

It can be described as follows: solve each small problem once, saving their solution; use the solutions of small problems to obtain solutions to larger problems.
The difference between dynamic programming problems and divide and conquer problems is the fact that the sub problems are not independent.
Scope: Dynamic programming algorithms are mostly used for optimization problems. […]

The divide and conquer method works as follows, divide big problem into smaller sub problems; conquer each sub problem separately; merge the solutions of the sub problems into the solution of the big problem.
Usually, better running times are obtained when the size of the subproblems are roughly equal. To write a recursive algorithm, find how […]

The Monte Carlo method is a way of solving problems using statistical methods; stochastic technique (which means using random numbers) and probability.
Given some probability, P, that an event will occur in certain conditions, a computer can be used to generate those conditions repeatedly. The number of times the event occurs divided by the number of […]

A greedy algorithm repeatedly executes a procedure which tries to maximize the return based on examining local conditions, with the hope that the outcome will lead to a desired outcome for the global problem.
In some cases such a strategy is guaranteed to offer optimal solutions, and in some other cases it may provide a compromise […]

Bubble sort, sometimes shortened to bubblesort, also known as exchange sort, is a simple sorting algorithm.
It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, […]