Sorting Basics

Sorting

http://www.youtube.com/playlist?list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U

Sorting is basically essential to do the searching.

Linear Search:
If we are to search a data in an unsorted pool of data, we call the search as Linear Search.
If the number of data in the pool is 'n', and we are to search for a data 'd', then we need to compare 'd' against (n-1) elements.
If n is 2^64, and if each comparison takes 1 ms, then we will need 2^64 ms (worst-case) to find the data.

size = n
n = 2^64 => 2^64 comparisons

Sorted:
If we the pool is sorted, then we can use Binary search.
size = n
And if n = 2^64 => 64 ms

Number of Sorting algorithms:

1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Heap Sort
7. Counting Sort
8. Radix Sort
9. [And many more]

Classification of these algorithms is based on:

1. Time Complexity (Big O Notation)
2. Space Complexity or Memory Usage [Merge sort, uses temporary storage]
3. Stability (already sorted items in the input, will be preserved in the sorted list). For ex, cards of 6heart and 6clubs along with other cards, will remain in same order even in sorted list
4. Internal (RAM) or External Sort (data in Disc or tapes)
5. Recursive (Quick and Merge) and Non-Recursive