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

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

Она же сортировка перемешиванием, она же коктейльная сортировка. Начинается процесс как в «пузырьке»: выдавливаем максимум на самые задворки. После этого разворачиваемся на 180° и идём в обратную сторону, при этом уже перекатывая в начало не максимум, а минимум. Отсортировав в массиве первый и последний элементы, снова делаем кульбит. Обойдя туда-обратно несколько раз, в итоге заканчиваем процесс, оказавшись в середине списка.
Шейкерная сортировка работает немного быстрее чем пузырьковая, поскольку по массиву в нужных направлениях попеременно мигрируют и максимумы и минимумы. Улучшения, как говорится, налицо.

Как видите, если к процессу перебора подойти творчески, то выталкивание тяжёлых (лёгких) элементов к концам массива происходит быстрее. Поэтому умельцы предложили для обхода списка ещё одну нестандартную «дорожную карту».

Реализация

Сортировка массивов

Быстрая сортировка является естественным рекурсивным алгоритмом — разделите входной массив на меньшие массивы, переместите элементы в нужную сторону оси и повторите.

При этом мы будем использовать две функции — partition() и quick_sort().

Давайте начнем с функции partition():

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array <= array:
            pivot += 1
            array, array = array, array
    array, array = array, array
    return pivot

И, наконец, давайте реализуем функцию quick_sort():

def quick_sort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

После того, как обе функции реализованы, мы можем запустить quick_sort():

array = 

quick_sort(array)
print(array)

Результат:

Поскольку алгоритм unstable (нестабилен), нет никакой гарантии, что два 19 будут всегда в этом порядке друг за другом. Хотя это ничего не значит для массива целых чисел.

Оптимизация быстрой сортировки

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

Однако быстрая сортировка может иметь очень глубокий рекурсивный стек вызовов, если нам особенно не повезло в выборе опорного элемента, а распараллеливание будет не так эффективно, как в случае сортировки слиянием.

Для сортировки небольших массивов рекомендуется использовать простой нерекурсивный алгоритм. Даже что-то простое, например сортировка вставкой, будет более эффективным для небольших массивов, чем быстрая сортировка. Поэтому в идеале мы могли бы проверить, имеет ли наш подмассив лишь небольшое количество элементов (большинство рекомендаций говорят о 10 или менее значений), и если да, то мы бы отсортировали его с помощью Insertion Sort (сортировка вставкой).

Как создать пузырьковую сортировку

Вот что нам придется делать для создания пузырьковой сортировки:

• Создать два цикла , чтобы проходить по всем элементам массива раз ( это размер массива).
• Сравнивать ячейки массива, с помощью оператора ветвления .
• Менять местами значения ячеек.

В примере ниже мы предложили пользователю заполнить массив, который мы дальше отсортируем используя пузырьковую сортировку.

#include <iostream>

using namespace std;

int main() {
setlocale(LC_ALL, «rus»);

int digitals; // объявили массив на 10 ячеек

cout << «Введите 10 чисел для заполнения массива: » << endl;

for (int i = 0; i < 10; i++) {
cin >> digitals; // «читаем» элементы в массив
}

for (int i = 0; i < 10; i++) {
for (int j = 0; j < 9; j++) {
if (digitals > digitals) {
int b = digitals; // создали дополнительную переменную
digitals = digitals; // меняем местами
digitals = b; // значения элементов
}
}
}

cout << «Массив в отсортированном виде: «;

for (int i = 0; i < 10; i++) {
cout << digitals << » «; // выводим элементы массива
}
system(«pause»);
return 0;
}

Давайте поподробнее разберем строки 16 — 24 (здесь находится пузырьковая сортировка)

1. В строке 16: мы создали первый цикл .
2. В строке 17: аналогично был создан второй, но уже вложенный цикл.
3. В строке 18: происходит сравнивание двух элементов.
   • Если  результат этого условия положительный, то мы меняем значение элементов.
   • Если же результат отрицателен, то мы пропускаем этап смены значений.
4. В строке 19: создали переменную , чтобы менять значения ячеек и местами.

Давайте посмотрим, что выведет программа выше при запуске:

sort_puzerek.cpp

Введите 10 чисел для заполнения массива:
5 3 6 2 7 0 2 8 9 10

Массив в отсортированном виде: 0 2 2 3 5 6 7 8 9 10
Process returned 0 (0x0) execution time : 0.005 s
Press any key to continue.

Подробный разбор пузырьковой сортировки

Давайте разберем подробно как работает пузырьковая сортировка

Первая итереация (первый повтор алгоритма) меняет между собой 4 и 2 так как цифра два меньше чем четыре 2<4, повторюсь что алгоритм меняет значения между собой если, слева оно меньше чем справа. Далее происходит сверка между 4 и 3, и так как 3 меньше чем 4 (3<4) происходит обмен значениями. Потом проходит проверку между 4 и 8 и так как значение 4 меньше чем 8 то не происходит обмена, ведь уже и так всё на своих местах.

Далее сравнивается 8 и 1 и так как 1 меньше чем 8 (1<8) и оно не находиться слева то происходит обмен значениями.После это первый повтор алгоритма заканчивается, на анимации я выделил это зеленым фоном.

В итоге по окончанию работы алгоритма пузырьковой сортировки мы имеем следующий порядок числового массива: 2 3 4 1 8

и начинается второй повтор алгоритма.

Далее сравнивается 2 и 3 и так как два меньше чем три и оно находиться слева то просто идем дальше ничего не трогая. Также проверяем и 3 и 4 и тоже самое условие выполняется 3<4 и оно слева. Дальше проверяется 4 и 1 и тут мы видим что число 1<4 и не находиться слева, поэтому алгоритм меняет их местами. В крайний раз для второго повторения алгоритма проверяется 4 и 8, но тут всё в порядке, и мы дошли до конца начинаем третье повторение. Итоги для второго повторения такие : 2 3 1 4 8

Третье повторение пузырькового алгоритма начинается с сравнения 2 и 3, тут алгоритм проверяет что 2<3 и 2 находиться слева и оставляет их в покое и идет дальше. Сравнение же 3 и 1 показывает что 1 то меньше чем три, но почему то не слева и меняет их местами. Далее идет сравнение 3 и 4, тут всё в порядке и так далее до сравнения 4 и 8.

После этого получается следующий результат: 2 1 3 4 8

Как мы видим почти все цифры уже на своих местах и в порядке возрастания! Осталось только в последнем повторении пузырькового алгоритма поменять местами 2 и 1 и всё. После того как алгоритм закончил свою работу и проверил что цифры больше нельзя поменять местами он перестает работать с таким вот результатом: 1 2 3 4 8

Таблица 2: Сортировка пузырьком в многопоточном режиме

Как работает Быстрая сортировка

Быстрая сортировка чаще всего не сможет разделить массив на равные части. Это потому, что весь процесс зависит от того, как мы выбираем опорный элемент. Нам нужно выбрать опору так, чтобы она была примерно больше половины элементов и, следовательно, примерно меньше, чем другая половина элементов. Каким бы интуитивным ни казался этот процесс, это очень сложно сделать.

Подумайте об этом на мгновение — как бы вы выбрали адекватную опору для вашего массива? В истории быстрой сортировки было представлено много идей о том, как выбрать центральную точку — случайный выбор элемента, который не работает из-за того, что «дорогой» выбор случайного элемента не гарантирует хорошего выбора центральной точки; выбор элемента из середины; выбор медианы первого, среднего и последнего элемента; и еще более сложные рекурсивные формулы.

Самый простой подход — просто выбрать первый (или последний) элемент. По иронии судьбы, это приводит к быстрой сортировке на уже отсортированных (или почти отсортированных) массивах.

Именно так большинство людей выбирают реализацию быстрой сортировки, и, так как это просто и этот способ выбора опоры является очень эффективной операцией, и это именно то, что мы будем делать.

Теперь, когда мы выбрали опорный элемент — что нам с ним делать? Опять же, есть несколько способов сделать само разбиение. У нас будет «указатель» на нашу опору, указатель на «меньшие» элементы и указатель на «более крупные» элементы.

Цель состоит в том, чтобы переместить элементы так, чтобы все элементы, меньшие, чем опора, находились слева от него, а все более крупные элементы были справа от него. Меньшие и большие элементы не обязательно будут отсортированы, мы просто хотим, чтобы они находились на правильной стороне оси. Затем мы рекурсивно проходим левую и правую сторону оси.

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

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)

Выберем первый элемент как опору 29), а указатель на меньшие элементы (называемый «low») будет следующим элементом, указатель на более крупные элементы (называемый «high») станем последний элемент в списке.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

Мы двигаемся в сторону high то есть влево, пока не найдем значение, которое ниже нашего опорного элемента.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

• Теперь, когда наш элемент high указывает на элемент 21, то есть на значение меньше чем опорное значение, мы хотим найти значение в начале массива, с которым мы можем поменять его местами. Нет смысла менять местами значение, которое меньше, чем опорное значение, поэтому, если low указывает на меньший элемент, мы пытаемся найти тот, который будет больше.
• Мы перемещаем переменную low вправо, пока не найдем элемент больше, чем опорное значение. К счастью, low уже имеет значение 89.
• Мы меняем местами low и high:

29 | 21 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (high),44

• Сразу после этого мы перемещает high влево и low вправо (поскольку 21 и 89 теперь на своих местах)
• Опять же, мы двигаемся high влево, пока не достигнем значения, меньшего, чем опорное значение, и мы сразу находим — 12
• Теперь мы ищем значение больше, чем опорное значение, двигая low вправо, и находим такое значение 41

Этот процесс продолжается до тех пор, пока указатели low и high наконец не встретятся в одном элементе:

29 | 21,27,12,19,28 (low/high),44,78,87,66,31,76,58,88,83,97,41,99,44

Мы больше не используем это опорное значение, поэтому остается только поменять опорную точку и high, и мы закончили с этим рекурсивным шагом:

28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44

Как видите, мы достигли того, что все значения, меньшие 29, теперь слева от 29, а все значения больше 29 справа.

Затем алгоритм делает то же самое для коллекции 28,21,27,12,19 (левая сторона) и 44,78,87,66,31,76,58,88,83,97,41,99,44 (правая сторона). И так далее.

Алгоритмы сортировки на собеседовании

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

На самом деле, программисты просто гуглят необходимую реализацию. Конечно, они имеют представление о принципах их работы, потому что в своё время рассмотрели несколько алгоритмов, как, например, сортировка пузырьком.

Кроме того, в Python и других языках программирования существуют встроенные функции, которые производят сортировку быстро и эффективно.

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

• Уметь классифицировать алгоритмы сортировки.
• Знать преимущества и недостатки популярных алгоритмов, чтобы понимать, когда каждый из них лучше использовать.
• Понимать, что такое сложность алгоритма и как с её помощью определять, подходит ли он для решения данной задачи.

Пузырьковая сортировка

Или сортировка простыми обменами. Бессмертная классика жанра. Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.
Если не только в конец задвигать максимумы, а ещё и в начало перебрасывать минимумы то у нас получается…

Поиск в массиве

• Используем цикл while:

1
2
3
4
5
6
7
8
9
10
11
12

import random # подключение библиотеки
from random import randint 
n=10; x=5
mas = randint(1,10) for i in range(n) # инициализируем массив
 
i = 
while i < n and masi != x: # если элемент не равен
      i += 1
if i < n:
      print ( "mas=", x, sep = "" )
else:
      print ( "Не нашли!" )

Используем цикл for:

1
2
3
4
5
6
7
8
9
10
11
12
13

import random
from random import randint 
n=10;x=5
mas = randint(1,10) for i in range(n)
 
for i in range (n):
     if masi == x:
             nomer = i
             break
if nomer >= :
     print ( "mas=", x, sep = "" )
else:
     print ( "Не нашли!" )

В данном случае в переменной nomer сохраняется номер элемента массива с найденным значением.

Поэтому рассмотрим второй способ поиска, более простой:

1
2
3
4
5
6
7
8
9
10
11
12
13

import random
from random import randint 
n=10;x=5
mas = randint(1,10) for i in range(n)
 
nomer = -1
for i in range (n):
     if masi == x:
             print ( "mas=", x, sep = "" )
             break
 
else:
     print ( "Не нашли!" )

Задание Python 7_1:
Дан массив. Необходимо подтвердить, что в массиве есть числа, кратные трем.

Задание Python 7_2:
Заполните массив случайными числами в диапазоне 0..4 и выведите на экран номера всех элементов, равных значению X (оно вводится с клавиатуры).

Модификации[править]

Сортировка чет-нечетправить

Сортировка чет-нечет (англ. odd-even sort) — модификация пузырьковой сортировки, основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность — .
Псевдокод указан ниже:

function oddEvenSort(a):
  for i = 0 to n - 1 
    if i mod 2 == 0
      for j = 2 to n - 1 step 2
        if a < a
          swap(a, a)  
    else      
      for j = 1 to n - 1 step 2
        if a < a
          swap(a, a)

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

Сортировка расческойправить

Сортировка расческой (англ. comb sort) — модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность — , но стремится к . Является самой быстрой квадратичной сортировкой. Недостаток — она неустойчива. Псевдокод указан ниже:

function combSort(a):
  k = 1.3
  jump = n
  bool swapped = true
  while jump > 1 and swapped
    if jump > 1
      jump /= k
    swapped = false
    for i = 0 to size - jump - 1
      if a < a
        swap(a, a)
        swapped = true

Пояснения: Изначально расстояние между сравниваемыми элементами равно , где — оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.

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

Сортировка перемешиванием (англ. cocktail sort), также известная как Шейкерная сортировка — разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность — , но стремится она к , где — максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:

function shakerSort(a):
  begin = -1
  end = n - 2
  while swapped
    swapped = false   
    begin++
    for i = begin to end 
      if a > a 
        swap(a, a)
        swapped = true    
    if !swapped
      break    
    swapped = false 
    end--
    for i = end downto begin
      if a > a 
        swap(a, a)
        swapped = true

Сортировка посредством выбора

Идея сортировки с помощью выбора не сложнее двух предыдущих. На j-ом

этапе выбирается элемент наименьший среди M,

M,. . ., M(см.

процедуру )

и меняется местами с элементом M.

В результате после j-го

этапа все элементы M,

M,. . ., Mбудут

упорядочены.

Сказанное можно описать следующим образом:

Более точно:

В программе, как уже было сказано, используется процедура

FindMin,

вычисляющая индекс lowindex элемента,

наименьшего среди элементов массива с индексами не меньше, чем startindex:

Оценивая эффективность применения , учтите что в демонстрации сортировки выбором

отсутствует пошаговое выполнение этой процедуры.

Сравнение скоростей сортировок

Для сравнения сгенерируем массив из 5000 чисел от 0 до 1000. Затем определим время, необходимое для завершения каждого алгоритма. Повторим каждый метод 10 раз, чтобы можно было более точно установить, насколько каждый из них производителен.

Пузырьковая сортировка — самый медленный из всех алгоритмов. Возможно, он будет полезен как введение в тему алгоритмов сортировки, но не подходит для практического использования.Быстрая сортировка хорошо оправдывает своё название, почти в два раза быстрее, чем сортировка слиянием, и не требуется дополнительное место для результирующего массива.Сортировка вставками выполняет меньше сравнений, чем сортировка выборкой и в реальности должна быть производительнее, но в данном эксперименте она выполняется немного медленней. Сортировка вставками делает гораздо больше обменов элементами. Если эти обмены занимают намного больше времени, чем сравнение самих элементов, то такой результат вполне закономерен.

Вы познакомились с шестью различными алгоритмами сортировок и их реализациями на Python. Масштаб сравнения и количество перестановок, которые выполняет алгоритм вместе со средой выполнения кода, будут определяющими факторами в производительности. В реальных приложениях Python рекомендуется использовать встроенные функции сортировки, поскольку они реализованы именно для удобства разработчика.

Лучше понять эти алгоритмы вам поможет их визуализация.

Чётно-нечётная сортировка

На сей раз мы не будем сновать по массиву взад-вперёд, а снова вернёмся к идее планомерного обхода слева-направо, но только сделаем шире шаг. На первом проходе элементы с нечётным ключом сравниваем с соседями, зиждущимися на чётных местах (1-й сравниваем со 2-м, затем 3-й с 4-м, 5-й с 6-м и так далее). Затем наоборот — «чётные по счёту» элементы сравниваем/меняем с «нечётными». Затем снова «нечёт-чёт», потом опять «чёт-нечет». Процесс останавливается тогда, когда после подряд двух проходов по массиву («нечётно-чётному» и «чётно-нечётному») не произошло ни одного обмена. Стало быть, отсортировали.
В обычном «пузырьке» во время каждого прохода мы планомерно выдавливаем в конец массива текущий максимум. Если же передвигаться вприпрыжку по чётным и нечётным индексам, то сразу все более-менее крупные элементы массива одновременно за один пробег проталкиваются вправо на одну позицию. Так получается быстрее.

Разберём последнее улучшение. Этот способ упорядочивает весьма шустро, O(n2) — его наихудшая сложность. В среднем по времени имеем O(n log n), а лучшая даже, не поверите, O(n). То есть, весьма достойный конкурент всяким «быстрым сортировкам» и это, заметьте, без использования рекурсии.

Немного теории

Итак, задача сортировки ставится следующим образом: имеется последовательность однотипных записей − строк разделенных на поля, в которые можно записывать данные различных типов. Одно из полей записей выбрано в качестве ключевого, далее будем называть его ключом сортировки. Необходимо чтобы тип данных ключа допускал операции сравнения («равно», «больше», «меньше», «не больше» и «не меньше»). Как правило, ключом сортировки являются данные целого типа. Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания или убывания значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.

Различают сортировку массивов записей, целиком расположенных в основной памяти – внутреннюю сортировку, и сортировку файлов, хранящихся во внешней памяти и не помещающихся полностью в основной памяти − внешнюю сортировку. Для внутренней и внешней сортировки требуются различные методы. В нашей практической работе будем изучать наиболее известные, простые и понятные методы внутренней сортировки, используя средства языка программирования Python.

Требованием, предъявляемые к внутренней сортировке является то, что методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа (от английского Compare – C) и число перестановок элементов (от английского Move – M).

Заметим, что поскольку сортировка основана только на значениях ключа и никак не затрагивает оставшиеся поля записей, можно говорить о сортировке массивов ключей. Таким образом, задачу сортировки можно сформулировать следующим образом: задан одномерный целочисленный массив Arr_N размером N = DIM, необходимо расположить элементы этого массива в порядке возрастания или убывания значений.

Экспериментальное исследование алгоритмов

В результате выполнения этой практической работы Вам необходимо провести численный эксперимент и

1. заполнить экспериментальными данными сравнительную таблицу эффективности алгоритмов (см. Таблицу 2 ниже);
2. рассчитать теоретические значения показателей эффективности для массива вашего размера. Для этого рекомендуется использовать MS Exell;
3. сравнить экспериментально полученные и расчетные значения;
4. высказать свое мнение об эффективности алгоритмов.

Сравнительная таблица эффективности алгоритмов (Таблица 2)

По структуре таблицы сравнительной эффективности легко видеть, что Вам необходимо проделать как минимум 9 опытов (3 метода х 3 реализации одномерного массива), в каждом из которых должны быть определены два числа C и M. Но в третьем случае, случайного массива, в отличие от двух первых, заранее нельзя предсказать значения показателей эффективности (смотри теорию выше). Естественно, что сравнительный анализ алгоритмов возможен только по средним значениям (в таблице Вы видите функцию Avr(C) – Average, что значит среднее значение С). Для этого необходимо провести серию опытов, желательно, 100–150 для каждого алгоритма (для получения устойчивых значений), т.е. всего 300–450 опытов. Именно это «жуткое» количество экспериментов и определяет структуру построения программы для реализации плана практической работы первой части курсовой работы.

Итак, каждый алгоритм сортировки должен быть оформлен в виде самостоятельной программной единицы – функции, в Python это подключаемый к основной программе модуль. Записать эти модули необходимо в различные файлы, например, insert.py, select.py и bubble.py. Пример одного из них, метод простого включения, файл insert.py,

#метод простого включения Insert
def insert(arr, dim):
    alg_count =               # массив для показателей эффективности
    
    for i in range(1, dim):         # Основной цикл со 2-го элемента право 
        temp = arr               # Запомним элемент для сравнения 
        j = i - 1
        while j >= 0:               # Ищем влево ближайший меньший  
            alg_count += 1       # Считаем операции сравнения 
            if arr > temp:
                alg_count += 1   # Считаем операции перестановки 
                arr = arr   # Сдвигаем элемент влево, а на его место ставим наименьший
                arr = temp
            j -= 1        
    return alg_count

А вот оставшиеся две функции Вам надо написать самостоятельно

Обратите внимание на оформление текста программы и комментарии к алгоритму. Комментарии не позволят Вам забыть эти алгоритмы через неделю после сдачи отчета о своей работе

Кроме того, в отдельный файл (например, sort-exp.py) необходимо записать программу, которая реализует весь численный эксперимент. Естественно, результаты вычислений необходимо сохранять в отдельном файле, который можно прочитать и использовать при заполнении таблицы 2.

Отчет по этой практической работе является частью I вашей большой курсовой работы. Время на выполнение — 2 недели с момента выдачи задания, в нашем случае deadline наступает 14 марта 2019. Не опаздывайте, впереди у вас обширное задание по курсовой работе до конца семестра.

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

Идея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала.

Отсортируем массив {1, 5, 2, 7, 6, 3}
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы
Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами
3 нарушает порядок, меняем местами с 7
Возвращаемся к началу массива и проделываем то же самое

void bubbleSort(int *a, size_t size) {
	size_t i, j;
	int tmp;
	for (i = 1; i < size; i++) {
		for (j = 1; j < size; j++) {
			if (a > a) {
				tmp = a;
				a = a;
				a = tmp;
			}
		}
	}
}

Этот алгоритм всегда будет делать (n-1)2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1)2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.

Пусть нужно отсортировать массив 1, 2, 4, 3

После того, как были поменяны местами элемента a и a нет больше необходимости проходить этот участок массива

Примем это во внимание и переделаем алгоритм

void bubbleSort2(int *a, size_t size) {
	size_t i, j;
	int tmp;
	for (i = 1; i < size; i++) {
		for (j = i; j > 0; j--) {
			if (a < a) {
				tmp = a;
				a = a;
				a = tmp;
			}
		}
	}
}

Ещё одна реализация

void bubbleSort2b(int *a, size_t size) {
	size_t i, j;
	int tmp;
	for (i = 1; i < size; i++) {
		for (j = 1; j <= size-i; j++) {
			if (a < a) {
				tmp = a;
				a = a;
				a = tmp;
			}
		}
	}
}

В данном случае будет уже вполовину меньше шагов, но всё равно остаётся проблема сортировки уже отсортированного массива: нужно сделать так, чтобы отсортированный массив функция просматривала один раз. Для этого введём переменную-флаг: он будет опущен (flag = 0), если массив отсортирован. Как только мы наткнёмся на нарушение порядка, то флаг будет поднят (flag = 1) и мы начнём сортировать массив как обычно.

void bubbleSort3(int *a, size_t size) {
	size_t i;
	int tmp;
	char flag;
	do {
		flag = 0;
		for (i = 1; i < size; i++) {
			if (a < a) {
				tmp = a;
				a = a;
				a = tmp;
				flag = 1;
			}
		}
	} while (flag);
}

В этом случае сложность также порядка n2, но в случае отсортированного массива будет всего один проход.

Теперь усовершенствуем алгоритм. Напишем функцию общего вида, чтобы она сортировала массив типа void. Так как тип переменной не известен, то нужно будет дополнительно передавать размер одного элемента массива и функцию сравнения.

int intSort(const void *a, const void *b) {
	return *((int*)a) > *((int*)b);
}

void bubbleSort3g(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
	size_t i;
	void *tmp = NULL;
	char flag;

	tmp = malloc(item);

	do {
		flag = 0;
		for (i = 1; i < size; i++) {
			if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) {
				memcpy(tmp, ((char*)a + i*item), item);
				memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item);
				memcpy(((char*)a + (i-1)*item), tmp, item);
				flag = 1;
			}
		}
	} while (flag);

	free(tmp);
}

Функция выглядит некрасиво – часто вычисляется адрес текущего и предыдущего элемента. Выделим отдельные переменные для этого.

void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
	size_t i;
	void *tmp = NULL;
	void *prev, *cur;
	char flag;

	tmp = malloc(item);

	do {
		flag = 0;
		i = 1;
		prev = (char*)a;
		cur  = (char*)prev + item;
		while (i < size) {
			if (cmp(cur, prev)) {
				memcpy(tmp, prev, item);
				memcpy(prev, cur, item);
				memcpy(cur, tmp, item);
				flag = 1;
			}
			i++;
			prev = (char*)prev + item;
			cur  = (char*)cur  + item;
		}
	} while (flag);

	free(tmp);
}

Теперь с помощью этих функций можно сортировать массивы любого типа, например

void main() {
	int a = {1, 0, 9, 8, 7, 6, 2, 3, 4, 5};
	int i;

	bubbleSort3gi(a, sizeof(int), 10, intSort);
	for (i = 0; i < 10; i++) {
		printf("%d ", a);
	}
	_getch();
}

Заключение

Как мы уже упоминали ранее, эффективность быстрой сортировки сильно зависит от выбора точки опоры — он может «упростить или усложнить» сложность алгоритма во времени (и в пространстве стека). Нестабильность алгоритма также может стать препятствием для использования с пользовательскими объектами.

Тем не менее, несмотря на все это, средняя сложность времени O(n*log_n) в быстрой сортировки, а также его относительно небольшое потребление памяти и простая реализация делают его очень эффективным и популярным алгоритмом.

Источники используемые для написания статьи: Olivera Popović — Quicksort in Pythonhttps://stackoverflow.com/questions/18262306/quicksort-with-pythonhttps://www.geeksforgeeks.org/python-program-for-quicksort/

Spread the love

Заключение

Метод пузырька гораздо менее эффективен других алгоритмов, однако он имеет простую и понятную реализацию, поэтому часто используется в учебных целях. Кроме того, пузырьковая сортировка может использоваться для работы с небольшими массивами данных.

На самом деле, вместо самостоятельного написания алгоритмов сортировки программисты на Python используют стандартные функции и методы языка, такие как и . Эти функции отлажены и работают быстро и эффективно.

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