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

TurboBasic 1.1

CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 ' 32 766 - 62.7 SEC
DIM Y, Y1, Y2, Y3, Y4 'FRE(-1)=21440-21456
 
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
 
FOR X = 1 TO N
   Y = X
   PRINT Y;
NEXT X:PRINT
 
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
 
PRINT " SLUCHAINYE CHISLA"
 
FOR X = 1 TO N
   YD=Y
   XS=INT(RND*N)+1
   PRINT XS;
   Y=Y
   Y=YD
NEXT X:PRINT
 
PRINT " PEREMESHANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y;
NEXT X:PRINT
 
'ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2)
MTIMER
FOR J=1 TO N-1 STEP 1
   F=0
   FOR I=1 TO N-J STEP 1
      'IF Y > Y THEN D=Y:Y=Y:Y=D:F=1
      IF Y > Y THEN SWAP Y,Y:F=1
 
      LOCATE 8,1                    REM
      PRINT " ANYMACIJA SORTIROVKI" REM
      FOR X1=1 TO N                 REM ANIMATION BLOCK
         PRINT Y;               REM
      NEXT X1:PRINT                 REM
      DELAY .5                      REM
 
   NEXT I
   IF F=0 THEN EXIT FOR
NEXT J
T1=MTIMER
 
PRINT " OTSORTIROVANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y;
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1

Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность. В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).


Как можно улучшить шейкер сортировку

Вы наверно уже заметили, что самый большой элемент перемещается в конец массива (за первый цикл в ), а самый маленький элемент переместится вниз на одну ячейку.

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

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

Переменную мы будем уменьшать на один после первого цикла (который находится в строках 6 — 11), же будем уменьшать после второго цикла (ну или другими словами в самом конце цикла ).

Ниже, находится оптимизированная версия шейкер сортировки:

bool sort_or_not = true; int right = n; // n — размер массива int left = 1; do { bool sort_or_not = true; for (int i = left; i <= right; i++) { if (chisla > chisla) { swap (chisla, chisla); sort_or_not = false; } } right—; for (int i = right; i >= left; i—) { if (chisla < chisla) { swap (chisla, chisla); sort_or_not = false; } } left++; } while (sort_or_not == false);

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

boolsort_or_not=true;

intright=n;// n — размер массива

intleft=1;

do{

boolsort_or_not=true;

for(inti=left;i<=right;i++){

if(chislai-1>chislai){

swap(chislai-1,chislai);

sort_or_not=false;

}

}

right—;

for(inti=right;i>=left;i—){

if(chislai<chislai-1){

swap(chislai,chislai-1);

sort_or_not=false;

}

}

left++;

}while(sort_or_not==false);

Как улучшить пузырьковую сортировку

Ниже вы можете видеть оптимизированную версию пузырьковой сортировки.

for (int i = 0; i < 10; i++) { bool flag = true; for (int j = 0; j < 10 — (i + 1); j++) { if (digitals > digitals) { flag = false; swap (digitals, digitals); } } if (flag) { break; } }

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

for(inti=;i<10;i++){

boolflag=true;

for(intj=;j<10-(i+1);j++){

if(digitalsj>digitalsj+1){

flag=false;

swap(digitalsj,digitalsj+1);

}

}

if(flag){

break;

}

}

Давайте посмотрим, что мы сделали для ее оптимизации:

  1. В строке 17: изменили условие внутреннего цикла на .Поэтому чтобы лишний раз не сравнивать элементы массива тратя на это время, мы решили уменьшать отрезок внутреннего цикла на 1, после каждого полного прохода внешнего цикла.
  2. Вы могли заметить, что если даже массив стал отсортирован (или сразу был отсортирован) алгоритм все равно продолжает сравнивать элементы.

Для этого в строке 5: чтобы пузырьковая сортировка останавливалась (когда массив уже стал отсортирован), мы объявили булеву переменную (ее обычно называют флаг или флажок). Еще при ее инициализации мы поместили значение , но она меняется на:

false, если результат условия в строке 4: положительный.

А в строке 9: чтобы мы могли выйти из алгоритма мы проверяем:

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

В строке 6: вы (возможно) увидели незнакомую функцию . Если коротко описать что она делает, то она принимает два аргумента (через запятую) и меняет их значения местами. В нашем случаи она принимает ячейки и . Мы использовали эту функцию чтобы не писать вот эти 3 строчки:

int b = digitals; digitals = digitals; digitals = b;

1 2 3

intb=digitalsj;

digitalsj=digitalsj+1;

digitalsj+1=b;

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

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

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

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

Задача стоит следующем образом нам необходимо рассортировать какой то неопределенный массив в порядке возрастания. Сделать можно это применяя пузырьковую сортировку массива. Начинаем сортировку мы с самого начала нашей имеющийся последовательности, и постепенно шаг за шагом сравниваем последовательно каких либо два числа. Сравниваются два числа — правое и левое. Если левое число меньше правого то они меняются местами, В другом случае они остаются на своих местах и алгоритм продолжает перебирать цифры дальше, прямо как танцоры в видео, (обязательно посмотрите, там очень наглядно показано как работает такого рода пузырьковая сортировка)

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

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

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

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

#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; }

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

#include <iostream>  

usingnamespacestd;

intmain(){

setlocale(LC_ALL,»rus»);

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

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

for(inti=;i<10;i++){

cin>>digitalsi;// «читаем» элементы в массив

}

for(inti=;i<10;i++){

for(intj=;j<9;j++){

if(digitalsj>digitalsj+1){

intb=digitalsj;// создали дополнительную переменную

digitalsj=digitalsj+1;// меняем местами

digitalsj+1=b;// значения элементов

}

}

}

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

for(inti=;i<10;i++){

cout<<digitalsi<<» «;// выводим элементы массива

}

system(«pause»);

return;

}

Давайте поподробнее разберем строки 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.

Что такое шейкер сортировка

Мы можем сделать некоторые модификации в пузырьковой сортировке чтобы сделать ее быстрее.

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

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

Такая разновидность пузырьковой сортировки называется — шейкер сортировка (Cocktail sort). У нее такое необычное название, потому что когда с помощью ее сортируют, массив похож на коктейль, который пытаются перемешать.

Описание алгоритма

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

  • первый проход: элементы массива чисел берутся по два и также парами сравниваются. Если в какой-то двойке элементов первое значение оказывается больше второго, программа производит их обмен местами;
  • следовательно, наибольшее число попадает в конец массива. В то время как все остальные элементы остаются, как и были, в хаотичном порядке и требуют еще сортировки;
  • поэтому и необходим второй проход: производится он по аналогии с предыдущим (уже описанным) и имеет число сравнений — минус один;
  • у прохода номер три сравнений на единицу меньше, чем у второго, и на двойку, чем у первого. И так далее;
  • подытожим, что каждый проход имеет (всего значений в массиве, конкретное число) минус (номер прохода) сравнений.

Еще короче алгоритм будущей программы можно записать так:

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

Метод пузырька

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


В общем случае алгоритм сортировки пузырьком следующий:

  1. Сравнить текущий элемент со следующим.
  2. Если следующий элемент меньше/больше текущего, поменять их местами.
  3. Если массив отсортирован, закончить алгоритм, иначе перейти на шаг 1.

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

Внешний цикл в худшем случае совершает N (кол-во элементов) – 1 проходов, то есть внутренний цикл выполняется N-1 раз.

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

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

Sort() и sorted() в Python

В Python вы можете отсортировать список, используя встроенный метод list.sort() или встроенную функцию sorted().

Функция sorted() создает новый отсортированный список, в то время как метод list.sort() сортирует список на месте. Если вы хотите сохранить, несортированный список использовать функцию sorted(). Другое отличие состоит в том, что функция sorted() работает с любым повторяемым объектом.

Синтаксис sort()и sorted()следующий:

list.sort(key=function, reverse=Boolean)
sorted(iterable, key=function, reverse=Boolean)

Необязательные ключевые аргументы key и reverse имеют следующее значение:

  • key – Функция, которая принимает один аргумент и преобразует его перед сравнением. Функция должна возвращать одно значение, которое используется для сравнения сортировки.
  • reverse – Значение реверса может быть либо либо, True либо False. Значением по умолчанию является True. Когда для этого аргумента установлено значение false, список сортируется в обратном порядке.

Элементы списка сравниваются с помощью оператора < (меньше чем) и сортируются по возрастанию. Оператор < не поддерживает сравнения строки в целое число, так что если у вас есть список , содержащие строки и целые числа, то операция сортировки не удастся.

В следующем примере показано, как отсортировать список строк в алфавитном порядке:

directions =  

directions.sort()

print('Sorted list:', directions)
Sorted list: 

Если вы хотите сохранить исходный список без изменений, используйте функцию sorted():

directions =  

sorted_directions = sorted(directions)

print('Sorted list:', sorted_directions)
Sorted list: 

Чтобы отсортировать список в обратном (нисходящем) порядке, установите аргумент reverse в True:

directions =  

directions.sort(reverse=True)

print('Sorted list:', directions)
Sorted list: 

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

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

Отсортируем массив {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();
}

Пример работы алгоритма[править]

Возьмём массив и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

До После Описание шага
5 1 4 2 8 1 5 4 2 8 Здесь алгоритм сравнивает два первых элемента и меняет их местами.
1 5 4 2 8 1 4 5 2 8 Меняет местами, так как 5 > 4
1 4 5 2 8 1 4 2 5 8 Меняет местами, так как 5 > 2
1 4 2 5 8 1 4 2 5 8 Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.

Второй проход:

До После Описание шага
1 4 2 5 8 1 4 2 5 8
1 4 2 5 8 1 2 4 5 8 Меняет местами, так как 4 > 2
1 2 4 5 8 1 2 4 5 8
1 2 4 5 8 1 2 4 5 8

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

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

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

Первая итереация (первый повтор алгоритма) меняет между собой 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

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

Самая простая реализация выполняется так:


Процедура Sortirovka_Puzirkom;

Начало

цикл для j от nachalnii_index до konechii_index;

цикл для i от nachalnii_index до konechii_index-1;

если massiv>massiv (первый элемент больше второго), то:

(меняем значения местами);

Конец

Конечно, здесь простота только усугубляет ситуацию: чем проще алгоритм, тем более в нем проявляются все недостатки. Затратность времени слишком велика даже для небольшого массива (тут вступает в дело относительность: для обывателя количество времени может казаться маленьким, но в деле программиста каждая секунда или даже миллисекунда на счету).

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

Процедура Sortirovka_Puzirkom;

Начало

sortirovka = истина;

цикл пока sortirovka = истина;

sortirovka = ложь;

цикл для i от nachalnii_index до konechii_index-1;

если massiv>massiv (первый элемент больше второго), то:

(меняем элементы местами);

sortirovka = истина; (обозначили, что обмен был произведен).

Конец.

Заключение

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

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

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


С этим читают