Sadda.ru Ironetcart Андроид Ассемблер MASM32 Linux Все статьи Table of Contents


 

Пузырьковая сортировка. Эстафета шариков

  Макс Петров июнь 2013

      Порядок (Order) зависимости времени работы алгоритма сортировки от числа (n) элементов в сортируемом массиве записывают оценочным выражением O(f(n)). Для пузырьковой сортировки имеем O(f(n2)), то есть временные затраты на нее пропорциональны квадрату числа элементов в сортируемом массиве. Это плохой показатель, есть сортировки и побыстрее. Однако, программная реализация пузырьковой сортировки очень проста. С массивом до 10 000 чисел пузырьковая сортировка даже в своем немодифицированном варианте на современном компьютере справляется за время не более секунды.

      При пузырьковой сортировке шарики последовательно попарно обмениваются местами, исходя из условия "больше" или меньше". В результате первого прохода шарик с наибольшим (наименьшим) значением оказывается в нужной позиции в конце списка. В пузырьковой сортировке в худшем случае требуется n-1 проходов по массиву с попарным обменом между шариками.

      Недостаток пузырьковой сортировки виден на приведенном рисунке. Пусть шарик с весом "9" и оказался в конце списка после первого же прохода, но часть шариков со значительными весами в результате сдвинулись в ненужную сторону - на шаг влево переместились шарики "6", "8", "5". Также недостатком пузырьковой сортировки является большое число перестановок между элементами массива. Для того, чтобы провести один шарик из крайней левой в крайнюю правую позицию, пришлось обменять местами все шарики.

пузырьковая сортировка эстафета шариков

      Пузырьковая сортировка может быть улучшена по скорости в разы при сохранении присущей ей простоты. В очевидном, но малоупоминаемом видоизменении пузырьковой сортировки шарики сначала "выбирают" из всего ряда подходящего кандидата для перестановки, только затем совершают с ним обмен, в результате число перестановок сокращается, соответственно, ускоряется и сама сортировка. Эту модификацию я буду называть эстафетой шариков. При беглом просмотре Интернета единственное указание на такую модификацию, под названием сортировка с экономией числа перемещений, я нашел здесь:
http://a-urusov2011.narod.ru/index/0-21

      Образно алгоритм модификации можно обрисовать так. Шарик подпрыгивает и отправляется в полет над шеренгой собратьев, высматривая ближайшего члена своей команды. Членом команды шарик считает того, у кого номер меньше (или больше - в этом случае массив будет ранжироваться по убыванию). Увидев кандидата для обмена, шарик приземляется на его место, отправляя в полет выбитый шарик, который ведет себя так же - ищет в ряду меньшее значение, чем у него самого. Если обмен совершить не удалось, шарик становится на место первого стартовавшего, замыкая круг (эстафету). До полной сортировки массива требуется не более n-1 кругов (эстафет).

      Помимо сокращения числа перестановок, при рассмотрении приведенного ниже ассемблерного кода можно увидеть еще одну причину, которая сделает эстафету шариков более быстрой, по сравнению с пузырьковой сортировкой. В ассемблере мы можем сравнивать содержимое ячейки памяти с содержимым регистра процессора, но не с содержимым другой ячейки памяти. Поэтому, перед проверкой выполнения условия приходится один элемент массива пересылать в регистр. Если в эстафете шариков такая пересылка находится во внешнем цикле, то в немодифицированной пузырьковой сортировке приходится записывать ее во внутренний цикл. Выполнение операции во внутреннем цикле добавляет к вычислительным затратам еще k*n2 тактов процессора (k - число тактов на одну операцию).

;========================================================= ;========================================================= ; ПУЗЫРЬКОВАЯ СОРТИРОВКА ; massiv - массив четырехбайтовых чисел; ; massiv_max_index - максимальный индекс массива; ; counter - счетчик обменов, если обменов не было, counter = 0 mov ECX, massiv_max_index .WHILE ECX > 0 mov EDX, 0 mov counter, 0 .WHILE EDX < ECX mov EAX, massiv[EDX*4+4] .IF massiv[EDX*4] > EAX push EAX push massiv[EDX*4] pop massiv[EDX*4+4] pop massiv[EDX*4] inc counter .ENDIF inc EDX .ENDW .if counter == 0 .break .endif dec ECX .ENDW ;========================================================= ;========================================================= ; ЭСТАФЕТА ШАРИКОВ ; massiv - массив четырехбайтовых чисел; ; massiv_max_index - максимальный индекс массива mov ECX, 0 .WHILE ECX < massiv_max_index mov EAX, massiv[ECX*4] mov EDX, ECX .WHILE EDX < massiv_max_index inc EDX .IF EAX > massiv[EDX*4] push EAX push massiv[EDX*4] pop EAX pop massiv[EDX*4] .ENDIF .ENDW mov massiv[ECX*4], EAX inc ECX .ENDW

      Сравнение времени обработки массивов четырехбайтовых чисел пузырьковой сортировкой, эстафетой шариков и сортировкой расческой приводится в конце статьи "Сортировка расческой" .

     


Добавить комментарий

E-mail:
*


Контрольные цифры:



Ассемблер MASM32

      Простейшая программа на ассемблере (beeper)
      Переменные и типы данных ассемблера
      Регистры процессора IA32
      Консоль ввода-вывода
      API-функция CharToOem и строки ассемблера
      API-функция ReadConsoleInput
      API-функция PeekConsoleInput
      События консоли (таблица)
      Системы счисления, тэги ассемблера, перевод чисел
      Отрицательные числа
      Инкремент и декремент
      Деление (DIV, IDIV)
      VKDEBUG
      Макросы ассемблера
      Воспоминание об Альгамбре на системном динамике
      Командная строка
      Пузырьковая сортировка. Эстафета шариков
      Сортировка расческой
      Быстрая сортировка

     


© Max Petrov При использовании материалов ссылка на sadda.ru обязательна