Friday, February 11, 2011

Insertion Sort

     Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

  • Simple implementation
  • Efficient for (quite) small data sets
  • Adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
  • More efficient in practice than most other simple quadratic, i.e. O(n2) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
  • Stable, i.e. does not change the relative order of elements with equal keys
  • In-place, i.e. only requires a constant amount O(1) of additional memory space
  • Online, i.e. can sort a list as it receives it


Algorithm


     Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.

The most common variant of insertion sort, which operates on arrays, can be described as follows:

  1. Suppose there exists a function called Insert designed to insert a value into a sorted sequence at the beginning of an array. It operates by beginning at the end of the sequence and shifting each element one place to the right until a suitable position is found for the new element. The function has the side effect of overwriting the value stored immediately after the sorted sequence in the array.
  2. To perform an insertion sort, begin at the left-most element of the array and invoke Insert to insert each element encountered into its correct position. The ordered sequence into which the element is inserted is stored at the beginning of the array in the set of indices already examined. Each insertion overwrites a single value: the value being inserted.





Reference:

http://en.wikipedia.org/wiki/Insertion_sort

Shell Sort

     Shell sort is a sorting algorithm, devised by Donald Shell in 1959, that is a generalization of insertion sort, which exploits the fact that insertion sort works efficiently on input that is already almost sorted. It improves on insertion sort by allowing the comparison and exchange of elements that are far apart. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted.


Analysis

     Although Shell sort is easy to code, analyzing its performance is very difficult and depends on the choice of increment sequence. The algorithm was one of the first to break the quadratic time barrier, but this fact was not proven until some time after its discovery.
The initial increment sequence suggested by Donald Shell was [1,2,4,8,16,...,2k], but this is a very poor choice in practice because it means that elements in odd positions are not compared with elements in even positions until the very last step. The original implementation performs O(n2) comparisons and exchanges in the worst case. A simple change, replacing 2k with 2k-1, improves the worst-case running time to O(N3/2), a bound that cannot be improved.
A minor change given in V. Pratt's book improved the bound to O(n log2 n). This is worse than the optimal comparison sorts, which are O(n log n), but lends itself to sorting networks and has the same asymptotic gate complexity as Batcher's bitonic sorter.
     Consider a small value that is initially stored in the wrong end of the array. Using an O(n2) sort such as bubble sort or insertion sort, it will take roughly n comparisons and exchanges to move this value all the way to the other end of the array. Shell sort first moves values using giant step sizes, so a small value will move a long way towards its final position, with just a few comparisons and exchanges.
     One can visualize Shell sort in the following way: arrange the list into a table and sort the columns (using an insertion sort). Repeat this process, each time with smaller number of longer columns. At the end, the table has only one column. While transforming the list into a table makes it easier to visualize, the algorithm itself does its sorting in-place (by incrementing the index by the step size, i.e. using i += step_size instead of i++).
For example, consider a list of numbers like [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. If we started with a step-size of 5, we could visualize this as breaking the list of numbers into a table with 5 columns. This would look like this:


13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10


We then sort each column, which gives us
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
When read back as a single list of numbers, we get [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Here, the 10 which was all the way at the end, has moved all the way to the beginning. This list is then again sorted using a 3-gap sort as shown below.


10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45


Which gives us


10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
Now all that remains to be done is a 1-gap sort (simple insertion sort).

Reference:
http://en.wikipedia.org/wiki/Shell_sort 

Selection Sort

     Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.
Algorithm
The algorithm works as follows:
  1. Find the minimum value in the list
  2. Swap it with the value in the first position
  3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)
Effectively, the list is divided into two parts: the sublist of items already sorted, which is built up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array.
Here is an example of this sort algorithm sorting five elements:
64 25 12 22 11
11 25 12 22 64
11 12 25 22 64
11 12 22 25 64
11 12 22 25 64   
(nothing appears changed on this last line because the last 2 numbers were already in order)
Selection sort can also be used on list structures that make add and remove efficient, such as a linked list. In this case it's more common to remove the minimum element from the remainder of the list, and then insert it at the end of the values sorted so far. For example:
64 25 12 22 11
11 64 25 12 22
11 12 64 25 22
11 12 22 64 25
11 12 22 25 64
Reference:
http://en.wikipedia.org/wiki/Selection_sort

Bubble Sort

      Bubble sort, also known as sinking sort, is 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. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. The equally simple insertion sort has better performance than bubble sort, so some have suggested no longer teaching the bubble sort.

Step-by-step example

Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared.
First Pass:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Finally, the array is sorted, and the algorithm can terminate.

Reference:
http://en.wikipedia.org/wiki/Bubble_sort


Wednesday, February 2, 2011

Big O Notation

          In mathematics, computer science, and related fields, Big-O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. Big-O notation characterizes functions according to their growth rate: different functions with the same growth rate may be represented using the same O notation.
          Although developed as a part  of pure mathematics, this notation is now frequently also used in the analysis of algorithms to describe an algorithm's usage of computational resources: the worst case or average case running time or memory usage of an algorithm is often expressed as a function of the length of its input using Big-O notation.
          Big -O notation has two main areas of application. In mathematics, it is commonly used to describe how closely a finite series approximates a given function, especially in the case of a truncated Taylor series or asymptotic expansion. In computer science, it is useful in the analysis of algorithms. In both applications, the function g(x) appearing within the O(...) is typically chosen to be as simple as possible, omitting constant factors and lower order terms.

Big-O Notation and Analysis of Algorithm
          In our study of algorithms, nearly every function whose order we are interested in finding is a function that defines the quantity of some resource consumed by a particular algorithm in relationship to the parameters of the algorithm. This function is usually not the same as the algorithm itself, but is a property of the algorithm. Although Big-O notation is a way of describing the order of a function, it is also often meant to represent the time complexity of an algorithm.

Reference:
http://en.wikipedia.org/wiki/Big_O_notation
http://www.eecs.harvard,edu/~ellard/Q-97/HTML/root/nodes8.html 

Analysis of Algorithm

          Analysis of algorithm is a field of computer science that is dedicated to understanding the complexity of algorithms. Algorithms are generally defined as processes that perform a series of operations to an end. Algorithms can be expressed in many ways, in flow charts, a natural languages, and computer programming languages.
          To analyze an algorithm is to determine the amount of resources (such as time and storage)necessary to execute it.
          Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem.

          In order to learn more about an algorithm, we can analyze it. By this we mean to study the specification of the algorithm and to draw conclusions about how the implementations of that algorithm will performin general. We can:
  • determine the running time of a program asa a function of its inputs;
  • determine the total or maximum memory space needed for program data;
  • determine the total size of the program code;
  • determine whether the program correctly computes the desired result;
  • determine the complexity of the program;
  • determine the robustness of the program.
In general, algorithm analysis is most concerned with finding out how much time a program takes to run, and how much memory storage space it needs to execute the program. In particular, computer scientists use algorithm analysis to determine how the data imputed into a program affects its total running time, how much memory space the computer needs for  program data, how much space the program's code takes in the computer, whether an algorithm produces correct calculations, how complex a program is, and how well it deals with unexpected results.

Reference:
http://www.wisegeek.com/topics/algorithm-analysis.htm
http://www.wisegeek.com/what-is-algorithm-analysis.htm

Empirical Analysis

The word empirical denotes information gained by means of observation, experience, or experiment. Empirical data is data that is produced by an experiment or observation. A central concept in modern science and the scientific method is that all evidence must be empirical, or empirically based, that is, dependent on evidence or consequence that are observable by the senses.
In a second sense "empirical" in science may be synonymous with "experimental." In this sense, an empirical result is an experimental observation.
Empirical research is a way of gaining knowledge by means of direct observation or experience. It is used to answer empirical questions, which must be precisely defined and answerable with data.

Empirical Cycle
A.D. de Groot's empirical cycle:

Observation: The collecting and organization of empirical facts; forming hypothesis.
Induction: Formulating hypothesis.
Deduction: Deducting consequences of hypothesis as testable predictions.
Testing: Testing the hypothesis with new empirical material.
Evaluation: Evaluating the outcome of testing.  

Reference:
http://en.wikipedia.org/wiki/Empirical
http://en.wikipedia.org/wiki/Empirical_research