Сортировка с помощью прямого выбора

При сортировке с помощью прямого выбора массив также делится на две части: отсортированную, или «готовую», последовательность и неотсортированную, или «исходную» -ah ..., а„.

Метод прямого выбора в некотором смысле противоположен методу прямого включения. При прямом включении на каждом шаге рассматриваются только один (первый) элемент исходной последовательности и все элементы готовой последовательности. При этом отыскивается точка включения этого элемента в «готовую» последовательность так, чтобы при вставке не нарушить ее упорядоченности.

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

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

Алгоритм сортировки с помощью прямого выбора можно описать следующим образом:

  • 1) из всего массива выбирается элемент с наименьшим значением;
  • 2) он меняется местами с первым элементом а
  • 3) затем этот процесс повторяется с оставшимися п— 1 элементами, п - 2 элементами и т. д. до тех пор, пока не останется один элемент с наибольшим значением.

Рассмотрим несколько первых шагов алгоритма сортировки с помощью прямого выбора на примере упорядочивания по возрастанию следующего массива:

На первом шаге готовая последовательность не содержит ни одного элемента. Выбираем наименьший элемент из исходной последовательности, куда пока что входят все элементы массива. Таким элементом является второй элемент массива, значение которого - 12. Он меняется местами с первым элементом.

Теперь готовая последовательность включает в себя один элемент - 12. На рис. 3.3, иллюстрирующем текущее состояние массива, готовая последовательность подчеркнута сплошной линией. Наименьший элемент исходной последовательности - 20, он должен занять место второго элемента. Оба эти элемента выделены на рис. 3.2 полужирным шрифтом.

На втором шаге готовая последовательность состоит уже из двух элементов: 12 и 20. Наименьший элемент исходной последовательности 28. Он является третьим элементом массива и именно эту позицию он должен занять. Поэтому на рис. 3.4 полужирным шрифтом выделен только один данный элемент.

Первый шаг алгоритма сортировки с помощью прямого выбора

Рис. 3.3. Первый шаг алгоритма сортировки с помощью прямого выбора

Второй шаг алгоритма сортировки с помощью прямого выбора

Рис. 3.4. Второй шаг алгоритма сортировки с помощью прямого выбора

На рис. 3.5 наглядно показаны все шаги алгоритма сортировки с помощью прямого выбора: отмечены готовые последовательности и переставляемые элементы.

Пример сортировки с помощью прямого выбора

Рис. 3.5. Пример сортировки с помощью прямого выбора

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

В случае изначально упорядоченных элементов число перестановок М минимально:

Если же первоначально элементы располагались в обратном порядке, число перестановок будет максимальным:

В общем случае алгоритм с прямым выбором, как правило, предпочтительнее алгоритма прямого включения. Однако если элементы в начале упорядочены или почти упорядочены, алгоритм с прямым включением выполнит сортировку быстрее.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >