Файл: Алгоритмы сортировки данных (Понятие алгоритма).pdf

ВВЕДЕНИЕ

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

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

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

Сам термин «информатика» (informatique) возник в 60-х годах во Франции для определения области исследований, связанных с автоматизацией обработки информации с помощью электронных вычислительных машин (ЭВМ). Этот термин был образован слиянием слов information (информация) и automatique (автоматика) для обозначения информационной автоматики или автоматизированной переработки информации.

Целью курсовой работы является ознакомление с алгоритмами сортировки, попытка проанализировать их и осветить каждый из них.

Таким образом, задачами курсовой работы являются:

1. изучить теоретическую основу алгоритмов сортировки;

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

3. произвести анализ работы алгоритмов сортировки.

• 1. Теоретический обзор различных сортировочных алгоритмов

     1. Понятие алгоритма

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

---

Слово «алгоритм» происходит от имени узбекского математика девятого века Аль-Харезми, который сформулировал правило четырёх арифметических действий над многозначными числами. В дальнейшем это слово стало использоваться не только в математике, а фактически любую последовательность действий, приводящих к конечному результату, стали называть алгоритмом, а каждое действие шагом алгоритма. Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: 1) определённость; 2) массовость; 3) результативность; 4) дискретность. Определённость алгоритма означает, что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.

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

1. Словесная форма;
2. Словесно-аналитическая форма;
3. В виде блок-схемы (графическое изображение алгоритма);
4. В виде программы на алгоритмическом языке программирования.

Виды алгоритмических структур:

• 1. Линейный алгоритм, в которой все команды выполняются последовательно одна за другой.
  2. Разветвляющийся, в которой в зависимости от условия выполнения либо одна серия команд, либо другая.
  3. Циклический, в которой многократно повторяется некоторый участок алгоритма.

I-ое поколение алгоритмических языков - конец 1950-х начало 1960-х. Совершенствовались ассемблерные языки. В настоящее время они применяются для создания драйверов оборудования ПК.

II-ое поколение - 60е годы. В это время появляются универсальные языки высшего уровня: ФОРТРАН, АЛГОЛ, КОБОЛ, обеспечивающие создание программ для решения задач различного класса.

III-e поколение. С начала 1970-х годов начался переход на создание больших программных комплексов. Они в основном применяются для проектирования приложений баз данных и средств визуального программирования.

В середине 1990-х – 4 поколение языков программирования, назначение которых для образования инструкции текст программ на универсальном языке программирования. Система 4 поколения имеет открытую архитектуру и поддерживает значительное число программных продуктов.

---

Языки программирования:

1. Бейсик отличается встроенными математическими функциями и простыми языковыми конструкциями.
2. Паскаль предназначен для решения вычислительных и информационно-логических задач.
3. Си + + был разработан для облегчения процесса переноса программного обеспечения с одной ЭВМ на другую.
4. Ада ориентирован для применения в системах реального времени и предназначен для разработки программного обеспечения встроенных вычислительных систем.
5. Java (джава) предназначен для создания надёжных, переносимых, распределённых сетевых программных приложений, работающих в архитектуре клиент–сервер, а также удобен для администраторов сети.
6. другим объектно-ориентировочным языком является язык Delphi (дельпхи). Обеспечивает взаимодействие с базами данных, создание различных видов баз, а также работу экономических программ и сети интернет.
7. История разработок алгоритмов сортировки

Первые прототипы современных методов сортировки появились уже в XIX веке. К 1890 году для ускорения обработки данных переписи населения в США американец Герман Холлерит создал первый статистический табулятор — электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах. У машины Холлерита имелся специальный «сортировальный ящик» из 26 внутренних отделений. При работе с машиной от оператора требовалось вставить перфокарту и опустить рукоятку. Благодаря пробитым на перфокарте отверстиям замыкалась определённая электрическая цепь, и на единицу увеличивалось показание связанного с ней циферблата. Одновременно с этим открывалась одна из 26 крышек сортировального ящика, и в соответствующее отделение перемещалась перфокарта, после чего крышка закрывалась. Данная машина позволила обрабатывать около 50 карт в минуту, что ускорило обработку данных в 3 раза. К переписи населения 1900 года Холлерит усовершенствовал машину, автоматизировав подачу карт. Работа сортировальной машины Холлерита основывалась на методах поразрядной сортировки. В патенте на машину обозначена сортировка «по отдельности для каждого столбца», но не определён порядок. В другой аналогичной машине, запатентованной в 1894 году Джоном Гором, упоминается сортировка со столбца десятков. Метод сортировки, начиная со столбца единиц, впервые появляется в литературе в конце 1930-х годов. К этому времени сортировальные машины уже позволяли обрабатывать до 400 карт в минуту.

В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин. По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин. Некоторые конструкторы ЭВМ, в частности разработчики EDVAC, называли задачу сортировки данных наиболее характерной нечисловой задачей для вычислительных машин. В 1945 году Джон фон Нейман для тестирования ряда команд для EDVAC разработал программы сортировки методом слияния. В том же году немецкий инженер Конрад Цузе разработал программу для сортировки методом простой вставки. К этому времени уже появились быстрые специализированные сортировальные машины, в сопоставлении с которыми и оценивалась эффективность разрабатываемых ЭВМ. Первым опубликованным обсуждением сортировки с помощью вычислительных машин стала лекция Джона Мокли, прочитанная им в 1946 году. Мокли показал, что сортировка может быть полезной также и для численных расчетов, описал методы сортировки простой вставки и бинарных вставок, а также поразрядную сортировку с частичными проходами. Позже организованная им совместно с инженером Джоном Эккертом компания «Eckert–Mauchly Computer Corporation» выпустила некоторые из самых ранних электронных вычислительных машин BINAC и UNIVAC. Наряду с отмеченными алгоритмами внутренней сортировки, появлялись алгоритмы внешней сортировки, развитию которых способствовал ограниченный объём памяти первых вычислительных машин. В частности, были предложены методы сбалансированной двухпутевой поразрядной сортировки и сбалансированного двухпутевого слияния.

---

К 1952 году на практике уже применялись многие методы внутренней сортировки, но теория была развита сравнительно слабо. В октябре 1952 года Даниэль Гольденберг привёл пять методов сортировки с анализом наилучшего и наихудшего случаев для каждого из них. В 1954 году Гарольд Сьюворд развил идеи Гольденберга, а также проанализировал методы внешней сортировки. Говард Демут в 1956 году рассмотрел три абстрактные модели задачи сортировки: с использованием циклической памяти, линейной памяти и памяти с произвольным доступом. Для каждой из этих задач автор предложил оптимальные или почти оптимальные методы сортировки, что помогло связать теорию с практикой. Из-за малого числа людей, связанных с вычислительной техникой, эти доклады не появлялись в «открытой литературе». Первой большой обзорной статьёй о сортировке, появившейся в печати в 1955 году, стала работа Дж. Хоскена, в которой он описал всё имевшееся на тот момент оборудование специального назначения и методы сортировки для ЭВМ, основываясь на брошюрах фирм-изготовителей. В 1956 году Э. Френд в своей работе проанализировал математические свойства большого числа алгоритмов внутренней и внешней сортировки, предложив некоторые новые методы.

После этого было предложено множество различных алгоритмов сортировки: например, вычисление адреса в 1956 году; слияние с вставкой, обменная поразрядная сортировка, каскадное слияние и метод Шелла в 1959 году, многофазное слияние и вставки в дерево в 1960 году, осциллирующая сортировка и быстрая сортировка Хоара в 1962 году, пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера в 1964 году. В конце 60-х годов произошло и интенсивное развитие теории сортировки. Появившиеся позже алгоритмы во многом являлись вариациями уже известных методов. Получили распространение адаптивные методы сортировки, ориентированные на более быстрое выполнение в случаях, когда входная последовательность удовлетворяет заранее установленным критериям.

Что представляет собой алгоритм сортировки

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

---

Алгоритм сортировки — это порядок действий для упорядочения элементов в списке. Обычно говорят о сортировке записей (содержащих любые данные) по ключам – фрагментам этих записей, допускающих отношение упорядочения. Например, ключи могут быть числами (в этом случае используется естественный математический порядок возрастания или убывания чисел) или строковыми значениями (в этом случае упорядочение производится по алфавиту).

Наверно, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Возможно, нет. Однако, имея приблизительные характеристики исходных данных, можно подобрать метод, работающий оптимальным образом.

Оценка алгоритма сортировки.

Для того чтобы обоснованно сделать выбор метода сортировки, рассмотрим параметры, по которым будет производиться оценка алгоритмов.

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

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

• Устойчивость. Устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.

• Естественность поведения — эффективность метода при обработке уже

отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:

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

Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), то есть в данный момент мы «видим» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

---