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

      Комментарии к записи Сортировка методом простого выбора отключены

Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.

int i,min,n_min,j;

for(i=0;i

{

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

for(j=i+1;j

if(a[j]

{

min=a[j];

n_min=j;

}

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

a[i]=min;

}

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

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

for(int i=1;i

for(int j=n-1;j=i;j—)

if(a[j]

{

int r=a[j];

a[j]=a[j-1];

a[j-1]=r;}

}

Поиск в отсортированном массиве

В отсортированном массиве используется дихотомический (бинарный) поиск. При последовательном поиске требуется в среднем n/2 сравнений, где n – количество элементов в массиве. При дихотомическом поиске требуется не более m сравнений, если n- m-ая степень 2, если n не является степенью 2, то n

Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части массива находится нужный элемент Х. Так как массив упорядочен, то, если a[S]

L S R

Console.WriteLine(Введите элемент для поиска);

buf=Console.ReadLine();

int x = int.Parse(buf);

int l = 0, r = n — 1, s;

do

{

s = (l + r) / 2;//средний элемент

if (c[s]x) l = s + 1;//перенести леую границу

else r = s;//перенести правую границу

} while (l != r);

if (c[l] == x) Console.WriteLine(элемент +c[l]+, его номер= +(l+1));

else Console.WriteLine(Элемент не найден);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Варианты

Вариант Удаление Добавление Перестановка Поиск Сортировка
Максимальный элемент К элементов в начало массива Перевернуть массив Первый четный Простой обмен
Минимальный элемент К элементов в конец массива Сдвинуть циклически на M элементов вправо Первый отрицательный Простой выбор
Элемент с заданным номером N элементов, начиная с номера К Сдвинуть циклически на M элементов влево Элемент с заданным ключом (значением) Простое включение
Nэлементов, начиная с номера K Элемент с номером К Поменять местами элементы с четными и нечетными номерами Элемент равный среднему арифметическому элементов массива Простой обмен
Все четные элементы К элементов в начало массива Четные элементы переставить в начало массива, нечетные — в конец Первый четный Простой выбор
Все элементы с четными индексами К элементов в конец массива Поменять местами минимальный и максимальный элементы Первый отрицательный Простое включение
Все нечетные элементы N элементов, начиная с номера К Положительныеэлементы переставить в началомассива, отрицательные — вконец Элемент с заданным ключом (значением) Простой обмен
Все элементы с нечетными индексами Элемент с номером К Перевернуть массив Элемент равный среднему арифметическому элементов массива Простой выбор
Все элементы больше среднего арифметического элементовмассива К элементов в начало массива Сдвинуть циклически на M элементов вправо Первый четный Простое включение
Максимальный элемент К элементов в конец массива Сдвинуть циклически на M элементов влево Первый отрицательный Простой обмен
Минимальный элемент N элементов, начиная с номера К Поменять местами элементы с четными и нечетными номерами Элемент с заданным ключом (значением) Простой выбор
Элемент с заданным номером Элемент с номером К Четные элементы переставить в начало массива, нечетные — в конец Элемент равный среднему арифметическому элементов массива Простое включение
Nэлементов, начиная с номера K К элементов в начало массива Поменять местами минимальный и максимальный элементы Первый четный Простой обмен
Все четные элементы К элементов в конец массива Положительныеэлементы переставить в началомассива, отрицательные — вконец Первый отрицательный Простой выбор
Все элементы с четными индексами N элементов, начиная с номера К Перевернуть массив Элемент с заданным ключом (значением) Простое включение
Все нечетные элементы Элемент с номером К Сдвинуть циклически на M элементов вправо Элемент равный среднему арифметическому элементов массива Простой обмен
Все элементы с нечетными индексами К элементов в начало массива Сдвинуть циклически на M элементов влево Первый четный Простой выбор
Все элементы больше среднего арифметического элементовмассива К элементов в конец массива Поменять местами элементы с четными и нечетными номерами Первый отрицательный Простое включение
Максимальный элемент N элементов, начиная с номера К Четные элементы переставить в начало массива, нечетные — в конец Элемент с заданным ключом (значением) Простой обмен
Минимальный элемент Элемент с номером К Поменять местами минимальный и максимальный элементы Элемент равный среднему арифметическому элементов массива Простой выбор
Элемент с заданным номером К элементов в начало массива Положительныеэлементы переставить в началомассива, отрицательные — вконец Первый четный Простое включение
Nэлементов, начиная с номера K К элементов в конец массива Перевернуть массив Первый отрицательный Простой обмен
Все четные элементы N элементов, начиная с номера К Сдвинуть циклически на M элементов вправо Элемент с заданным ключом (значением) Простой выбор
Все элементы с четными индексами Элемент с номером К Сдвинуть циклически на M элементов влево Элемент равный среднему арифметическому элементов массива Простое включение
Все нечетные элементы К элементов в начало массива Поменять местами элементы с четными и нечетными номерами Первый четный Простой обмен

Методические указания

1. Используются массивы, под которые количество памяти выделяется в процессе выполнения программы:

Console.Write(Введите количество элементов в массиве );

buf=Console.ReadLine();

n=int.Parse(buf);

int [] arr=new int[n];

2. Формирование массива осуществляется с помощью датчика случайных чисел. Для этого

используется класс Random.

Random a=new Random(0);//инициализация ДСЧ

. . . .

arr[i] = a.Next(0,100);//генерация элемента массива

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

for ( i = 0; in; i++) Console.Write(arr[i] +);

Console.WriteLine();

6. Содержание отчета:

1) Постановка задачи (общая и конкретного варианта).

2) Анализ поставленного задания: определить к какому классу задач относится задача и объяснить почему.

3) Алгоритмы для каждой подзадачи.

4) Текст программы.

5) Результаты тестов (тесты, ЧЯ, МГТ)

Статьи к прочтению:

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


Похожие статьи: