RE: Challenge for Sort programs.
- Posted by Don Phillips <Graebel at hotmail.com> Jun 04, 2002
- 404 views
>Looks nice but it won't sort sequences. >Hook it up to a test harness & see what it does. > >Karl Bochert I dont have a good way to test it. I could (I guess) peek into the high performance clock on my chip, but I dont really have any need for a quick sort of any kind. Was just throwing it out there to see how it did and maybe help someone out. Heres a slightly modified version that should sort anything. function QuickSort( sequence Data ) sequence Left sequence Right object Pivot object NextVal -- initialize Left = {} Right = {} Pivot = Data[ 1 ] -- partition both halves for ListIter = 2 to length(Data) do NextVal = Data[ ListIter ] if compare(NextVal,Pivot) < 0 then Left = append( Left, NextVal ) else Right = append( Right, NextVal ) end if end for -- sort partions if length(Left) > 1 then Left = QuickSort(Left) end if if length(Right) > 1 then Right = QuickSort(Right) end if -- join back return( Left & {Pivot} & Right ) end function >I think it's dangerous to choose the 1st element as the pivot >because of the possibility of pre-sorted data. > Its always a possibility that pre sorted data could come in, but dangerous no. Wont hurt the algo any. Only thing is with QuickSort is that pre-sorted data is actually its worse case speed wise. If you use this and the data *might* be pre-sorted, you might look into randomizing it first. Little more overhead, but no worse case anymore... _________________________________________________________________ Chat with friends online, try MSN Messenger: http://messenger.msn.com