Сортировка данных в одномерном массиве

Процедура упорядочивания структур данных по некоторому признаку или ключу называется сортировкой. Основное требование к сортировке массивов – экономичное исполь­зование памяти. Есть сортировка включениями, выбором и обменом, сортировка с разделением.

Сортировка простыми включениями. Элементы условно разделяют на готовую последовательность и входную последовательность. На первом шаге i=2, затемэто значение увеличивается на единицу на последующих шагах. На каждом из шагов выбирается первый элемент входной последовательности и передается в готовую последовательность с помощью вставки (включения) его на подходящее место в соответствии с функцией упорядочения. Процесс продолжается до тех пор, пока величина i не станет равной n. Для поиска подходящего места можно “просеивать” x, сравнивая его с очередным элементом. При просеивании предполагается, что если очередной элемент вектора W[I] >= X, то W[I] сдвигается на одну позицию направо (при первой проверке – на место X). Затем X либо вставляется на “освободившееся” место, либо сравнивается с очередным левым элементом вектора. Просеивание может закончиться при двух различных условиях (найден элемент w_k с ключом меньшим, чем ключ w_i или достигнут левый конец готовой последовательности). В общем случае сортировка включениями оказывается не очень эффективным методом, так как включение элемента связано со сдвигом всех предшествующих элементов на одну позицию, а эта операция неэкономна.

Воснове сортировки простым выбором лежит просмотр последовательности с целью выбора элемента с наименьшим ключом, после чего он меняется местами с первым элементом. Эти операции повторяются с оставшимися n-1, затем n-2 элементами и так далее, пока не останется только один элемент – наибольший. Рассматриваемый метод в определенном смысле противоположен сортировке простыми включениями. Сортировка простым выбором предпочтительнее сортировки простыми включенями кроме случая, когда ключи заранее рассортированы или почти рассортированы. Тогда сортировка простыми включениями работает несколько быстрее.

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

Сортировка с разделением является одним из лучших методов, он назван быстрой сортировкой.

Быстрая сортировка основана на том, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Для этого необходимо сначала поменять местами самый левый и самый правый элементы и постепенно продвигаться с двух концов к середине. Этот пример позволяет предложить следующую процедуру: выбрать случайным образом какой-то элемент (пусть x) и просматривать массив, двигаясь слева направо, пока не найдется элемент а_i > x, а затем просматривать его справа налево, пока не найдется элемент а_j < x. Затем, поменяв местами эти два элемента и продолжить процесс "просмотра с обменом", пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую – с ключами меньшими, чем x, и правую – с ключами большими x.