notes.txt

#Why study sorting algorithms
- Sorting can reduce the complexity of a problem.
- The sorting algos have a direct application in searching algorithms, database algorithms,
  devide and conquer methods, data structure algorithms etc.
- It is more of an academic exercise meant to test your knowledge of CS  fundamentals and communication skills.


# Questions to ask before using the algos
- How big is the collection being sorted ?
- How much memory is at disposal
- Will the collection grow or not

* Answering this qsns is important because some algos like merge sort may need a lot of space to run
* On the other hand insertion sort is not the fasted, yet requires less memory resource to run


# Some of the common algorithms include:
@ Selection Sort
@ Bubble Sort
@ Insertion Sort
@ Merge Sort
@ Quick Sort
@ Heap Sort
@ Counting Sort
@ Radix Sort
@ Bucket Sort

# Classification of a sorting algorithm
- Classification of algorithms is based on the following:
> Number of Swaps or Inversion. This is the number of times the algorithm swaps elements to sort the input. 
  Selection Sort  requires the minimum number of swaps.

> Number of Comparisons. This is the number of times the algorithm compares elements to sort the input. 
  Using Big-O notation, the sorting algorithm examples listed above require at least  O(nlogn) comparisons in the best case 
  and  O(n^2)  comparisons in the worst case for most of the outputs.

> Recursion or Non-Recursion Some sorting algorithms, such as  Quick Sort , use recursive techniques to sort the input.
  Other sorting algorithms, such as  Selection Sort  or  Insertion Sort , use non-recursive techniques. 
  Finally, some sorting algorithm, such as  Merge Sort , make use of both recursive as well as non-recursive techniques to sort the input

> Based on Stability Sorting algorithms are said to be  stable  if the algorithm maintains the relative order of elements with equal keys.
  In other words, two equivalent elements remain in the same order in the sorted output as they were in the input.

> Insertion sort ,  Merge Sort , and  Bubble Sort  are stable

> Heap Sort  and  Quick Sort  are not stable

> Based on Extra Space Requirement Sorting algorithms are said to be  in place  if they require a constant  O(1)  extra space for sorting.

> Insertion sort  and  Quick-sort  are  in place  sort as we move the elements about the pivot and do not actually use a separate array 
  which is NOT the case in merge sort where the size of the input must be allocated beforehand to store the output during the sort.

> Merge Sort  is an example of  out place  sort as it require extra memory space for its operations.

1. Insertion Sort
- Is simple
- Best used on shorter or amost sorted lists 
- Looks at one list element per iteration and grows a sorted output list by placing an
  element in its correct position.
- Sorts in place, so memory usage is low
- Average runtime is O(n^2)