Quick Sorting

Quick Sorting


=============================================================
 

The QUICKSORT algorithm, first introduced by C.A.R. Hoare, is
indeed simpler than MEDIAN SORT,
http://opensourceframework.blogspot.com/2010/09/median-sorting.html

QucikSort Complexity
Best O(n log n)
Average O(n log n)
Worst  O(n^2)


=================================================================
Quick Sort Algorithm

Sort(Array)
quickSort(Array,0,n-1)
end

quickSort(Array,left,right)
if(left<right) then
pi=partition(Array,left,right)
quickSort(Array,left,pi-1)
quickSort(Array,pi+1,right)
end

partition(Array,left,right)
p=selectPivot in Array[left,right]
Swap Array[p] and Array[right]
store left
for i=left to right -1 do
if(Array[i]<=Array[rigth])
then
swap Array[i] and Array[Store]
store++
swap Array[Store] and Array[right]
return store
end

===========================================================================================

--
ANish

Median Sorting

MedianSorting


=============================================================
 

MEDIAN SORT(DIVIDE AND CONQUER) algorithm sorts an
array A of n≥1 elements by swapping the median element A[me] with the middle
element of A , creating a left and right half of the array. MEDIAN SORT
then swaps elements in the left half that are larger than A[mid] with elements in
the right half that are smaller or equal to A[mid]

Median   Sort Complexity
Best O(n log n)
Average O(n log n)
Worst  O(n^2)


=================================================================
Median Sort Algorithm

Sort(Array)
for i=1to n-1 do
medianSort(Array,0,n-1)
end

medianSort(Array,left,right)
if(left<right) then
find Median value Array[median] in Array[left,right]
mid=(right+left)/2
swap Array[mid] and Array[median]
for i=left to mid-1 do
if(Array[i]>Array[mid])then
find Array[k] <=Array[mid] where k>mid
swap A[i] and A[k]
medianSort(Array,left,mid-1)
medianSort(Array,mid+1,right)
end
===========================================================================================

--
ANish

Insertion sorting

Insertion Sorting


=============================================================
 

Use INSERTION SORT when you have a small number of elements to sort or the
elements in the initial collection are already “nearly sorted.”
Insertion Sort Complexity
Best O(n)
Average O(n^2)
Worst  O(n^2)

=================================================================
Insertion Sort Algorithm

Sort(Array)
for i=1to n-1 do
insert(Array,i,Array[i])
end

insert(Array,pos,value)
i=pos-1
while(i>=0 and Array[i]>value) do
Array[i+1]=Array[i]
--i
Array[i+1]=value
end
===========================================================================================

Cons
INSERTION SORT suffers from being too conservative for “random
data.
--
ANish