Какую роль в сортировке играет условие айверсона

Сюда можно добавить сортировку правой части массива по убыванию, добавив максимальный элемент max — получим шейкерную сортировку выбором. См. раздел про шейкерную сортировку в конце статьи.

Быстрая сортировка

Механизм выбора опорного элемента используется также и в быстрой сортировке. Этот алгоритм предполагает выбор начального опорного элемента, с которым сравниваются все остальные элементы массива. От выбора начального элемента зависит время выполнения алгоритма. На gif-ке, представленной выше, начальным является элемент с номером 3. Подробнее про выбор начального опорного элемента можно прочитать в статье (Википедия).
Видео, посвящённое быстрой сортировке есть на официальном youtube-канале языков processing и p5.js Вот здесь можно посмотреть визуализацию алгоритма.
Если опорным является первый элемент, то можно перед ним вставлять элементы меньше опорного, тогда массив разделится на две части, слева будут элементы меньше опорного, справа — больше. О таком способе см. раздел про сортировку вставками ниже.

Гномья сортировка

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

После подъёма флага сохраняем координату ползунка в переменной limiterR и возвращаем ползунок в начало массива по шагам

slider--; 

Оказавшись в начале массива сбрасываем флаг и ставим ползунок в ячейку с координатой, которую мы сохранили в переменную limiterR

 if(slider==0)

Изменив данный алгоритм, получим "сортировку вставками".
В сортировке вставками выбирается опорный/минимальный элемент, затем в неотсортрованной части массива выбирается элемент, меньше опорного и вставляется перед опорным

Пусть у нас минимальный элемент обменивается местами с предыдущими, вплоть до опорного, и т.о. вставляется перед опорным.
Добавим условие

 if(slider==limiterR-1 && mods[slider-1].rectHight

Сравнение с ограничителем

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

 if(mods[slider-1].rectHight > mods[limiterL-1].rectHight) slider++; 

Если текущий элемент меньше минимального, сохраняем координату ползунка в переменной limiterR и возвращаем ползунок в начало массива по шагам, как в гномьей сортировке

 vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider-2].rectHight; mods[slider-2].rectHight=vTemp; slider--; 

Оказавшись в начале массива сбрасываем флаг и ставим ползунок в ячейку с координатой, которую мы сохранили в переменную limiterR

 if(flag && slider==limiterL)

Если ползунок выходит за правый край, сдвигаем ограничитель на один шаг вправо, возвращаем ползунок к ограничителю

 if(slider==moduleSize+1)

Сюда можно добавить сравнение (обмен) текущего и следующего за текущим элементы по методу пузырька

 if(slider

«Быстрая» сортировка вставками

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

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight) 

вставляем перед опорным найденный элемент

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight)< flag=true; // поднимаем флаг vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider-2].rectHight; mods[slider-2].rectHight=vTemp; >

Если флаг поднят, сдвигаем ползунок влево по шагам, пока не встретим опорный элемент

 if(flag) < slider--; if(slider> 

Т.о. массив разделяется на две части, слева — элементы меньше опорного, справа — больше

Если после каждого перебора сохранять координаты опорного элемента в доп. массиве pivotsArr, то по достижении опорным элементом правого края мы получим массив, отсортированный по уровням/ступеням. Элементы на каждом следующем уровне будут больше элементов предыдущего уровня. Границы уровней будут содержаться в доп. массиве pivotsArr
При каждом нажатии на кнопку будем выводить массив pivotsArr в консоль

 for(int i=0;i

Добавим рандомную функцию randFoo() в конец программы

Теперь надо отсортировать элементы каждого уровня по отдельности (остаётся только добавить условие завершения цикла)

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

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

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

 slider=slider+2;

Т.о. мы сравниваем элементы 0 и 1, 2 и 3, 4 и 5, 6 и 7, и т.д.
Если ползунок достиг края массива, то пусть ограничитель сдвигается на один шаг влево, а ползунок перемещается в начало массива.
Далее сравниваем элементы 1 и 2, 3 и 4, 5 и 6, 7 и 8, и т.д.
Дойдя до ограничителя, сдвигаем его на одни шаг вправо, ползунок ставим в начало массива.

Сортировка расчёской

Пусть ползунок находится в начале массива и правый ограничитель в конце. Сравниваем (меняем местами) элементы. Сдвигаем ограничитель влево на один шаг и сохраняем его индекс в переменой limiterStore

 if(limiter==moduleSize)

Cдвигаем по шагам ползунок с ограничителем в конец массива

 if(limiter!=moduleSize) < // пока limiter не достиг конца массива limiter++; slider++; >

Дойдя ограничителем до конца массива, ставим ползунок в начало массива, а ограничитель ставим в limiterStore-1

 if(limiter==moduleSize)

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

Добавим левый ограничитель limiterL в начало массива.
Пусть флаг flag поднимается, когда ползунок достигает правого ограничителя limiterR, тогда ограничитель сдвигается влево на один шаг. Далее, когда флаг поднят, ползунок по шагам двигается обратно к левому ограничителю limiterL — ограничитель сдвигается вправо на один шаг — ползунок двигается по шагам вправо

Код кнопки

 // отжатие void mouseReleased() < if(boolButton) < if(!flag) < slider++; if(slider==limiterR) < flag=true; limiterR--; if(limiterR<=limiterL+1) limiterR=limiterL+1; >> if(flag) < slider--; if(slider==limiterL) < flag=false; limiterL++; if(limiterL>=limiterR-1) limiterL=limiterR-1; > > > > 

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

 if(mods[slider-1].rectHight

Когда ползунок достигает правого ограничителя limiterR, правый ограничитель сдвигается влево на один шаг, левый ограничитель сдвигается вправо на один шаг, ползунок возвращается к левому ограничителю

 if(slider>=limiterR)

Еще один способ сортировки обменами, использующий двойной цикл, приведён в третьем томе монографии Дональда Кнута «Искусство программирования», о чём можно прочитать в статье «Is this the simplest (and most surprising) sorting algorithm ever?», перевод которой есть на Хабре в блоге компании Спортмастер.
В псевдокоде этот алгоритм можно представить так
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]

Здесь в двойном цикле перебираются и меняются местами элементы с индексами i и j.
На языке Processing этот алгоритм можно представить так:

Алгоритм

int counter;
int moduleSize = 10;
int slider_i = 1;
int slider_j=1;

int vTemp;
//button
int buttonX=25, buttonY=325;
int buttonSize = 50;
boolean boolButton = false;

int count;
Module[] mods;

void setup() size(400, 400);
mods = new Module[moduleSize];
mods[0] = new Module(1*30, 100);
mods[1] = new Module(2*30, 50);
mods[2] = new Module(3*30, 30);
mods[3] = new Module(4*30, 60);
mods[4] = new Module(5*30, 20);
mods[5] = new Module(6*30, 40);
mods[6] = new Module(7*30, 80);
mods[7] = new Module(8*30, 70);
mods[8] = new Module(9*30, 90);
mods[9] = new Module(10*30, 10);
>

void draw() <
background(50);
buttonUpdate();
for (Module mod: mods)

// paddle
rect (slider_i*30, 85, 20, 5);
rect (slider_j*30, 75, 20, 5);

textSize(25);
text(counter,300,350);
// draw button
fill(150);
rect(buttonX,buttonY,buttonSize,buttonSize);
if(boolButton && mousePressed)
<
fill(200);
rect(buttonX,buttonY,buttonSize,buttonSize);
>
>
class Module int xOffset;
int rectHight;

// Contructor
Module(int xOffsetTemp, int rectHightTemp) xOffset = xOffsetTemp;
rectHight=rectHightTemp;
>
// Custom method for drawing the object
void display() fill(255);
rect(xOffset, 100, 20, rectHight);
>
>

// button
void mouseReleased() if(boolButton)
slider_j++;
if(slider_j>moduleSize)
<
slider_i++;
slider_j=1;
>
>
>

void mousePressed() <
if(boolButton)
<
counter++;
if(mods[slider_i-1].rectHight < mods[slider_j-1].rectHight)
<
vTemp= mods[slider_j-1].rectHight;
mods[slider_j-1].rectHight=mods[slider_i-1].rectHight;
mods[slider_i-1].rectHight=vTemp;
>
>
>

void buttonUpdate() if ( overButton(buttonX, buttonY, buttonSize, buttonSize) ) boolButton = true;
> else boolButton = false;
>
>
boolean overButton(int x, int y, int width, int height) if (mouseX >= x && mouseX mouseY >= y && mouseY <= y+height) return true;
> else return false;
>
>

P.S.
Большая коллекция сортировок, в том числе сортировок обменами, собрана у пользователя valemak

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

Еще одна визуализация ряда алгоритмов и структур данных.

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

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

• сортировка
• сортировка обменами
• сортировка пузырьком
• bubble sort
• qsort
• processing.js
• визуализация
• анимация

Сортировка обменом

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

Обозначим квадратными скобками со стрелками t_Ь обмениваемые элементы, а I_I без стрелок — сравниваемые элементы. Первый этап сортировки показан на рис. 5.5, а второй этап — на рис. 5.6.

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

Рис. 5.5. Сортировка обменом (первый просмотр)

Рис. 5.6. Сортировка обменом (второй просмотр) последующий просмотр исключает очередную позицию с найденным максимальным элементом, тем самым укорачивая список. После первого просмотра в последней позиции оказался больший элемент, равный 83 (исключаем его из дальнейшего рассмотрения). Второй просмотр выявляет максимальный элемент, равный 75 (рис. 5.6). Процесс сортировки продолжается до тех пор, пока не будут сформированы все элементы конечного списка либо не выполнится условие Айверсона.

Условие Айверсона: если в ходе сортировки при сравнении элементов не было сделано ни одной перестановки, то множество считается упорядоченным (условие Айверсона выполняется только при шаге d = 1).

Сложность метода стандартного обмена 0(п 2 ).