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

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

Сортировка обменом — метод, в котором элементы списка последовательно сравниваются между собой и меняются местами в том случае, если предшествующий элемент больше последующего. Требуется, например, провести сортировку списка <40, 11, 83, 57, 32, 21, 75, 64>методом стандартного обмена или методом «пузырька».

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

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

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

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

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

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

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

Сортировку вставкой рассмотрим на примере заданной неупорядоченной последовательности элементов:

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

Рис. 2. Сортировка вставкой

На первом этапе сравниваются два начальных элемента. Поскольку второй элемент меньше первого, он перемещается на место первого элемента, который сдвигается вправо на одну позицию. Остальная часть последовательности остаётся без изменения. На втором этапе из неупорядоченной последовательности выбирается элемент и сравнивается с двумя упорядоченными ранее элементами. Так как он больше предыдущих, то остаётся на месте. Затем анализируются четвёртый, пятый и последующие элементы – до тех пор, пока весь список не будет упорядоченным, что имеет место на последнем (седьмом) этапе.

Разновидностью сортировки вставкой является метод фон Неймана. Пусть заданы два упорядоченных по возрастанию элементов одномерных массива: а размерности n и b размерности m. Требуется получить третий массив с размерности n+m, который содержал бы все элементы исходных массивов, упорядоченных по возрастанию.

Алгоритм решения этой задачи ,известный как «сортировка фон Неймана» или сортировка слиянием, состоит в следующем: сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив. Полученный новый массив упорядочен таким же образом, как исходные.

Сложность метода сортировки вставкой порядка O(n²).

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

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

Требуется, например, провести сортировку списка методом стандартного обмена или методом ’пузырька’ :

Обозначим квадратными скобками со стрелками обмениваемые элементы, а — сравниваемые элементы. Первый этап сортировки показан на рис.3, а второй этап – на рис.4.

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

Второй просмотр выявляет максимальный элемент, равный 75 (рис.4).

Процесс сортировки продолжается до тех пор, пока не будут сформированы все элементы конечного списка, либо не выполнится условие Айверсона.

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

Шейкерная сортировка (англ, cocktail sort) является модификацией пузырьковой. Улучшить работу последней можно исходя из следующих соображений:

• 1. Если при некотором проходе не было выполнено ни одной перестановки, то множество А является упорядоченным. Это условие также называют условием Айверсона. При его выполнении алгоритм завершает работу. В примере предыдущего параграфа такая ситуация наступает после четвертого прохода, в течение которого не было сделано ни одной перестановки.
• 2. Пусть на г-м проходе последняя перестановка выполнялась для элементов ai и ai₊1, где L + 1 то на следующем проходе сравнение выполняется для первых L элементов.
• 3. Для проходов с нечетными номерами множество А можно просматривать слева направо, а для четных — справа налево. При этом наименьший элемент окажется в начале и будет уже отсортированным. Если запомнить номер элемента Я последней перестановки ап и а а- для четного прохода, то на следующем нечетном просматриваются элементы не с первого, а начиная с номера Я.

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

Номер прохода

Перестановка 9 и 3

Перестановка 12 и 1

Перестановка 12 и 8

Перестановка 12 и 5

Перестановка 9 и 1

Перестановка 9 и 8

Перестановка 9 и 5

Перестановка 3 и 1

Перестановка 8 и 5

Таким образом, при использовании чередующихся проходов слева направо и справа налево формируются левая и правая границы сравниваемых элементов L и R соответственно.

Пример 11.6. Применяя алгоритм шейкерной сортировки, упорядочить множество чи сел А = <9,3,12,1,8,5>по возрастанию.

Решение. В табл. 11.5 приведены состояния множества А при шейкерной сортировке. Величины L и R изменяются после выполнения действий в соответствующей строке (например, значение L будет изменено на 2 после перестановки 12 и 5). Вертикальной чертой сверху помечены элементы, находящиеся на своих местах в упорядоченной части множества.

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

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 <= x+width &&
mouseY >= y && mouseY <= y+height) return true;
> else return false;
>
>