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.
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.
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"); } |
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.
Comments
To leave a comment
Algorithms
Terms: Algorithms