Сортировка методом простого выбора

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

На рис. показан пример сортировки методом выбора. Среди пяти целых чисел выбирается наибольшее - число 37, которое меняется местами с последним элементом массива - числом 13. (Числа, стоящие на правильных местах, выделены полужирным шрифтом. Затем среди оставшихся четырех чисел снова выбирается наибольшее - число 29, - которое меняется местами с предпоследним элементом - числом 13. Обратите внимание, что следующий выбор - число 14- уже стоит на правильном месте, однако алгоритм игнорирует этот факт и выполняет фиктивную перестановку числа 14 на одном и том же месте. В принципе намного эффективнее выполнять фиктивные перестановки, чем каждый раз проверять, нужна перестановка или нет. В заключение выбирается число 13, которое меняется местами со вторым элементом массива - числом 1о. Теперь массив упорядочен по возрастанию.

int i,max, n_max,j;

for(i=0;i<n-1;i++)

{

max=a[i]; n_max=i; //поиск максимального

for(j=i+1; j<n; j++)

if(a[j]>max)

{

max=a[j];

n_max=j;

}

a[n_max]=a[i]; //обмен

a[i]=max;

}

Постановка задачи

1. Сформировать массив из n элементов с помощью датчика случайных чисел (n задается пользователем с клавиатуры).

2. Распечатать полученный массив.

3. Выполнить удаление указанных элементов из массива.

4. Вывести полученный результат.

5. Выполнить добавление указанных элементов в массив.

6. Вывести полученный результат.

7. Выполнить перестановку элементов в массиве.

8. Вывести полученный результат.

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

10. Вывести полученный результат.

11. Выполнить сортировку массива указанным методом.

12. Вывести полученный результат.

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

14. Вывести полученный результат.

При решении задач использовать псевдодинамические массивы.

Варианты

Не нашли, что искали? Воспользуйтесь поиском: