wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> One pass sort
        
(Message started by: sateesp on Jul 28th, 2010, 10:46pm)
Title: One pass sort
Post by sateesp on Jul 28th, 2010, 10:46pm
Given an array with consists of 0's, 1's and 2's only in random order.

Can we sort this array in one pass?
Title: Re: One pass sort
Post by towr on Jul 29th, 2010, 2:47am
Yes. It's known as http://en.wikipedia.org/wiki/Dutch_national_flag_problem

See also
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1100111371
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1197342769
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1231090929
Title: Re: One pass sort
Post by birbal on Jul 29th, 2010, 11:21am
Save begining for 0's , ending for 2's , then you automatically have all 1's in the middle.
Its sorted :)


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