JavaScript
Programming
Java
Algorithms
Processing
4 June

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

Tutorial

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

Перед прочтением рекомендую ознакомиться со статьями пользователя valemak:

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

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


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

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


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

Далее проверяем: не достигли ли мы конца массива (тогда прыгаем в начало), дальше сравниваем (меняем местами) соседние элементы
Код кнопки

// кнопка
// нажатие 
 void mousePressed() { 
 if(boolButton)
 {  
 counter++; 
  if(mods[slider].rectHight < mods[slider-1].rectHight)  
    {     
     vTemp= mods[slider-1].rectHight;
     mods[slider-1].rectHight=mods[slider].rectHight;
     mods[slider].rectHight=vTemp;
    }
  } 
}
//отжатие 
void mouseReleased() {
 if(boolButton)
  {    
   slider++;
   if(slider>=moduleSize) 
   { 
    slider=1;     
   }
  }   
 }




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();  }

Добавим функцию 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, который поднимается, когда мы встречаем пару элементов, которые нужно поменять местами. Если флаг поднят, перебираем массив повторно. Если нет, заканчиваем цикл. Состояние флага выводится в консоль

Проверка соседних элементов

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



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

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

Добавим переменную 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[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)  {
      flag=false;
      slider=limiterR;
    }

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

if(slider==moduleSize+1)  {
    limiterL++;
    slider=limiterL+1;
    }


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

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

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


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


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

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

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 — ограничитель сдвигается вправо на один шаг — ползунок двигается по шагам вправо
Код кнопки

// отжатие
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<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--;
    }


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

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

+6
2.9k 43
Comments 6
Top of the day