Сортировка.

Поиск наименьшего элемента массива.

Ищет наименьший элемент в массиве простым перебором. Если заменить знак "", то можно искать наибольший элемент. Наверх

Сортировка массива по возрастанию.

Это наиболее естественный алгоритм упорядочивания.

Допустим, что элементы a1,...,ai-1 уже упорядочены, тогда среди оставшихся (ai,...,an) находим минимальный элемент и меняем его местами с i-тым элементом. И т.д. пока массив не будет полностью упорядочен.

Благодарю Alex Maximenko за то, что он прислал мне этот алгоритм. Наверх

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

Последовательно просматриваем числа a1,...,an находим наименьшее i такое, что a i > ai+1. Поменять ai и ai+1 местами,возобновить просмотр с элемента ai+1 и т.д. Тем самым наибольшее число передвиниться на последнее место. Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра в котором участвовали только первый и второй элементы. Наверх

Сортировка массива по возрастанию (метод простых вставок).

Последовательно просматриваем a2,...,an и каждый новый элемент ai вставляем на подходящее место в уже упорядоченную совокупность a1,...,ai-1. Это место определяется последовательным сравнением ai с упорядоченными элементами a1,...,ai-1. Наверх

Сортировка массива по возрастанию (метод бинарных вставок).

Этот алгоритм представляет из себя оптимизированную версию предыдущего, отличие заключается в том, что при поиске место, на которое надо вставить элемент ai в уже упорядоченную совокупность a1,...,ai-1, определяется алгоритмом деления пополам (отсюда и название алгоритма "бинарные вставки" здесь понимаем как "вставка делением пополам"). Наверх

Сортировка массива методом Шелла.

Данный алгоритм прислан мне Широковым А.В за что ему большое спасибо. Присылайте больше и чаще.

Описывать алгоритм не буду, смотрите блок-схему алгоритм простой как все гениальное. Наверх

Сортировка массива по возрастанию (метод Уильяма Флойда, бинарных деревьев).

Алгоритм основан на представлении массива в виде бинарного дерева, обладающего особыми свойствами. В памяти компьютера все элементы массива расположены последовательно, структура же дерева определяется следующим образом: будем считать, что i элемент массива ("предок") имеет два элемента потомка с номерами 2i и 2i+1. Дерево имеет нормальную форму, если любой элемент предок больше своих потомков.

Для понимания алгоритма рассмотрите приведенную блок-схему. Из свойств алгоритма стоит заметить, что он дает стабильно хорошую скорость упорядочивания (порядка n log(n)), вне зависимости от того с каким массивом работает, и поэтому используется в случаях когда необходимо гарантировано упорядочить массив за короткое время. Наверх

Сортировка массива по возрастанию (метод фон Неймана, слияний).

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

Алгоритм дает хорошие показатели по скорости работы, даже в сравнении с сортировкой методом бинарных деревьев. Единственный недостаток - необходимость использовать дополнительный массив того же размера.

Реализацию данного алгоритма мне прислал Alex Kochnev. Наверх

Поиск 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, но он предлагал использовать рекурсию и два дополнительных массива, надеюсь, что то что я избавился от рекурсии не сократит скорость работы. Наверх