Комбинаторные алгоритмы для программистов



             

Сортировки


В лекциях 14 и 15

мы рассматривали более подробно различные способы сортировки. Здесь мы напоминаем некоторые из них и приводим пример программ.

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

Способ сортировки: сортировка по возрастанию, сортировки по убыванию. Методы сортировки:

  • метод прямого выбора;
  • метод пузырька;
  • метод по ключу;
  • сортировки слиянием;
  • сортировки Батчера.

Сортировка по возрастанию - это сортировка, при которой записи упорядочиваются по возрастанию значений ключевых полей.

Сортировка по убыванию - это сортировка, при которой записи упорядочиваются по убыванию значений ключевых полей.

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

Сортировка по ключу - это сортировка записей с упорядочением по значению указанного поля или группы полей.

Сортировка слиянием - это внешняя сортировка, при которой на первом этапе группы записей сортируются в оперативной памяти и записываются на несколько внешних носителей; на втором этапе упорядоченные группы сливаются с нескольких внешних носителей на один носитель данных. Носитель данных - материальный объект, предназначенный для хранения данных, или среда передачи данных.

Сортировка Батчера - это сортировка, внутренний алгоритм которой работает за время

O(N\cdot\log (N))
.

Программа 5. Сортировка массива по возрастанию методом пузырька.

//Данные, которые нужно отсортировать, берутся из файла "massiv.txt", //результат записывается в массив int mas['K'] и выводится на экран // Алгоритм реализован на Turbo C++. #include <conio.h> #include <stdio.h> #define K 1000; //Размер массива




Содержание  Назад  Вперед