Algo-Lecture#4 divide and conquer approach-23-NOV-11.ppt

in this presentation we have explained the concept of divide and conquer approach

28. 128
64
32
16
8
4
2
1

37. Stable Sorting
Stable sorting algorithms 
maintain the relative
order of records with equal keys (i.e. 
values).
That is, a sorting algorithm is
 
stable 
if whenever
there are two records
 
R 
and 
S 
with the same key
and with
 
R 
appearing before 
S 
in the original
list,
 
R 
will appear before 
S 
in the sorted list.
Some examples of stable sorting algorithms
are
bubble sort and
mergesort( although the 
stability of

mergesort
is dependent upon how it is implemented).
Some example of
unstable 
sorting algorithms
are
heapsort
and quicksort(quick 
sort can
be made 
stable,

but
then it won't be quicky any more).

48. In-Place
Algorithm
An
in-place algorithm is an algorithm that does not need an
extra
space and produces an output in the same memory
that
contains the data by transforming the input ‘in-place’.
However,
a small constant extra space used for variables is
allowed.