Shaker (mixing) sorting

Lecture



The algorithm considered in this article has several dissimilar names. Among them: sorting by mixing, bidirectional bubble sorting, shaker sorting, pulsating sorting (ripple sort), transfer sorting (shuttle sort), and even happy hour sort sorting. The second option (bidirectional bubble sort) most accurately describes the process of the algorithm. Here, in its name, the term "bubbly" is quite successfully included. This is really an alternative version of the well-known method, the modifications of which consist, for the most part, in the implementation mentioned in the title, bidirectionality: the algorithm moves, neither as in exchange (bubble) sorting - strictly from bottom to top (left to right), and first from bottom to top, then from top to bottom.

Shaker (mixing) sorting

The permutation of the elements in the shaker sorting is performed in the same way as in the bubble sorting, i.e., two adjacent elements, if necessary, are swapped. Let the array be ordered in ascending order. Denote each path traveled from the beginning to the end of the sequence by W i , where i is the path number; and the return path (from the end to the beginning) is through -W j , where j is the path number. Then after performing W i , one of the uninstalled elements will be placed in the position on the right, as the largest of the still unsorted elements, and after the execution of -W j , the smallest of the unsorted elements will move to some position on the left. So, for example, after executing W 1 at the end of the array, there will be an element having the largest value, and after -W 1 , the element with the smallest value will go to the beginning.

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
34
35
36
37
38
39
40
41
#include "stdafx.h"
#include <iostream>
using namespace std;
// exchange function
void Swap (int * Mas, int i)
{
int temp;
temp = mas [i];
Mas [i] = Mas [i-1];
Mas [i-1] = temp;
}
// shaker sort function
void ShakerSort (int * Mas, int Start, int N)
{
int Left, Right, i;
Left = Start;
Right = N-1;
while (Left <= Right)
{
for (i = Right; i> = Left; i--)
if (Mas [i-1]> Mas [i]) Swap (Mas, i);
Left ++;
for (i = Left; i <= Right; i ++)
if (Mas [i-1]> Mas [i]) Swap (Mas, i);
Right--;
}
}
// main function
void main ()
{
setlocale (LC_ALL, "Rus");
int n, k;
cout << "Array size>"; cin >> n;
int * A = new int [n];
for (k = 0; k <n; k ++)
{cout << k + 1 << "element>"; cin >> A [k]; }
ShakerSort (A, 1, n);
cout << "Result array:";
for (k = 0; k <n; k ++) cout << "" << A [k];
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
34
35
36
37
38
39
40
41
42
43
44
program CocktailSort;
uses crt;
type Massiv = array [1..100] of integer;
var
n, k: integer;
A: Massiv;
{shaker sorting procedure}
procedure ShakerSort (Mas: Massiv; Start, m: integer);
var Left, Right, temp, i: integer;
begin
Left: = Start;
Right: = m;
while Left <= Right do
begin
for i: = Right downto Left do
if (Mas [i-1]> Mas [i]) then
begin
temp: = mas [i];
Mas [i]: = Mas [i-1];
Mas [i-1]: = temp;
end;
Left: = Left + 1;
for i: = Left to Right do
if Mas [i-1]> Mas [i] then
begin
temp: = mas [i];
Mas [i]: = Mas [i-1];
Mas [i-1]: = temp;
end;
Right: = Right-1;
end;
for i: = 1 to M do write (', Mas [i]);
end;
{main program block}
begin
clrscr;
write ('array size>'); read (n);
for k: = 1 to n do
begin
write (k, 'element>'); read (a [k]);
end;
write ('Resulting array:');
ShakerSort (A, 2, n);
end.

The following table shows the time complexity of the shaker sorting algorithm for the three cases.

Best case

Average case

Worst case

O (n)

O (n 2 )

O (n 2 )

These temporary indicators do not allow recommending an algorithm for its practical use. In teaching, due to its relative complexity, the method will undoubtedly be useful.

created: 2014-11-30
updated: 2021-03-13
132905

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