Gnome sort: Difference between revisions
Content deleted Content added
TakuyaMurata (talk | contribs) remove Java code; sorry but it looks superficial. Both Java and Python are imperative languages and both of the code look almost identical |
No edit summary |
||
| Line 1: | Line 1: | ||
'''Gnome sort''' is a [[sort algorithm]] which is similar to [[insertion sort]] except that moving an element to its proper place is accomplished by a series of swaps, as in [[bubble sort]]. The name comes from the supposed behavior of the Dutch garden gnome in sorting a line of flowerpots. |
|||
A true beginner's sorting algorithm, requiring no nested loops. Experimentally has an average case running time of <i>n</i><sup>2</sup>, with a slightly higher constant than [[Bubble sort]]. [[Python programming language|Python]] code follows: |
|||
It is conceptually simple, requiring no nested loops. The running time is [[Big O notation|O]](<i>n</i><sup>2</sup>), and the constant has been reported to be slightly higher than [[Bubble sort]] (although this would depend on the details of the architecture and the implementation). [[Python programming language|Python]] code follows: |
|||
<pre> |
<pre> |
||
| Line 13: | Line 14: | ||
</pre> |
</pre> |
||
==External link== |
|||
* [http://www.cs.vu.nl/~dick/gnomesort.html Gnome sort]. |
|||
Revision as of 08:26, 30 March 2004
Gnome sort is a sort algorithm which is similar to insertion sort except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. The name comes from the supposed behavior of the Dutch garden gnome in sorting a line of flowerpots. It is conceptually simple, requiring no nested loops. The running time is O(n2), and the constant has been reported to be slightly higher than Bubble sort (although this would depend on the details of the architecture and the implementation). Python code follows:
def GnomeSort(l):
i = 0
while (i < len(l)):
if i == 0 or l[i - 1] <= l[i]:
i += 1
else:
l[i], l[i - 1] = l[i - 1], l[i]
i -= 1
return l