HCSD Data Structures Case Study 6

                                                  SORTING

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 bubble sort works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary. This process is repeated as many times as necessary, until the array is sorted.Since the worst case scenario is that the array is in reverse order, and that the first element in sorted array is the last element in the starting array, the most exchanges that will be necessary is equal to the length of the array. Here is a simple example:

Given an array 23154 a bubble sort would lead to the following sequence of partially sorted arrays: 21354, 21345, 12345. First the 1 and 3 would be compared and switched, then the 4 and 5. On the next pass, the 1 and 2 would switch, and the array would be in order.

The basic code for bubble sort looks like this, for sorting an integer array:

for(int x=0; x<n; x++)

 {

  for(int y=0; y<n-1; y++)

  {

   if(array[y]>array[y+1])

   {

    int temp = array[y+1];

    array[y+1] = array[y];

    array[y] = temp;

   }

  }

 } 

Selection 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.

Insertion Sort-Among simple sort algorithms
insertion sort 
is the best (uses the less number of comparisons that Bubble sort 
and selection sort). It is the most efficient sorting.

Shell Sort-Shellsort, also known as Shell sort or Shell's method is an in-place comparison sort. It generalizes an exchanging sort, such as insertion or bubble sort, by allowing the comparison and exchange of elements that lie far apart.

Bucket Sort-Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets.
 Each bucket is then sorted individually, either using a different 
sorting algorithm, or by recursively applying the bucket sorting 
algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. 

Merge Sort-Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

Quicksort- Quicksort is a very fast unstable sorting algorithm based on divide and conquer principle. It's asymptotic complexity is , but the expected complexity is only  and quicksort usually outperforms other algorithms in this complexity class such as heapsort or merge sort

.Algorithm picks one random element of the input array (pivot).
 In next steps it reorganizes the array in such a way, that all elements
 with higher value than the pivot are located before the pivot and all 
elements with lower value than the pivot are after it. We can see that 
the pivot itself is located at the correct positioncomplexity class such as complete heapsort or merge sort.