SORTING

1.BUBBLE SORT
It is the simplest sorting algorithm that performs repeatedly and swapping the first element to the second element. And make it into a sorting algorithm. it performs swapping if it in a wrong order, for example the list of a student during flag ceremony; the student must be in order according to their hight to make it orderly net and orderly arrange into sorting line.

A.Illustration:
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 ) \to ( 1 5 4 2 8 ) Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 ) \to ( 1 4 5 2 8 )
( 1 4 5 2 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 ) Now, since these elements are already in order, algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. Algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Finally, the array is sorted, and the algorithm can terminate.
[http://en.wikipedia.org/wiki/Bubble_sort]

2.INSERTION SORT
It is the is a simple sorting algorithm, in which each element from unsorted algorithm will pick one by one and put it into sorted. the new list and the remaining elements can share the array's space, insertion is expensive it required shifting all the following elements over by one.

A. Illustration:

Example

The example below shows the steps necessary to sort 6 elements. White elements are unsorted, grey elements have been sorted and the red element has been inserted in the current step.
833 197 153 634 889 381
833 197 153 634 889 381
833 197 153 634 381 889
833 197 153 381 634 889
833 197 153 381 634 889
833 153 197 381 634 889
153 197 381 634 833
[http://corewar.co.uk/assembly/insertion.htm]

3.SHELL SORT
It is sort by moving out of order elements more than one position at a time. Arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort is the best implementation of this sorting algorithm. Although this method is inefficient for large data sets, it is one of the fastest algorithms for sorting small numbers of elements. The advantage of this algorithm is that it requires relatively small amounts of memory.

A.Illustration:

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, and then 1-gap sort (simple insertion sort).
[http://en.wikipedia.org/wiki/Shell_sort]

4.MERGE SORT
It works by comparing every two elements and swapping them if the first should come after the second then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on;it is stable,meaning that it preserves the input order of equal elements in the sorted output.

A.Illustration: