Shell Sort

Shell Sort is a sorting algorithm in which the items will be converted into nearly sorted list and sort by using insertion sort.

Algorithm:

The algorithm will sort every Ath item in the list and Bth item in the list(A>B).In this process, the list will be changed into nearly sorted list. After that, we can use the insertion sort.(see Insertion Sort). Or it can be explained by deviding the list into columns.

Psuedocode:

void shellsort (int[] a, int n)
{
    int i, j, k, h, v;
    int[] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
                    1968, 861, 336, 112, 48, 21, 7, 3, 1}
    for (k=0; k<16; k++)
    {
        h=cols[k];
        for (i=h; i<n; i++)
        {
            v=a[i];
            j=i;
            while (j>=h && a[j-h]>v)
            {
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=v;
        }
    }
}

Source:
http://en.wikipedia.org/wiki/Shell_sort
http://www.sorting-algorithms.com/shell-sort
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm

Bubble Sort

 a sorting algorithm in which item is swap in the adjacent item until the list of item will be sorted just like bubble(in ascending order),the smaller item will slowly moved to the top and the larger item will slowly moved to the bottom.

Algorithm:
Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
If at least one swap has been done, repeat step 1.

Pseudocode(C++):

void bubbleSort(int arr[], int n) {
      bool swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < n - j; i++) {
                  if (arr[i] > arr[i + 1]) {
                        tmp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = tmp;
                        swapped = true;
                  }
            }
      }
}

Source:
http://en.wikipedia.org/wiki/Bubble_sort
http://www.algolist.net/Algorithms/Sorting/Bubble_sort

Insertion Sort

A sorting algorithm in which every item will be implemented a time. The first item that will be implemented is the first item in the list.

Algorithm:
The list will be devided imaginarilly by into sorted list and unsorted list. The algorithm will take the first element of the unsorted list and insert it to right place in the sorted list in every step. if there will be no item in unsorted list, the algorithm stop.

PseudoCode(C++):

void insertionSort(int arr[], int length) {
      int i, j, tmp;
      for (i = 1; i < length; i++) {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                  tmp = arr[j];
                  arr[j] = arr[j - 1];
                  arr[j - 1] = tmp;
                  j--;
            }
      }
}


Source:
http://en.wikipedia.org/wiki/Insertion_sort
http://www.algolist.net/Algorithms/Sorting/Insertion_sort

Selection Sort

is a sorting algoritm in which every item will be emplimented every time like insertion sort. Instead of inserting the first item of the unsorted list to the sorted list, the algorithm will just select the smallest value in the unsorted list and add it to the last element of the sorted list.

Algorithm:
The list will be devided imaginarilly into sorted and unsorted list. The algorithm will select the first element of the sorted list, which is, the smallest value in the group. And in every step, the algorithm will find and select the smallest item in the unsorted list and adds it to the end of the sorted list.

Pseudocode(C++):

void selectionSort(int arr[], int n) {
int i, j, minIndex, tmp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}

Source:
http://en.wikipedia.org/wiki/Selectionsort
http://www.algolist.net/Algorithms/Sorting/Selection_sort

The Big-O Notation

Big-O notation (also known as big Oh notation, big Omicron notation, Landau notation, Bachmann–Landau notation, and asymptotic notation) (along with the closely related big-Omega notation, big-Theta notation, and little 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 rates: different functions with the same growth rate may be represented using the same O notation.
In computer science, it is used in the analysis of algorithm. It used to determine the efficiency of the algorithm. When getting the big-O notation, we can get It’s magnitude of order of run time.

Example:
We have this program fragment
for(int x=0;x<n;x++)
{
statement;
for(int y=0;y<n;y++)
{
statement2;
}
}

The statement in inner loop will iterate n*n times
The statement in outer loop will iterate n times.
So, the number of step f(x) = n^2+n.

Now, we want to know the how many steps are there in the fragment. Here, we have n^2+n, where n is the number of input. So, we have f(x)=n^2+n. Basing in the formal definition(although it is not used directly) we can come up with the O notation for f(x). In analyzing algorithm, we commonly derive the O notation of f(x) by following this simplification rules.
-If f(x) is a sum of several terms, the one with the largest growth rate is kept, and all others omitted.
-If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) are omitted.
So, for f(x), the O notation for f(x) is O(n^2). In other words, f(x)=O(n^2) or f(x)” has an order of” n^2.
That’s all folks. Hope you understand. Just comment for some questions.

Source:
http://en.wikipedia.org/wiki/Big_o_notation

Empirical Analysis

First, we must know what is empiricism. Empiricism is the a theory of knowledge comes via the senses’ experience. Empiricism emphasizes the role of experience and evidence, especially sensory perception, in the formation of ideas, over the notion of innate ideas or tradition in contrast to, for example, rationalism which relies upon reason and can incorporate innate knowledge.
About empirical analysis, empirical analysis is the analysis of things in empiric way. It is an analysis of things from direct observation, experiment or scientific method, and solid evidences. To make it short, it is an analysis with the use of your senses.
Source:
http://en.wikipedia.org/wiki/Analysis_of_algorithms