habrahabr

Визуализация сортировки обменами

  • четверг, 6 июня 2019 г. в 00:20:27
https://habr.com/ru/post/454792/
  • JavaScript
  • Программирование
  • Java
  • Алгоритмы
  • Processing



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

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

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

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

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

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

Код кнопки
// кнопка
// нажатие 
 void mousePressed() { 
 if(boolButton) {  
 counter++; 
 // сравниваем соседние элементы
  if(mods[incPaddle].rectHight < mods[incPaddle-1].rectHight)   {     
     vTemp= mods[incPaddle-1].rectHight;
     mods[incPaddle-1].rectHight=mods[incPaddle].rectHight;
     mods[incPaddle].rectHight=vTemp;
    }
  } 
}
//отжатие 
void mouseReleased() {
 if(boolButton)  { 
  // передвигаем ползунок   
   incPaddle++;
  // прыгаем в начало массива 
   if(incPaddle>=moduleSize)    {     incPaddle=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();  }


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

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

Если добавить ограничитель в начало массива, получим шейкерную сортировку.


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

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

Проверка соседних элементов
 if(mods[incPaddle].rectHight < mods[incPaddle-1].rectHight)  
    { 
     flag=true;  // поднимаем флаг
     vTemp= mods[incPaddle-1].rectHight;
     mods[incPaddle-1].rectHight=mods[incPaddle].rectHight;
     mods[incPaddle].rectHight=vTemp;
    }


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

Изменив логику работы ограничителя, получим сортировку расчёской/гребёнкой. Сравниваем ( меняем местами) элементы. Сдвигаем ограничитель влево и сохраняем его индекс в переменой limiterStore.

Cдвигаем ползунок с ограничителем в конец массива, сравнивая (меняя местами) элементы.

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


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

Код
  if(limiter==moduleSize)   {
    limiter = limiterStore-1;
    limiterStore = limiter;
    incPaddle=1;
   }


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