wu :: forums « wu :: forums - Median of 5 » Welcome, Guest. Please Login or Register. Apr 19th, 2024, 12:58am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: william wu, Icarus, towr, SMQ, Eigenray, ThudnBlunder, Grimbal)    Median of 5 « Previous topic | Next topic » Pages: 1 2  Reply Notify of replies Send Topic Print    Author  Topic: Median of 5  (Read 37020 times) Jon Anderson Guest Re: Median of 5   « Reply #25 on: Feb 4th, 2005, 1:40pm » Quote Modify Remove Just so you know,the median of median method is used to find the pivot for solving the selection problem, not for doing a quicksort.  The selection problem is that of finding the kth smallest element in an unsorted list of n elements.  The best approach is to apply the quicksort algorithm.  If the pivot lands in spot k, then you are done.  Otherwise, you have to run the algorithm on whichever half of the list k happens to be in, not both as in the quicksort.  It can be shown that by using the median-of-medians approach, the worst case scenario is still solved in linear time.  (22n by comparisions) IP Logged Pages: 1 2  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board