|
Home
|
Sign up!
|
Projects
|
Seminars
|
Research Notes
|
Today's Lecture
|
About
|
Update Research Note Form
Course:
Research Note Topic:
Research Note Description:
This algorithm was designed by
E.K.Batcher
The first and only criteria for this sorting algorithm is that the number of elements must be of the order of
2
n
. Now the steps involved in doing so are:
i)
Divide the list of elements into 2 halves and sort them using any efficient recursive sorting algorithm.
ii)
Now swap the 2 halves.
iii)
Now take the elements in the odd and even positions resp. and sort them into 2 lists.
iv)
Now
merge
the 2 lists placing the elements of the odd positioned elements in the odd positions and resp. for the even positioned elements.
v)
Now except the first and last elements, compare and exchange(if required) pairs of consequtive even-odd elements(specifically in that order).
Note:
The
Time complexity T(n)
of this sorting algorithm is
nlog(n)
.
SORTING NETWORKS:
Sorting networks are employed when we have to sort lists of some
specific
size. These are very simple devices that only do
compare -exchange
operations.
eg. consider the below illustrated 4-element sorting network.
c__.__ b ____ b__.__ a____a ____a
b__|__ c ____ c__|__ c__.__ c__.__b
d____ d__.__ a__|__ b__|__ b__|__c
a____ a__|__ d____ d__|__ d____ d
|___________| |____________| |_____|
step1 step2    step3
A further in-depth explaination will be provided in the course of the next few days.
Your Password:
Prof. Ashay Dharwadker