
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 <b>E.K.Batcher</b> <br> The first and only criteria for this sorting algorithm is that the number of elements must be of the order of<b> 2<sup>n</sup></b>. Now the steps involved in doing so are: <br><br><b> i)</b>Divide the list of elements into 2 halves and sort them using any efficient recursive sorting algorithm. <br><br> <b> ii)</b> Now swap the 2 halves. <br><br> <b> iii)</b> Now take the elements in the odd and even positions resp. and sort them into 2 lists. <br><br><b> iv)</b> Now <b>merge</b> the 2 lists placing the elements of the odd positioned elements in the odd positions and resp. for the even positioned elements. <br><br><b> v)</b> Now except the first and last elements, compare and exchange(if required) pairs of consequtive evenodd elements(specifically in that order). <br><br><br><b><u> Note:</u></b> The <b>Time complexity T(n)</b> of this sorting algorithm is <b>nlog(n)</b>. <br><br><br><b><u>SORTING NETWORKS:</u></b> <br><br> Sorting networks are employed when we have to sort lists of some <b>specific</b> size. These are very simple devices that only do <i><b> compare exchange</b></i> operations. <br>eg. consider the below illustrated 4element sorting network. <br><br> <br><b>c__.__ b ____ b__.__ a____a ____a<br> b____ c ____ c____ c__.__ c__.__b<br> d____ d__.__ a____ b____ b____c<br> a____ a____ d____ d____ d____ d<br> <br><br> ___________ ____________ _____ <br> step1 step2 step3</b> <br><br> A further indepth explaination will be provided in the course of the next few days.
Your Password:
Prof. Ashay Dharwadker