Last Updated:

Gnome sorting

Dwarven sorting was first proposed on October 2, 2000 by Hamid Sarbazi-Azad. He called it "Stupid sorting, the simplest sorting algorithm with just one cycle...". And indeed, whether this method is stupid or not, but it involves, in most sortings - two or more cycles, but only one. Later, the Dutch scientist Dick Groen, in the pages of one of his books, gave the following analogy for gnome sorting.

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter). Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

 

"Dwarven sorting" is based on a technique used by an ordinary Dutch garden gnome. Here's how a garden gnome sorts a row of flower pots. Essentially, he looks at two adjacent flower pots, if they are in the correct order, then he moves one pot forward, otherwise he swaps them and goes back one pot. Boundary conditions: if there is not a single pot behind, he steps forward, and if there is no next pot, then he is finished.

 

This is how Dick Groen described the basic idea of the gnome sorting algorithm. Let's replace the gnome and pots with more formal objects, such as the pointer (the number of the current element) and the elements of the array, and consider the principle of the algorithm again. First, the pointer is placed on the 2nd element of the array (in C++ it has the number 1, and in Pascal number 2).

Then there is a comparison of two adjacent elements A[i] and A[i-1], i.e. the first element (i-1) and the second (i) are compared. If they are standing on their positions, then move the pointer to the position i + 1 and continue the comparison with the new position; otherwise, we swap the elements, and since at some point it may turn out that the elements in the left submassive are out of place, move the pointer one position to the left, making the next comparison with the new position. So the algorithm continues to execute until the entire array is ordered.

Two important points should be highlighted here.

First, the ordering process ends when the condition i<n, where n is the size of the array, is not met.

Secondly, as mentioned, the pointer moves both forward in the list and backward, and in the event that it is above the first element, it should immediately be moved one position to the right, because otherwise you will have to compare two elements, one of which does not exist.

Let's move on to the code itself. On his website, Dick Groene posted the following listing:

1
2
3
4
5
6
7
8
void gnomesort(int n, int ar[])
{
int i = 0;
while (i < n) {
if (i == 0 || ar[i-1] <= ar[i]) i++;
else {int tmp = ar[i]; ar[i] = ar[i-1]; ar[—i] = tmp;}

}
}

The code given by Grun allows you to arrange the array, but it can still be slightly improved. Optimization will require a little editing, in particular, the addition of one auxiliary variable, which will get rid of unnecessary comparisons. The following are listings of programs that sort the elements of an array in ascending order.

The code of the program in C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include "stdafx.h"
#include <iostream>
using namespace std;
int n;
void Gnome_sort(int i, int j, int *mas)
{
while (i<n)
{
if (mas[i1]<=mas[i]) { i =j; j++; }
else
{
int t=mas[i];
mas[i]=mas[i1]; mas[i1]=t;
i;
if (i==0) { i=j; j++; }
}}
cout<< "Sorted array: ";
for (i=0; i<n; i++) output of
the cout<<mas[i]<< array";
}
void main()
{
setlocale(LC_ALL,«Rus»);
int m, k;
cout<< Array Size >"; cin>>n;
int *a=new int[n];
for (k=0; k<n; k++) entering an array
{ cout<<k+1<<" element > "; cin>>a[k]; }
k=1; m=2;
Gnome_sort(k, m, a); call the
sort function delete []a;
system(«pause>>void»
);
}

The code of the program in Pascal:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
program Gnome_sort;
uses crt;
type massiv=array[1.. 100] of integer;
var k, m, n: integer;
a: massiv;
procedure PGnome_sort(i, j: integer; mas: massiv);
var t: integer;
begin
while i<=do
begin
if mas[i1]<=mas[i] then begin i:=j; j:=j+1end
else
begin
t:=mas[i];
mas[i]:=mas[i1]; mas[i1]:=t;
i:=i1;
if i=1 then begin i:=j; j:=j+1end;
end;
end;
write('Sorted array: ');
for i:=1 to n do write(mas[i], ‘ ‘){array output}
end;
begin
clrscr;
write('Array size > ')read(n);
for k:=1 to n do {array input}
begin
write(k, ' element > ')read(a[k]);
end;
k:=2; m:=3;
PGnome_sort(k, m, a){call to sort}
readkey;
end.

It seems a bit unusual, the fact that the sorting algorithm uses only one cycle. Plus, in practice, dwarven sorting is not inferior in the speed of sorting by inserts, as can be seen from the table of three cases of these sorts.

 

Gnome sorting

Sort by inserts

Worst case scenario

O(n2)

O(n2)

 

Best Case

O(n)

O(n)

Average case

O(n2)

O(n2)