Having considered “bubble” sorting array can proceed to analyze its variations – “Shaker”-sorting. You can meet some of her titles : sorting mixing, throbbing sorting, bi-directional sorting “bubble”.
After looking carefully to, how the sorting “bubble” – You can say the following: part of the array, in which the elements of the permutation is not already occurring (sorted part of the array), then this could be excluded from consideration and do not handle the following iterations. Second, you may have noticed – It `s that, that the minimum (most “easy” element) when sorting, immediately moved to the very beginning of the array, and “heavy” elements are shifted one position only “down”. So array
will be sorted in one pass nested loop, and for the array
you will need three iterations.
Therefore, a more effective form of the sort was invented “bubble” -“Shaker”-sorting. It limits the part of an array that has a permutation, constrict. A plus – inner loops pass through the array in one direction, the other side, raising the lightest element up and dropping the heaviest element in the bottom of one iteration of the outer loop. Dial code:
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include <iostream> using namespace std; //ф-ция для обмена значений ячеек void swapEl(int *arr, int i) { int buff; buff = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = buff; } //ф-ция "шейкер"-сортировки void myShakerSort(int *arr, int size) { int leftMark = 1; int rightMark = size - 1; while (leftMark <= rightMark) { for (int i = rightMark; i >= leftMark; i--) if (arr[i - 1] > arr[i]) swapEl(arr, i); leftMark++; for (int i = leftMark; i <= rightMark; i++) if (arr[i - 1] > arr[i]) swapEl(arr, i); rightMark--; cout << "\nИтерация: " << leftMark - 1; // просмотр количества итераций } } int main() { setlocale(LC_ALL, "rus"); int size = 0; cout << "Размер массива: "; cin >> size; int *A = new int[size]; for (int k = 0; k < size; k++) { A[k] = size - k; // запись значений по убыванию cout << A[k] << " | "; } myShakerSort(A, size); // сортировка cout << "\nМассив после сортировки:\n"; for (int k = 0; k < size; k++) { cout << A[k] << " | "; } cout << endl; return 0; } |
Consider the function in which it is “Shaker”-sorting (bi-directional sorting “bubble”) – strings 14-31. Due to the variable leftMark and rightMark array section, which is to be sorted will shrink with each step of the loop. This has a positive impact on the time of the program. And thanks to two nested loops for – in one iteration of the outer loop minimum and maximum values take their rightful positions in the array.
Result:
As mentioned, on the execution of the sort array ASC took half of the outer loop iterations, compared with the classical “bubble” sorting.
Read also about other algorithms for sorting data.
Why in the condition while (leftMark <= rightMark) (string 18) check equality? Indeed, in the case of equality of the left and right borders remain 1 element, and passing unnecessary iteration it is not necessary for.
The shake sorting efficiently? – so that in a single iteration of the outer loop, not only the smallest element moves downwards, and most – up? – duck but iteration itself has become more difficult.
That is. In the worst case of bubble sort was N iterations of the outer loop, each of which performs N-i iterations of the internal (where i – number of outer loop iteration). That is. the difficulty is calculated as the sum of (N-i) for all i from 1 до N, i.e.. N * (N+1)/2 = 0.5*N^2 + 0.5*N. Asymptotically – is N ^ 2, but I write this formula, tk. more accurate (It may be so in the shaker at least some advantage will?)
In the worst case, the shake of sorting will be executed N / 2 iterations of the outer loop (because for one iteration 2 element take their places in a sorted array), but the inner loop has difficulty (N-i) * 2. Difficulty sorting – is the sum (N-i)*2 for all i from 1 до N/2. Again, we see the arithmetic progression and consider the amount of a
N * ((N-1) + (N, N / 2))/2 = N * (N-1 + N – N/2)/2 = (1.5*N * N, N)/2 = 0.75*N^2 – N/2.
Duck here, even if we ignore the analysis for N tends to infinity (where sorting equivalents efficiency), obviously the same, that for small values of N “optimized” the algorithm will work worse (at least in the worst case).
Where am I now wrongly considered? – I never understood all these dancing with shaker.
Shake sorts almost sorted array in O(n)
In the code, a memory leak
shtrafnie = [6, 10, 3, 5, 8]
link_shtraf = {
6: ["Karelyn", 'Alexander', 'Russian team', ‘Classic style wrestling’, ’10’],
10: ['Popov', 'Alexander', ‘Olympic team’, 'Swimming', ’15’],
3: [‘Ishchenko’, 'Natalia', ‘Olympic team’, 'Synchronized swimming', ’13’],
5: ["Sharapova", 'Maria', '-No-', 'tennis', ’10’],
8: ['Arshavin', 'Andrey', "Arsenal", 'Football', ’10’]
}
def insertion(data):
for i in range(len(data)):
j = i – 1
key = data[i]
while data[j] > key and j >= 0:
data[j + 1] = data[j]
j -= 1
data[j + 1] = key
return data
def shaker_sort(array):
length = len(array)
swapped = True
start_index = 0
end_index = length – 1
while (swapped == True):
swapped = False
# passage from left to right
for i in range(start_index, end_index):
if (array[i] > array[i + 1]) :
# exchange of elements
array[i], array[i + 1] = array[i + 1], array[i]
swapped = True
# if there were no exchanges, interrupt the cycle
if (not(swapped)):
break
swapped = False
end_index = end_index – 1
#passage from right to left
for i in range(end_index – 1, start_index – 1, -1):
if (array[i] > array[i + 1]):
# exchange of elements
array[i], array[i + 1] = array[i + 1], array[i]
swapped = True
start_index = start_index + 1
return array
for i in shtrafnie:
print(f'Surname: {link_shtraf[i][0]}, Имя: {link_shtraf[i][1]}, Team: {link_shtraf[i][2]}, Kind of sport: {link_shtraf[i][3]}, Test result: {link_shtraf[i][4]}’)
insertion(shtrafnie)
print(‘—–Simple insertion sort—–‘)
for i in shtrafnie:
print(f'Surname: {link_shtraf[i][0]}, Имя: {link_shtraf[i][1]}, Team: {link_shtraf[i][2]}, Kind of sport: {link_shtraf[i][3]}, Test result: {link_shtraf[i][4]}’)
print(‘—–Sorting Shaker by sorting—–‘)
shaker_sort(shtrafnie)
for i in shtrafnie:
print(f'Surname: {link_shtraf[i][0]}, Имя: {link_shtraf[i][1]}, Team: {link_shtraf[i][2]}, Kind of sport: {link_shtraf[i][3]}, Test result: {link_shtraf[i][4]}’)