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

Фриланс
Новости
Статьи
   
Рубрики:


Сортировка поиском минимума

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

Реализация алгоритма

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

После k-го хода результат содержит k чисел, а исходный набор — N-k. Договоримся, что текущий результат мы будем хранить в первых k элементах массива. Разберем подробнее, как это можно реализовать. Для этого вновь обратимся к нашему примеру:

3, 6, 1, 2, 9, 5.

На первом шаге мы находим наименьшее число — 1 — и должны переместить его на первое место. Но там уже записано число 3, куда же его деть? Ответ прост: на место числа 1. Таким образом, мы просто меняем местами два элемента массива:

1 | 6, 3, 2, 9, 5.

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

На втором шаге мы находим минмиальное число в правой части — среди элементов массива со 2-го по 6-й (в общем случае — по N-й) — и меняем его местами с числом, стоящим на втором месте:

1, 2 | 3, 6, 9, 5.

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

1, 2, 3 | 6, 9, 5.

Попробуем записать действия, которые нам предстоит проделать на шаге с номером k. Сначала нам нужно найти наименьшее среди чисел, записанных в k, k+1, ..., N позициях массива. После этого нам нужно поменять этот элемент с k-м.

Сколько таких шагов нужно сделать, чтобы полностью отсортировать массив? Напрашивается ответ "N", но не будем торопиться. Пусть сделан N-1 шаг. Тогда в правой, неотсортированной части массива останется одно число. Какое это число? Ясно, что это самое большое число в массиве. Где оно в итоге должно оказаться? На последнем месте в массиве. Но оно уже и так там! Поэтому N-й шаг алгоритма выполнять не нужно.

Таким образом, алгоритм можно записать следующим образом (на некотором условном языке, который мы нигде не будем описывать, но всюду будем использовать: надеемся, он будет интуитивно понятен всем читателям):

Код


for k:=1 to N-1 do begin
  Выполнить k-й шаг алгоритма
end



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

Код

for k:=1 to N-1 do begin
  Найти наименьший среди элементов массива с номерами k..N
  Поменять его местами с k-м элементом
end


Будем считать, что массив называется a, и напишем соответствующий код, вспомнив, как искать минимальный элемент и как менять два элемента местами:
Код


for k:=1 to N-1 do begin
  min:=k;
  for i:=k+1 to N do
    if a[i]<a[min] then min:=i;
  temp:=a[min]; a[min]:=a[k]; a[k]:=temp;
end


Алгоритм сортировки поиском минимума реализован.

Анализ работы алгоритма

Предположим, что кто-то придумал еще один алгоритм сортировки. Как сравнить его с нашим. Чем он может быть лучше ли хуже? Ясно, что результаты работы обоих алгоритмов обязаны совпадать, в противном случае можно сказать, что один из них работает неправильно (неоптимально). Таким образом, алгоритмы надо сравнивать по другим параметрам. Такими параметрами, в первую очередь, являются время работы алгоритма и требуемая для его работы память. Поскольку сравнивать наш алгоритм нам пока не с чем, попробуем просто оценить его по указанным параметрам.

Поскольку время работы алгоритма зависит от того, на каком языке программирования был написан код, как он был скомпилирован, на каком компьютере выполняется и т. д., то мы будем считать не время работы алгоритма, а количество операций, выполняемых алгоритмом. Наш алгоритм N-1 раз выполняет поиск минимума - в первый раз минимум ищется среди N элементов, и на это требуется порядка N операций, второй раз - среди N-1 элемента, и т. д. Таким образом, на поиск минимума всего потребуется N + (N-1) + ... + 3 + 2 = (N+2)(N-1)/2 операций, что примерно равно N2/2 операций. На перестановку минимумов на свои места требуется порядка N операций. При больших N N2/2 много больше N, поэтому операциями перестановки максимума можно пренебречь, и сказать, что наш алгоритм работает за время порядка N2/2, где N - количество чисел. Алгоритмы, которые требуют порядка CN2/2 операций (где С - некоторая константа, не зависящая от N), называют квадратичными. Посмотрим, как растет величина N2 с ростом N:

N    10     1,000      10,000         1,000,000
N2  100 1,000,000 100,000,000 1,000,000,000,000

Видно, что уже при N равном миллиону количество операций достигает триллиона!

Теперь посмотрим, как используется память. Мы не используем никакой дополнительной памяти, кроме той, в которую записан исходный массив. Казалось бы, меньше памяти использовать нельзя! Это не совсем точное утверждение.






Просмотров: 4320

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную