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

В данной статье рассматриваются различные варианты сортировки обменами, а также даётся описание простого графического приложения (processing.js) с примерами сортировок.

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

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

→ Проверить можно здесь




Для того, чтобы передвинуть ползунок, надо нажать на серую кнопку в левом нижнем углу
При нажатии на кнопку ползунок сдвигается вправо

slider++;

Далее проверяем: находится ли ползунок на противоположной границе массива (тогда прыгаем в начало массива)

if(slider>=moduleSize) 
   { 
    slider=1;     
   }

далее сравниваем (меняем местами) соседние элементы

if(mods[slider].rectHight < mods[slider-1].rectHight)  
    {     
     vTemp= mods[slider-1].rectHight;
     mods[slider-1].rectHight=mods[slider].rectHight;
     mods[slider].rectHight=vTemp;
    }

Поскольку нумерация элементов массива начинается с нуля, а ползунок изначально (при инициализации) находится в первой ячейке int slider=1;, то нам нужно сравнить текущий элемент mods[slider].rectHight с предыдущим mods[slider-1].rectHight



Processing.js использует структуры данных Java, потом код транслируется в javascript (ссылка), поэтому объявление массива экземпляров класса Module, отвечающего за отрисовку элементов и инициализация экземпляров происходит так

 Module[] mods;
...
 mods[0] = new Module(1*30,  30);
 mods[1] = new Module(2*30,  50);
 mods[2] = new Module(3*30,  10);
 mods[3] = new Module(4*30,  60);
 mods[4] = new Module(5*30,  20);
 mods[5] = new Module(6*30,  100);
 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, 40);  
 

Основная функция отрисовки void draw() представляет собой бесконечный цикл, в котором перебираются экземпляры класса

for (Module mod : mods) {  mod.display();  }

Для нажатия на кнопку (прямоугольник в левом нижнем углу) необходимо сравнить координаты курсора и кнопки в булевой функции overButton(). Само нажатие обрабатывается в функции mousePressed(). Отжатие кнопки обрабатывается в функции mouseReleased().

Рандомные значения

Добавим функцию randFoo(), которая возвращает рандомные значения. Для того, чтобы значения не повторялись, будем добавлять их к ArrayList списку listRand, а в функции randFoo() проверять, не входит ли новое рандомное число в список listRand

int randFoo(){
  newRand = int(random(1,11));
  if(!listRand.contains(newRand) )  listRand.add(newRand );
 	 else newRand=randFoo();
		return newRand;
}

→ Проверить можно здесь

Пиксельная сортировка

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

void draw(){
  while (i <= height) { 
  c=get(i,j);  // получаем цвет пикселя
  cTemp=c;   // запоминаем цвет во временной переменной
  i++;            // переходим к следующему пикселю
  c=get(i,j);   // получаем цвет следующего пикселя
 if(cTemp>c)    { // сравниваем пиксели
   fill(c);               // меняем пиксели местами
   rect(i-1,j,1,1);  
   fill(cTemp);
  rect(i,j,1,1);   } 
 }  
  if(mousePressed) { if(j>=width) j=0; } // переходим к следующей колонке пикселей 
  if(i >= height) {j++; i=0;}
}

→ Проверить можно здесь
Чтобы начать сортировку, надо кликнуть на картинку и удерживать кнопку.
Ещё про пиксельные сортировки можно прочитать здесь.
Видео о пиксельной сортировке на официальном канале The Coding Train здесь

Ограничитель и флаг

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

   if(slider>=limiter) { 
    slider=1;
    limiter--;
    if(limiter<1) limiter=1; 
   }

→ Проверить можно здесь

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

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



→ Проверить можно здесь

Если поставить ограничитель слева и использовать элемент с ограничителем как опорный/минимальный, получим сортировку выбором.

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

if(mods[slider-1].rectHight < min){     
     min=mods[slider-1].rectHight;
    }

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

 if (mods[limiterL-1].rectHight>min) {     
     vTemp= mods[limiterL-1].rectHight;
     mods[limiterL-1].rectHight=mods[slider-1].rectHight;
     mods[slider-1].rectHight=vTemp;
    }    

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

if(slider==moduleSize){ 
      if(limiterL<moduleSize) limiterL++;
      min=mods[limiterL-1].rectHight;
      incPaddle=limiterL-1; 
      }

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

if(mods[limiterL-1].rectHight>mods[moduleSize-1].rectHight)     {
     vTemp=mods[limiterL-1].rectHight;
     mods[limiterL-1].rectHight=mods[moduleSize-1].rectHight;
     mods[moduleSize-1].rectHight=vTemp;        
     }

Тогда можно не проверять крайний правый элемент массива

//if(slider==moduleSize){       
     if(slider==moduleSize-1){
      //if(limiterL<moduleSize) limiterL++;
      limiterL++;      
      min=mods[limiterL-1].rectHight;
      slider=limiterL-1; 
      }
     // slider++;
    if(slider<moduleSize) slider++;    

→ Проверить можно здесь

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

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

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

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

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

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

slider--;

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

if(slider==0){ 
    flag=false;            
    slider=limiterR;
     }

→ Проверить можно здесь

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

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

  if(slider==limiterR-1 &&
     mods[slider-1].rectHight<mods[limiterR-1].rectHight){
   flag=false;            
   slider=limiterR;
   }

→ Проверить можно здесь


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

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

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<pivot){ 
                           flag=false; // опускаем флаг
                           pivot++; 
                           slider=pivot;
                           }
           }

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

→ Проверить можно здесь

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

for(int i=0;i<pivotsArr.length;i++){
        print(" ");
                 print(pivotsArr[i]);  
                               print(" ");   }

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

→ Проверить можно здесь

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

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

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

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

slider=slider+2;

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

→ Проверить можно здесь

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

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

if(limiter==moduleSize)   {
    limiter = limiterStore-1;
    limiterStore = limiter;
    slider=1;
   }

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

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

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

  if(limiter==moduleSize)   {
    limiter = limiterStore-1;
    limiterStore = limiter;
    slider=1;
   }

→ Проверить можно здесь

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

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


→ Проверить можно здесь

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

if(mods[slider-1].rectHight<mods[limiterL-1].rectHight){
    vTemp= mods[slider-1].rectHight;
     mods[slider-1].rectHight=mods[limiterL-1].rectHight;
     mods[limiterL-1].rectHight=vTemp;
  }

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

if(slider>=limiterR){ 
     limiterL++; 
     slider=limiterL;
     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 этот алгоритм можно представить так:

Проверить можно здесь.

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

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

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

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

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