You get a bonus - 1 coin for daily activity. Now you have 1 coin

Dwarf sort

Lecture



Dwarven sorting was first proposed on October 2, 2000 by Hamid Sarbazi-Azad. He called it "Stupid sorting, the simplest sorting algorithm with only one cycle ...". Indeed, this method is stupid or not, but is involved in it, in no way in most sorts - two or more cycles, but only one. Later, the Dutch scientist Dick Grun, in the pages of one of his books, gave the following analogy for the dwarf sort.

Dwarf sort Dutch Garden Gnome (Du .: tuinkabouter). Here is a garden of flower pots. He and the previous one; If you are a potter, you may want to take a pot backwards. Boundary conditions: if there are no steps, he steps forwards; if there is no pot next to him, he is done.

Transfer:

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

So described the main idea of ​​the algorithm of the dwarf sort Dick Grun. Replace the gnome and pots with more formal objects, such as a pointer (the number of the current element) and elements of the array, and consider the principle of the algorithm once again. First, the pointer is placed on the 2nd element of the array (in C ++ it has the number 1, and in Pascal the number 2). Then, two neighboring elements A [i] and A [i-1] are compared, that is, the first element (i-1) and the second (i) are compared. If they are in their positions, then move the pointer to the position i + 1 and continue the comparison from the new position; otherwise, we change elements in places, and, since at some point it may turn out that elements in the left subarray are not in their places, we move the pointer one position to the left, making the following comparison with the new position. So the algorithm continues to run until the entire array is ordered. Here we should highlight two important points. First, the ordering process ends, then when the condition i

Let's go over to the code itself. Dick Grun posted the following listing on his website:

one
2
3
four
five
6
7
eight
void gnomesort (int n, int ar [])
{
int i = 0;
while (i 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 Gruno allows you to organize the array, but it can still be slightly improved. Optimization will require some editing, in particular, the addition of one auxiliary variable, which will eliminate unnecessary comparisons. The following shows the listings of programs that sort the elements of an array in ascending order.

C ++ program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty
31
32
33
#include "stdafx.h"
#include
using namespace std;
int n;
void Gnome_sort (int i, int j, int * mas)
{
while (i {
if (mas [i-1] <= mas [i]) {i = j; j ++; }
else
{
int t = mas [i];
mas [i] = mas [i-1]; mas [i-1] = t;
i--;
if (i == 0) {i = j; j ++; }
}}
cout << "Sorted array:";
for (i = 0; i cout << mas [i] << "";
}
void main ()
{
setlocale (LC_ALL, "Rus");
int m, k;
cout << "Array size>"; cin >> n;
int * a = new int [n];
for (k = 0; k {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");
}

Pascal program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty
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 <= n do
begin
if mas [i-1] <= mas [i] then begin i: = j; j: = j + 1; end
else
begin
t: = mas [i];
mas [i]: = mas [i-1]; mas [i-1]: = t;
i: = i-1;
if i = 1 then begin i: = j; j: = j + 1; end;
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 sorting}
readkey;
end.

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

Dwarf sort

Sort Inserts

Worst case

O (n 2 )

O (n 2 )

Best case

O (n)

O (n)

Average case

O (n 2 )

O (n 2 )

created: 2014-11-30
updated: 2021-03-28
133422



Rating 9 of 10. count vote: 2
Are you satisfied?:



Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms