Sorts

««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.Most1 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

1. out performs even quick sort if list s already sorted or almost sorted
2. best used if num is less (10 or less)
3. in-place algo n takes
• O(n) time 4 best case(already sorted)
• O(n2) for avg n wrst case

more…..

#### Merge Sort

1. Ths s comparison sort,It is easy to implement merge sort such that it is stable
2. divide and conquer algorithmic paradigm
3. 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
for each x in m after middle
left = mergesort(left)
right = mergesort(right)
result = merge(left, right)
return result

more…..

#### Quicksort

1. very efficient in practise than othr O(n lg2 n) sorting algos general purpose
2. Quicksort is a comparison sort and is not a stable sort.
3. uses 'divide n conquer' strategy
4. nearly-in-place(requires Ω(lg n) extra space) algorithm n takes
• O(n2) as wrstcase
• O(n lg n) as avg case
• O(n2) 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( n2 ) O( 1 ) Yes insertion
bubble O( n ) —— O( n2 ) 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( n2 ) O( lg n ) no partition
selection O( n2 ) O( n2 ) O( n2 ) 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.

#### roddix sort

Name Best average worst memory stable n< <2k
bucket/bin O(n.k) O(n.k) O( n2.k ) O( n.k) Yes no
counting O(n+2k) O(n+2k) O(n+2k) O(n+2k) 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.2s ) O( n.k/s.2s ) no no

««Hashing|tree»»

page revision: 31, last edited: 08 Jun 2007 01:24