Сортировка методом выбора на C#

Не так давно мы разбирали сортировку методом пузырька на языке C#. Теперь давайте рассмотрим сортировку выборкой.

Описание алгоритма:

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

Пример:

Сортировка методом выбора проходит следующим образом.

К примеру, у нас имеется массив 3 9 1 4 0

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

Затем мы меняем местами найденное минимальное число с элементом на нулевой позиции в массиве и “выкидываем” эту нулевую позицию из процесса сортировки.

Жирным шрифтом будет обозначаться нынешний минимальный элемент.

3 9 1 4 0

Нынешний минимальный элемент сравнивается с 9. Он меньше, чем 9, поэтому сравнивается со следующим элементом. 1 меньше, чем 3, следовательно, теперь 1 – это наш нынешний минимальный элемент.

3 9 1 4 0

Продолжаем сравнение. 1 меньше 4, но 0 меньше 1, значит теперь он считается минимальным элементом.

3 9 1 4 0

Мы прошли по массиву и нашли самый маленький его элемент.

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

0 9 1 4 3

Вторая итерация. Принимаем первый элемент среди оставшихся неупорядоченных чисел за минимальный и сравниваем его с остальными.

0 9 1 4 3

Единица меньше 9, теперь она минимальная.

0 9 1 4 3

Единица сравнивается с 4 и с 3, но все эти числа больше неё, следовательно, это и есть наш следующий минимальный элемент.

Мы меняем его местами с элементом на первой позиции массива и опять сокращаем количество шагов в итерации на 1.

0 1 9 4 3

Третья итерация. Таким же образом ищем следующее минимальное число.

0 1 9 4 3

Четвёрка меньше девятки.

0 1 9 4 3

Тройка меньше четвёрки. Мы обошли весь массив, значит 3 и является минимальными значением. Меняем его местами с элементном на второй позиции массива.

0 1 3 4 9

Четвёртая итерация. Сравниваем оставшиеся числа. Нынешнее минимальное число 4 меньше, чем 9, значит оно остаётся на своём месте, а так как у нас после него остаётся последнее число 9 в массиве, то оно, соответственно, является максимальным из всего массива. Сортировка окончена.

Таким образом у нас получается упорядоченный методом выбора массив:

0 1 3 4 9

Код программы:

В программе для начала создаём функцию сортировки.

В строках 7-14 мы ищем минимальный элемент массива. Происходит это так же, как описано в примере.

В строках 16-18 мы меняем местами элементы. В переменную temp записываем минимальный элемент массива. Затем на позицию минимального элемента записываем элемент, на чьё место он должен встать (на первой итерации – нулевая позиция, на второй итерации – первая, и так далее; это контролируется условием в строке 4), а затем, на эту самую позицию, которую мы освободили, вставляем значение из переменной temp.

В главную функцию main мы вернём уже упорядоченный массив (строка 20).

Теперь рассмотрим, что у нас будет в функции main.

В строках 3-10 мы просим пользователя ввести количество элементов массива и сами эти значения, и считываем их.

Затем вызываем функцию ViborSort(mas), куда передаём заполненный массив. Там он упорядочивается и возвращается. Нам остаётся только вывести его в в консоль, что мы и делаем в строках 12-17.

В консоли наша сортировка методом выбора будет выглядеть вот так:

Сортировка методом выбора на C#

Скачать программу “Сортировка методом выбора на C#” можно ниже:

Скачать исходник

 

Сортировка методом выбора на C#
5 (100%) 4 votes

Поделиться в соц. сетях:

2 комментария(ев) к статье “Сортировка методом выбора на C#

  1. Programmer_blog

    Здравствуйте. Можно ли утверждать, что сортировка методом выбора эффективнее, чем пузырьковая, рассмотренная ранее? – если можно, поясните почему, пожалуйста. :)

    1. admin

      Оба алгоритма имеют одинаковую вычислительную сложность (n * n). Единственный плюс сортировки пузырьком в том, что если массив уже отсортирован, то потребуется всего один проход функции для завершения работы алгоритма, а в случае с сортировкой методом выбора все равно будет произведено n * n операций.

Добавить комментарий для admin Отменить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">