В данной статье рассматриваются различные варианты сортировки обменами, а также даётся описание простого графического приложения (processing.js) с примерами сортировок.
Перед прочтением рекомендую ознакомиться со статьями:
> Сортировка обменами
> Пузырьковая сортировка и все-все-все
> Глупая сортировка и некоторые другие, поумнее
Пузырьковая сортировка
Простейший вариант: перебирать массив от первого элемента к последнему, меняя местами (если потребуется) соседние элементы.
> Проверить можно здесь
Для того, чтобы передвинуть ползунок, надо нажать на серую кнопку в левом нижнем углу.
При нажатии на кнопку сдвигаем ползунок на один шаг вправо
incPaddle++;Далее проверяем: не достигли ли мы конца массива (тогда прыгаем в начало), дальше сравниваем (меняем местами) соседние элементы:
Код кнопки
// кнопка
// нажатие
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 (ограничитель), который будет сдвигаться к началу массива после каждого перебора.
if(incPaddle>=limiter) {
incPaddle=1;
limiter--;
if(limiter<1) limiter=1;
}
> Проверить можно здесь
Еще об одном способе уменьшить количество переборов можно прочитать в статье 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;
}
> Проверить можно здесь
Сортировка чёт-нечет
Будем сдвигать ползунок на два шага, сравнивая соседние элементы
incPaddle=incPaddle+2;Т.о. мы сравниваем элементы 0 и 1, 2 и 3, 4 и 5, 6 и 7, и т.д.
Достигнув конца мвссива, сдвигаем ограничитель на один шаг влево, ползунок ставим в начало массива и сравниваем элементы 1 и 2, 3 и 4, 5 и 6, 7 и 8, и т.д.
Дойдя до ограничителя, сдвигаем его на одни шаг вправо, ползунок ставим в начало массива.
> Проверить можно здесь
Гномья сортировка
После поднятия флага сохраняем координату ползунка в переменной limiterR и возващаеми ползунок в начало массива по шагам.
incPaddle--;Оказавшись в начале массива сбрасываем флаг и ставим ползунок в ячейку с координатой, которую мы сохранили в переменную limiterR
if(incPaddle==0){
flag=false;
incPaddle=limiterR;
}
> Проверить можно здесь
Сортировка расчёской
Изменив логику работы ограничителя, получим сортировку расчёской/гребёнкой. Сравниваем (меняем местами) элементы. Сдвигаем ограничитель влево на один шаг и сохраняем его индекс в переменой limiterStore.
if(limiter==moduleSize) {
limiter = limiterStore-1;
limiterStore = limiter;
incPaddle=1;
}
Cдвигаем по шагам ползунок с ограничителем в конец массива
if(limiter!=moduleSize) { // пока limiter не достиг конца массива
limiter++;
incPaddle++;
}
Дойдя ограничителем до конца массива, ставим ползунок в начало массива, а ограничитель ставим в limiterStore-1:
if(limiter==moduleSize) {
limiter = limiterStore-1;
limiterStore = limiter;
incPaddle=1;
}
> Проверить можно здесь
Шейкерная сортировка
Добавим ограничитель limiterL в начало массива.
Пусть флаг flag поднимается, когда ползунок достигает правого ограничителя limiterR, тогда ограничитель сдвигается влево на один шаг. Далее, когда флаг поднят, ползунок по шагам двигается обратно к левому ограничителю limiterL — ограничитель сдвигается вправо на один шаг — ползунок двигается по шагам вправо…
// отжатие
void mouseReleased() {
if(boolButton) {
if(!flag) {
incPaddle++;
if(incPaddle==limiterR) {
flag=true;
limiterR--;
if(limiterR<=limiterL+1) limiterR=limiterL+1; }
}
if(flag) {
incPaddle--;
if(incPaddle==limiterL) {
flag=false;
limiterL++;
if(limiterL>=limiterR-1) limiterL=limiterR-1; }
}
}
}
> Проверить можно здесь
LoadRunner
Я честно посмотрел всю анимацию на КДПВ. Можно её ускорить?
demsp Автор
gifка отсюда