Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!goblin1!goblin.stu.neva.ru!postnews.google.com!news1.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail NNTP-Posting-Date: Wed, 22 Feb 2012 21:52:16 -0600 Message-ID: <4F45B7F2.2BE5@mindspring.com> Date: Wed, 22 Feb 2012 22:52:18 -0500 From: pete Reply-To: pfiland@mindspring.com Organization: PF X-Mailer: Mozilla 3.04Gold (WinNT; I) MIME-Version: 1.0 Newsgroups: comp.programming Subject: Re: What algorithm is this? (Variant of Selection sort?) References: <1bbf76cc-241c-4936-bf52-3d48e1180c41@kn4g2000pbc.googlegroups.com> <4F3A7F10.6F65@mindspring.com> <4F3B5380.F0B@mindspring.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 94 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.156.228.136 X-Trace: sv3-Ggp7yJ8hNj4IqRwqUGu8z+SK4XKsnBtkpZcGt0++1+UcPbeKQjyPnVpMHD1Fl0vixoTJ36DMT7T/rAk!+u7KzPwST1ilczWZqM9r7bd7ufOJ8U/gq5aarT/sAxfptTmDaf6HBYH5f3sxyXVUmnZi3sKxfE/u!Nzdc1rNlHz0= X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 4549 Xref: x330-a1.tempe.blueboxinc.net comp.programming:1336 pete wrote: > > R. Rajesh Jeba Anbiah wrote: > > > > On Feb 14, 8:34 pm, pete wrote: > > > R. Rajesh Jeba Anbiah wrote: > > > > On Feb 13, 12:47 pm, Zeljko Vrba wrote: > > > > > On 2012-02-13, R. Rajesh Jeba Anbiah wrote: > > > > > > > > > > > $arr = array(10,9,8,7,6,5,4,3,2,1); > > > > > > for($i=0, $len=count($arr); $i<$len-1; ++$i){ > > > > > > for($j=$i+1, $len=count($arr); $j<$len; ++$j){ > > > > > > if ($arr[$i] > $arr[$j]) { > > > > > > $temp = $arr[$i]; > > > > > > $arr[$i] = $arr[$j]; > > > > > > $arr[$j] = $temp; > > > > > > } > > > > > > } > > > > > > } > > > > > > ?> > > > > > > > > > As I understand, selection sort is > > > > > > about finding index first and > > > > > > doing the swap. What about the above? Is it a variant or sort with > > > > > > some name? TIA > > > > > > > > Looks like textbook implementation of Bubble sort. > > > > > > > Yes, found in textbook only. But, it's not a Bubble sort. Right? > > > >http://en.wikipedia.org/wiki/Bubble_sort > > > > > > It looks a lot like bubble sort, > > > but it is not bubble sort. > > > > > > Bubble sort works by swapping adjacent elements. > > > The algorithm which you have shown, > > > swaps elements which are not adjacent. > > > > > > I would just call your algorithm "simple selection sort", > > > while realizing that there are variations > > > on the way that it can be implemented. > > > > > > Selection sorts, sort from one end to the other. > > > > > > Knuth classifies heapsort > > > as belonging to the selection sort family of algorithms. > > > As heapsort is typically implementd for sorting arrays: > > > the last element is sorted first, > > > and then the next to last, > > > and so on. > > > > Thanks for your valuable feedback. On a personal note I'm thinking > > why it's not officially documented and named--even though it's > > available in some textbooks as "bubble sort". > > That is definitely not bubble sort. > > This is bubble sort: > > $arr = array(10,9,8,7,6,5,4,3,2,1); > for($i=0, $len=count($arr); $i<$len-1; ++$i){ > for($j=$len-1, $len=count($arr); $j>$i; --$j){ > if ($arr[$j-1] > $arr[$j]) { > $temp = $arr[$j-1]; > $arr[$j-1] = $arr[$j]; > $arr[$j] = $temp; > } > } > } > > Bubble sort is a stable sort, > simple selection sort is not. One reason that there might not be too much literature on this particular variety of simple selection sort, is that it is not very good. If one were desperate to find a metric by which simple selection sort could be said to be better than bubble sort, you could say that ordinary simple selection sort does (n - 1) swaps for worst case, while bubble sort does (((n - 1) * n) / 2) swaps for worst case. But this particular variety of selection sort does (((n - 1) * n) / 2) swaps for worst case and it does (((n - 1) * n) / 2) comparisons for every case, which means that by any metric, its not as good as bubble sort. And bubble sort is not really a very good algorithm. -- pete