Сборник по задачам и примерам Assembler


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



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

Под сортировкой понимается процесс перестановки элементов некоторого множества в порядке убывания или возрастания. Если элементы множества — скаляры, то сортировка ведется относительно их значений. Если элементы множества — структуры, то каждая структура должна иметь поле, относительно которого будет производиться упорядочивание местоположения элементов (то есть сортировка) относительно других элементов-структур множества.

Различают два типа алгоритмов сортировки: сортировку массивов и сортировку файлов. Другое их название — алгоритмы внутренней и внешней сортировки. Разница заключается в местонахождении объектов сортировки: для внутренней сортировки — это оперативная память компьютера, для внешней — файл. В данном разделе будут рассмотрены алгоритмы внутренней сортировки массивов. Алгоритмы внешней сортировки будут рассмотрены в разделе, посвященном работе с файлами.

Существует несколько алгоритмов сортировки массивов, которым следует уделить внимание в контексте проблемы изучения ассемблера. По критерию эффективности алгоритмы сортировки массивов делят на простые и улучшенные. Среди простых методов сортировки, которые также называют сортировками «на том же месте», мы рассмотрим следующие:

  • сортировка прямым включением;
  • сортировка прямым выбором;
  • сортировка прямым обменом.

Улучшенные методы сортировки в нашем изложении будут представлены следующими алгоритмами:

  • сортировка Шелла;
  • сортировка с помощью дерева;
  • быстрая сортировка.

Сортировка прямым включением

Идея сортировки прямым включением (программа prg4_96.asm) заключается в том, что в сортируемой последовательности masi длиной n (i = 0..n - 1) последовательно выбираются элементы начиная со второго (i< 1) и ищутся их местоположения в уже отсортированной левой части последовательности. При этом поиск места включения очередного элемента х в левой части последовательности mas может закончиться двумя ситуациями:

  • найден элемент последовательности mas, для которого masi<x;
  • достигнут левый конец отсортированной слева последовательности.



  • - Начало -  - Назад -  - Вперед -



    Книжный магазин