From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 108717,f142583de41ba830 X-Google-Attributes: gid108717,public X-Google-Thread: fd7c9,f142583de41ba830 X-Google-Attributes: gidfd7c9,public X-Google-Thread: 1014db,f142583de41ba830 X-Google-Attributes: gid1014db,public X-Google-Thread: 103376,f142583de41ba830 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-02-01 04:48:39 PST Newsgroups: comp.lang.c,comp.lang.ada,comp.programming,comp.lang.forth Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!transit.news.xs4all.nl!newsfeed.xs4all.nl!xs4all!sparc!albert From: albert@spenarnc.xs4all.nl (Albert van der Horst) Subject: Re: Quick Sort Median of Three worst case Organization: Dutch Forth Workshop Message-ID: References: <588d8bf4.0301301425.586b0ae4@posting.google.com> Date: Fri, 31 Jan 2003 09:59:24 GMT Xref: archiver1.google.com comp.lang.c:170674 comp.lang.ada:33673 comp.programming:50128 comp.lang.forth:30190 Date: 2003-01-31T09:59:24+00:00 List-Id: In article <588d8bf4.0301301425.586b0ae4@posting.google.com>, goms wrote: >Hi, > >I would like to know the running time of the Median of Three routine >version Quick Sort for the following input > >(a) 2, 3, 4, ..,N-1, N, 1 > >What is the running time for the following input > >(b) 1, N, N-1, ....., 4, 3, 2 > >Is the above said inputs (a) and (b) the worst case? and is the >running time is O(N^2) ? > >I know that using Median of Three routine version of Quick Sort for, > >a) sorted input > the pivot is always in the middle, so the time would be O(nlogn) > >b) reverse-ordered input > the pivot is always in the middle, so the time would be O(nlogn) > > >A reply with explanation will be great. Thanks in Advance. Your questions cannot be answered because they are critically dependant on implementation details. However I can offer the following explanation: The worst case for a simplistic qsort is O(N^2) (where the pivot happens to be the minimum of the remainder to be sorted.) (This has actually occurred on sorted sets, where the first element is chosen as a pivot.) On a very contrived data set the Median of Three would result in a pivot that is the second minimum item of the remainder to be sorted.) This too would be be O(N^2). Some qsorts use random selection for the pivot. The data set would need to be contrived for exactly the RNG and the random seed, but it is still possible. Extremely unlikely, but present as a worst case. QED -- -- Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS Q.: Where is Bin? A.: With his ma. Q.: That makes the Saudi's terrorists, then? A.: No, George already owns their oil. albert@spenarnc.xs4all.nl http://home.hccnet.nl/a.w.m.van.der.horst