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

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


Поиск k-го по величине элемента массива

Поиск:
Алгоритм ищет в массиве M, состоящем из n элементов, k-ый по величине элемент. Эту задачу можно решить упорядочив массив и взяв элемент M[k], но упорядочивание имеет скорость не лучше O(n·log(n)), данный же алгоритм, и это можно достаточно строго доказать, имеет скорость работы O(n).

Каждый шаг работы алгоритма состоит из двух этапов и приводит к сокращению числа рассматриваемых элементов n.

Первый этап. Поиск некоторого "среднего" элемента в массиве M, который осуществляется следующим образом: разобьем массив М на части по 5 элементов в каждой и упорядочим подмассивы по неубыванию. Из средних элементов подмассивов (элементов с номером 3) составим новый массив, с которым проделаем то же самое, будем осуществлять этот алгоритм пока не останется один элемент, который мы помещаем в переменную med и переходим ко второму этапу.

Второй этап. Просматривая элементы массива M, перегруппируем их так, чтобы вначале шли элементы меньшие или равные med, а затем большие med. Допустим первая часть массива содержит j элементов (соответственно вторая n-j). Если k < j, то искомый элемент содержиться в первой половине массива, тогда полагаем n = j и возвращаемся к первому этапу. Если k > j, то искомый элемент находится во второй части массива, тогда переносим n-j последних элементов в начало массива, полагаем n = n-j, k = k-j и возращаемся к первому этапу.

Продолжаем до того момента пока n не станет меньше 5, когда это произойдет просто упорядочим оставшиеся элементы (их меньше 5) и элемент с номером k, будет искомым.

Принцип построения алгоритма прислан riiki, но он предлагал использовать рекурсию и два дополнительных массива, надеюсь, что то что я избавился от рекурсии не сократит скорость работы.
Автор: riiki@7ka.mipt.ru






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

 

 

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


Популярные:
  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. Проверить дубляжи в столбце


 

 

 
 
На главную