Сортировка шейкер в питоне

Cocktail Sort

Cocktail Sort is a variation of Bubble sort. The Bubble sort algorithm always traverses elements from left and moves the largest element to its correct position in the first iteration and second-largest in the second iteration and so on. Cocktail Sort traverses through a given array in both directions alternatively. Cocktail sort does not go through the unnecessary iteration making it efficient for large arrays.

Cocktail sorts break down barriers that limit bubble sorts from being efficient enough on large arrays by not allowing them to go through unnecessary iterations on one specific region (or cluster) before moving onto another section of an array.
Algorithm:
Each iteration of the algorithm is broken up into 2 stages:

1. The first stage loops through the array from left to right, just like the Bubble Sort. During the loop, adjacent items are compared and if the value on the left is greater than the value on the right, then values are swapped. At the end of the first iteration, the largest number will reside at the end of the array.
2. The second stage loops through the array in opposite direction- starting from the item just before the most recently sorted item, and moving back to the start of the array. Here also, adjacent items are compared and are swapped if required.

Let us consider an example array (5 1 4 2 8 0 2)

First Forward Pass:
(5 1 4 2 8 0 2) ? (1 5 4 2 8 0 2), Swap since 5 > 1
(1 5 4 2 8 0 2) ? (1 4 5 2 8 0 2), Swap since 5 > 4
(1 4 5 2 8 0 2) ? (1 4 2 5 8 0 2), Swap since 5 > 2
(1 4 2 5 8 0 2) ? (1 4 2 5 8 0 2)
(1 4 2 5 8 0 2) ? (1 4 2 5 0 8 2), Swap since 8 > 0
(1 4 2 5 0 8 2) ? (1 4 2 5 0 2 8), Swap since 8 > 2
After the first forward pass, the greatest element of the array will be present at the last index of the array.
First Backward Pass:
(1 4 2 5 0 2 8) ? (1 4 2 5 0 2 8)
(1 4 2 5 0 2 8) ? (1 4 2 0 5 2 8), Swap since 5 > 0
(1 4 2 0 5 2 8) ? (1 4 0 2 5 2 8), Swap since 2 > 0
(1 4 0 2 5 2 8) ? (1 0 4 2 5 2 8), Swap since 4 > 0
(1 0 4 2 5 2 8) ? (0 1 4 2 5 2 8), Swap since 1 > 0
After the first backward pass, the smallest element of the array will be present at the first index of the array.
Second Forward Pass:
(0 1 4 2 5 2 8) ? (0 1 4 2 5 2 8)
(0 1 4 2 5 2 8) ? (0 1 2 4 5 2 8), Swap since 4 > 2
(0 1 2 4 5 2 8) ? (0 1 2 4 5 2 8)
(0 1 2 4 5 2 8) ? (0 1 2 4 2 5 8), Swap since 5 > 2
Second Backward Pass:
(0 1 2 4 2 5 8) ? (0 1 2 2 4 5 8), Swap since 4 > 2
Now, the array is already sorted, but our algorithm doesn’t know if it is completed. The algorithm needs to complete this whole pass without any swap to know it is sorted.
(0 1 2 2 4 5 8) ? (0 1 2 2 4 5 8)
(0 1 2 2 4 5 8) ? (0 1 2 2 4 5 8)
Below is the implementation of the above algorithm :

Источник

Книга программиста/Обработка списков на Python

Все программы, код которых выложен здесь, являются работоспособными.

• 1 Сортировки
  • 1.1 Сортировка пузырьком
  • 1.2 Сортировка выбором
  • 1.3 Сортировка вставками
  • 1.4 Шейкерная сортировка
  • 2.1 Строки с максимальным количеством согласных
  • 2.2 Исключение одинаковых элементов списка
  • 2.3 Максимальные элементы столбцов
  • 2.4 Минимальные элементы на пересечении строк и столбцов
  • 2.5 Двузначные числа, кратные 2
  • 2.6 Поменять местами строки двумерного списка
  • 2.7 Совершенные числа
  • 2.8 Сумма чисел многомерного списка

  Сортировки [ править ]

  Сортировка пузырьком [ править ]

  import random N = 10 L = list() for i in range(N): L.append(random.randint(0, 100)) print(L) for j in range(N - 1, 0, -1): for i in range(j): if L[i] > L[i + 1]: L[i], L[i + 1] = L[i + 1], L[i] print(L) 

  Сортировка выбором [ править ]

  import random N = 10 L = list() for i in range(N): L.append(random.randint(0, 100)) print(L) for i in range(N): for j in range(i + 1, N): if L[i] > L[j]: L[i], L[j] = L[j], L[i] print(L) 

  Сортировка вставками [ править ]

  import random N = 10 L = list() for i in range(N): L.append(random.randint(0, 100)) j = i while j > 0 and L[j - 1] > L[j]: L[j - 1], L[j] = L[j], L[j - 1] j -= 1 print(L) 

  Шейкерная сортировка [ править ]

  import random N = 4 L = list() for i in range(N): L.append(random.randint(0, 10)) print('Изначальный список:') print(L) Left = 0 Right = N - 1 while Left  Right: for i in range(Right, Left, -1): if L[i - 1] > L[i]: L[i - 1], L[i] = L[i], L[i - 1] for i in range(Left + 1, Right): if L[i] > L[i + 1]: L[i], L[i + 1] = L[i + 1], L[i] Right -= 1 Left += 1 print('Изменённый список:') print(L) 

  Более сложные задачи [ править ]

  Строки с максимальным количеством согласных [ править ]

  N = 10 Words = list() Count = list() Consonants = set('QWRTPSDFGHJKLZXCVBNM') for i in range(N): Words.append(input()) Count.append(0) for i in range(N): for j in Words[i]: if j.upper() in Consonants: Count[i] += 1 j = 0 Max = Count[0] for i in range(N): if Count[i] > Max: Max = Count[i] j = i print('Слово  содержит максимальное количество согласных: .'.format(Words[j], Count[j])) 

  Исключение одинаковых элементов списка [ править ]

  Exists — список, который хранит булевы значения для указания того, что некоторый i-ый элемент должен быть в списке.

  import random N = 10 L, Exists = list(), list() for i in range(N): L.append(random.randint(0, 10)) Exists.append(True) print('Изначальный список:') print(L) for i in range(N): if Exists[i]: for j in range(i + 1, N): if L[j] == L[i]: Exists[j] = False print('Изменённый список:') for i in range(N): if Exists[i]: print(str(L[i]) + ' ') 

  Максимальные элементы столбцов [ править ]

  import random N = 4 L = [] Max = list() for i in range(N): L.append([]) Max.append(-10000) for j in range(N): L[i].append(random.randint(0, 100)) print('Матрица:') for i in range(N): print(L[i]) for j in range(N): for i in range(N): if L[i][j] > Max[j]: Max[j] = L[i][j] print('Максимумы:') print(Max) 

  Минимальные элементы на пересечении строк и столбцов [ править ]

  import random def Print(l): print('Матрица:') for i in range(len(l)): print(l[i]) N = 4 L = [] for i in range(N): L.append([]) for j in range(N): L[i].append(random.randint(0, 10)) Print(L) MinI = 0 MinJ = 0 Min = 0 Found = False for i in range(N): Min = 10000 Found = True for j in range(N): if L[i][j]  Min: Min = L[i][j] MinI = i MinJ = j for i2 in range(N): if L[i2][MinJ]  Min: Found = False if Found: break if not Found: print('Минимального элемента на пересечении строк и столбцов не найдено.') else: print('Индексы минимального элемента  равны [ , ].'.format(Min, MinI, MinJ)) 

  Двузначные числа, кратные 2 [ править ]

  import math, random def Print(l): print('Матрица:') for i in range(len(l)): print(l[i]) N = 4 L = [] for i in range(N): L.append([]) for j in range(N): L[i].append(random.randint(0, 100)) Print(L) C = 0 for i in range(N): for j in range(N): if (math.fabs(L[i][j]) >= 10) and (math.fabs(L[i][j])  100) and ((s//2 + s%2)%2 == 0): C += 1 print('Количество двузначных чисел с четной суммой цифр равно .'.format(C)) 

  Поменять местами строки двумерного списка [ править ]

  import random def Print(l): print('Матрица:') for i in range(len(l)): print(l[i]) N = 4 L = [] for i in range(N): L.append([]) for j in range(N): L[i].append(random.randint(0, 100)) Print(L) N2 = N - 1 i1 = random.randint(0, N2) i2 = random.randint(0, N2) for j in range(N): L[i1][j], L[i2][j] = L[i2][j], L[i1][j] Print(L) 

  Совершенные числа [ править ]

  L = list() for a in range(1, 1001): S = 0 for k in range(1, a): if a%k == 0: S += k if S == a: L.append(a) print(L) 

  Сумма чисел многомерного списка [ править ]

  def Sum(a): if type(a) is int: return a else: result = 0 for b in a: result += Sum(b) return result L = [[1, 2], 3, [4, [5, 6]], 7, [8]] print(Sum(L)) 

  Источник

  Шейкерная сортировка

  Сортировка перемешиванием (cocktail sort, shaker sort), или шейкерная сортировка – это усовершенствованная разновидность сортировки пузырьком, при которой сортировка производиться в двух направлениях, меняя направление при каждом проходе.

  Описание алгоритма шейкерной сортировки

  Проанализировав алгоритм пузырьковой сортировки, можно заметить:

  • если при обходе части массива не было обменов элементов, то эту часть можно исключить, так как она уже отсортирована;
  • при проходе от конца массива к началу минимальное значение сдвигается на первую позицию, при этом максимальный элемент перемещается только на один индекс вправо.

  Исходя из приведенных идей, модифицируем сортировку пузырьком следующим образом:

  • на каждой итерации, фиксируем границы части массива в которой происходит обмен;
  • массив обходиться поочередно от начала массива к концу и от конца к началу;

  При этом минимальный элемент перемещается в начало массива, а максимальный — в конец, после этого уменьшается рабочая область массива.

  Реализация шейкерной сортировки

  def shaker_sort(array): length = len(array) swapped = True start_index = 0 end_index = length - 1 while (swapped == True): swapped = False # проход слева направо for i in range(start_index, end_index): if (array[i] > array[i + 1]) : # обмен элементов array[i], array[i + 1] = array[i + 1], array[i] swapped = True # если не было обменов прерываем цикл if (not(swapped)): break swapped = False end_index = end_index - 1 #проход справа налево for i in range(end_index - 1, start_index - 1, -1): if (array[i] > array[i + 1]): # обмен элементов array[i], array[i + 1] = array[i + 1], array[i] swapped = True start_index = start_index + 1 print("Шейкерная сортировка") arr = [] length = int(input("Введите длину массива: ")) for i in range(0, length): element = int(input("arr[" + str(i + 1) + "] hljs-string">"Отсортированный массив: ") print(arr) 

  Результат работы программы:

  Источник