««Hashing|tree»»

Here **sorting** is basically arranging items of the same kind, class, nature, etc. in some ordered sequence.Here v discuss several algos which do the sorting job n finally compare and analyse them.

Here v frequently face some terms.I giv a brief account of thm …..

**comparison sort** is a typ f sortin algo which can only read the list elements through a single abstract comparison operation (often a "less than or equal to" operator) that determines which of two elements should occur first in the final sorted list.Most^{1} of the sortin algos r f ths type.Examples of othr typ of sorts are **Radix sort,Bucket sort** (examines individual bits of keys),**Counting sort** (indexes using key values).

**stable sorting** algorithms maintain the relative order of records with equal keys (i.e. values).

**In-place algo:**algorithm which transforms a data structure using a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not in-place is sometimes called **not-in-place** or **out-of-place**.

#### insert'n sort

- out performs even quick sort if list s already sorted or almost sorted
- best used if num is less (10 or less)
- in-place algo n takes

- O(n) time 4 best case(already sorted)
- O(n
^{2}) for avg n wrst case

more…..

#### bubble sort

#### Merge Sort

- Ths s comparison sort,It is easy to implement merge sort such that it is stable
- divide and conquer algorithmic paradigm
- not in-place(requires Ω(n) auxiliary space)

- O(n lg n) avg case

function mergesort(m)

var list left, right, result

if length(m) ≤ 1

return m

else

middle = length(m) / 2

for each x in m up to middle

add x to left

for each x in m after middle

add x to right

left = mergesort(left)

right = mergesort(right)

result = merge(left, right)

return result

more…..

#### Quicksort

- very efficient in practise than othr O(n lg
^{2}n) sorting algos general purpose - Quicksort is a comparison sort and is not a stable sort.
- uses 'divide n conquer' strategy
- nearly-in-place(requires Ω(lg n) extra space) algorithm n takes

- O(n
^{2}) as wrstcase - O(n lg n) as avg case
- O(n
^{2}) for already sorted list

more…..

#### selection sort

- specifically an in-place,comparison sort

1. Find the minimum value in the list

2. Swap it with the value in the first position

3. Repeat the steps above for remainder of the list (starting at the second position)

Name | Best | average | worst | memory | stable | method |
---|---|---|---|---|---|---|

Insertion | O( n ) | O( n+d ) | O( n^{2} ) |
O( 1 ) | Yes | insertion |

bubble | O( n ) | —— | O( n^{2} ) |
O( 1 ) | Yes | exchanging |

merge | O(n lg n) | O(n lg n) | O(n lg n) | O( n ) | Yes | merging |

quick | O(n lg n) | O(n lg n) | O( n^{2} ) |
O( lg n ) | no | partition |

selection | O( n^{2} ) |
O( n^{2} ) |
O( n^{2} ) |
O( 1 ) | no | selection |

#### Bucket sort or bin sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

#### counting sort

#### roddix sort

Name | Best | average | worst | memory | stable | n< <2^{k} |
---|---|---|---|---|---|---|

bucket/bin | O(n.k) | O(n.k) | O( n^{2}.k ) |
O( n.k) | Yes | no |

counting | O(n+2^{k}) |
O(n+2^{k}) |
O(n+2^{k}) |
O(n+2^{k}) |
Yes | yes |

LSD roddix | O( n.k/s ) | O( n.k/s ) | O( n.k/s ) | O( n ) | Yes | no |

MSD roddix | O( n.k/s ) | O( n.k/s ) | O( n.k/s.2^{s} ) |
O( n.k/s.2^{s} ) |
no | no |