Talk:Gnome sort

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

formatting problems[edit]

I posted some C++ code so that if its wanted anyone can use it, free

The code black needs to be less rigid in formatting so that code paste can be easier.

--My IQ >> 160 (talk) 19:39, 12 August 2010 (UTC)[reply]

Implementation transwiki[edit]

I've been told that Wikipedia is not the place for excessive code implementations, and I'm inclined to agree. Where would the the proper place to which all this code should be transwikied? ~ Booyabazooka 22:42, 11 May 2006 (UTC)[reply]

Nowhere. The pseudocode is small and pretty straightforward. So I'll go ahead and remove the implementations. If anyone disagrees, please post here the reason and revert it back. DanielKO 01:35, 12 July 2006 (UTC)[reply]
Hi. I have been going through pages like this and reimplementing the pseudocode in Python. If the end result is easier to understand, as it was in this case, I have replaced the pseudocode with Python. If you think the pseudocode was better, you can go ahead and put it back. Jesin (talk) 02:18, 27 November 2007 (UTC)[reply]
Aloha. Why is the only version now in Java? Unless anyone has any objections, I'll be reverting to the Python/Pseudocode implementation (Probably pseudocode). Wikipedia isn't (usually) the place for specific implementations, but rather for the general version. 212.159.30.215 (talk) 17:07, 22 January 2008 (UTC)[reply]
Hi, I remove some syntax clutter on the pseudocode and simplify it with simpler implementation based on http://dickgrune.com/Programs/gnomesort.html as GnomeSort is meant to be the simplest sorting algorithm. rkokasih

Same as insertion sort?[edit]

Hmm, the optimisation included in the psuedocode (... and not part of the original algorithm I might add) appears to make gnome sort perform identical to insertion sort. Watch it in a visualizer if you don't believe me, I cannot pick the difference between them. =/ ? Themania 17:00, 13 May 2007 (UTC)[reply]

Yes, gnome sort and insertion sort are simply described in a different method, and are completely identical. In my opinion. (Oh, by the way, this is User:Goffrie, too lazy to login.) 4.20.175.132 23:49, 2 July 2007 (UTC)[reply]

they are identical. instead of sequence of swaps with temp insertsort uses only one temp. gnomesort does this a <=> b <=> c <=> until a is in proper place.... insert sort does this temp <= a, a<= b <= c <= .... x <= temp . User:cc.aa.ll 84.16.123.194 19:34, 1 December 2007 (UTC)[reply]

The optimization could be mentioned (though perhaps not, since it seems to be original research). But after optimization it is clearly the same as insertion sort. Therefore the visualization is wrong and should be changed, since the current vizualization is of the optimized version, which means it is just a vizualization of insertion sort. Presumably the whole point of Gnome sort is that this very simple and tiny code (including traversing back up the list, without optimization) can successfully sort - so the vizualization should be a vizualization of that. Bmju (talk) 18:05, 10 July 2021 (UTC)[reply]

@Bmju: There are two important differences between gnome sort and insertion sort:
  • gnome sort has all its work organized with a single loop with a single working index variable while insertion sort is a typical implementation of O(n2) algorithm with two loops and two working indices;
  • gnome sort does its work with simple swaps while insertion sort extracts an item to be moved, shifts items 'till the destination place is freed and inserts the removed item at the free position[1][2][3][4] (although our article on Insertion sort says something different, namely it presents the basic algorithm with unnecessary swaps, and then the normal implementation as its super-duper-optimized version!)
The so-called 'optimization' produces an algorithm which is complicated like insertion sort and slow like gnome sort – that is, which is worse than they both.
BTW, it's not true that after optimization it is clearly the same as insertion sort – at least if you consider the true insertion sort, not a lame swap-based Wikipedia version. --CiaPan (talk) 20:14, 10 July 2021 (UTC)[reply]

References

  1. ^ https://www.geeksforgeeks.org/insertion-sort/
  2. ^ https: //www .tutorialspoint .com/data_structures_algorithms/insertion_sort_algorithm.htm
  3. ^ https://www.programiz.com/dsa/insertion-sort
  4. ^ https://isaaccomputerscience.org/concepts/dsa_search_insertion

Garden Gnome?[edit]

How can a garden gnome, which is not a real thing, have a methodology for sorting flower pots? How could this real algorithm be based on such a fictional algorithm? This does not make very much logical sense. Nimur 07:03, 21 October 2007 (UTC)[reply]

The garden gnome, kabouter in nederlands, is a common childhood story figure in dutch culture. Much as the real Achilles tendon is named after the fictional Achilles heel, so this real algorithm is named after the garden gnome's fictional sorting pattern. Kyle van der Meer (talk) 17:14, 14 July 2009 (UTC)[reply]
Plus, you gotta think about it from a practical standpoint. Traditional depictions of a gnome show it to be about the size of a flower pot anyway, if not a bit larger [1], so it makes sense that something that small would sort things in this way, being unable to move multiple pots at a time. Scale it up to human size with larger planters (large enough to where you would only be able to carry one at a time) and you'd be sorting them in about the same way. ItsMiki (talk) 15:16, 20 October 2014 (UTC)[reply]

References

  1. ^ https://en.wikipedia.org/wiki/Gnome

Python example[edit]

Is it really needed? It is almost the same as the pseudo code.AV-2 (talk) 09:56, 17 March 2008 (UTC)[reply]

I agree that it is quite unnecessary, so I've removed it. It is available on the Wikibooks page though.--CyHawk (talk) 11:20, 25 August 2008 (UTC)[reply]
Pseudocode is so 1970s. Please remove it and keep the Python implementation. 2001:9E8:4627:BB00:FCE2:1F54:C937:3085 (talk) 22:32, 12 April 2024 (UTC)[reply]

This pseudocode is so wrong[edit]

In fact, the index j is never used. It just increases for no reasons. 138.37.84.44 (talk) 10:16, 10 February 2009 (UTC)[reply]

The j is in place to 'remember' where i was when i bring something out of order back along the list. It is indeed needed to jump the i back up the list without rechecking everything. Kyle van der Meer (talk) 17:17, 14 July 2009 (UTC)[reply]
I also think the J in de pseudocode is wrong: even if the algorithm is better now I don't think it is Gnome-sort anymore. Not the same as given in the text anyway.
As a side note: shouldn't pseudocode define an array as A[1..n] instead of A[0..n-1]?
Pukkie (talk) 14:34, 11 August 2009 (UTC)[reply]
I agree, the whole point of this algorithm is to use the gnome story to demonstrate a very simple way to sort. It is not meant to be efficient. The "optimized" example defeats the purpose (unless the gnome can teleport) for no asymptotic gain, so I have replaced it with something closer to the original C example that was cited. Maghnus (talk) 13:27, 31 December 2009 (UTC)[reply]

Removal of the origins of the name[edit]

An anonymous someone keeps removing the paragraphs describing the origin of the name "Gnome Sort" without any explanation. Since another part of the article references it (regarding flower pots), I'm going to assume this is vandalism and continue to re-add it. Lavers (talk) 12:41, 5 July 2011 (UTC)[reply]

I'm not the one removing it, but the naming and discovery information is highly dubious, I've seen this sort being used back in the 80's 217.128.255.181 (talk) 06:12, 24 May 2013 (UTC)[reply]
Added it back in. Would the butthead who is removing it please stop? ItsMiki (talk) 15:17, 20 October 2014 (UTC)[reply]
Someone did it again! Reverted once more. I too was confused on entering the page as to why it's called "gnome sort". — Preceding unsigned comment added by 198.160.103.151 (talk) 16:05, 11 November 2014 (UTC)[reply]
This really needs to be sorted out, one way or another, since random unexplained references to flower pots do little to aid understanding of the topic. 86.147.197.65 (talk) 19:06, 24 June 2018 (UTC)[reply]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Gnome_sort&oldid=1218913450"