C# Урок 10. Сортировка массива

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

Массив упорядочен по возрастанию, если выполняться условие:

a[0] ≤ a[1] ≤ a[2] ≤ ... ≤ a[n]

где n - верхняя граница индекса массива.

Метод выбора

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

1. Просматривая массив от первого элемента, найти (выбрать) минимальный элемент и поменять его с первым элементом (поместить минимальный элемент на место первого элемента, а первый — на место минимального).

2. Просматривая массив от второго элемента, найти (выбрать) минимальный элемент и поменять его со вторым элементом.

3. Выполнить описанные действия для остальных, за исключением последнего, элементов массива.

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

Листинг 10.1. Сортировка массива по возрастанию методом выбора

static void Main(string[] args)
{
int[] a; // массив
int k = 10; // размер массива

a = new int[k];
Console.Write("Введите элементы массива\n");

for ( int i = 0; i<k; i++)
{
Console.Write("{0} >", i);
a[i] = System.Convert.ToInt32(Console.ReadLine());
}

Console.Write("\nИсходный массив:");
for (int i = 0; i < k; i++)
Console.Write("{0} ", a[i]);

Console.WriteLine();
Console.Write("\nСортировка...\n");
for (int i = 0; i < k - 1; i++)
{
// просматривая массив с i-го элемента найти min элемент
int min = i;
for (int j = i; j < k; j++)
{
if (a[j] < a[min])
min = j;
}

// здесь min элемент найден
// поменять местами i-й и min элементы
int b = a[i];
a[i] = a[min];
a[min] = b;

// массив после очередного цикла поиска мин. элта
for (int l = 0; l < k; l++)
Console.Write("{0} ", a[l]);
Console.WriteLine();
}

// массив отсортирован
Console.Write("\nОтсортированный массив: ");
for (int i = 0; i < k; i++)
Console.Write("{0} ", a[i]);

Console.Write("\n\nPress any key...");
Console.ReadKey();
}

Метод обменов

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

Алгоритм сортировки можно описать так: каждый (текущий) элемент массива, начиная с первого до n-1 (n – количество элементов массива), сравнивается со следующим элементом, и если следующий элемент меньше текущего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива ("всплывают"), а элементы с большим значением продвигаются к концу массива или "тонут" (поэтому этот метод обмена иногда называют методом "пузырька"). Процесс просмотра и обменов повторяется n-1 раз, где n- количество элементов массива.

В листинге 10.2 представлена программа сортировки массива целых чисел по возрастанию методом обмена. Для демонстрации процесса сортировки после выполнения очередного цикла обменов программа выводит массив.

Листинг 10.2. Сортировка массива методом обменов (пузырька)

static void Main(string[] args)
{
int[] a; // массив
int n = 10; // размер массива
a = new int[n];

Console.Write("Введите элементы массива\n");
for (int i = 0; i < n; i++)
{
Console.Write("{0}>>", i);
a[i] = System.Convert.ToInt32(Console.ReadLine());
}

Console.Write("\nИсходный массив: ");
for (int i = 0; i < n; i++)
Console.Write("{0} ", a[i]);

Console.Write("\n\nСортировка...\n");

for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1; j++)
{
if (a[j + 1] < a[j])
{
// следующий элемент меньше текущего
// поменять местами j-й и j+1-й элементы массива
int b = a[j];
a[j] = a[j + 1];
a[j + 1] = b;
}
}

// массив после очередного цикла перестановок
for (int j = 0; j < n; j++)
Console.Write("{0} ", a[j]);

Console.WriteLine();
}

Console.Write("\n\nОтсортированный массив: ");
for (int i = 0; i < n; i++)
Console.Write("{0} ", a[i]);

Console.Write("\n\nPress any key...");
Console.ReadKey();
}

Предыдущий урок

Урок 9. Массивы

Литература

Культин Н. Б. C# для начинающих. Самоучитель с примерами и задачами для самостоятельного решения. эл. - 1 файл pdf : 130 c. Текст: электронный.

Культин Н.Б. Самоучитель C#. Текст: электронный (приложение для Android)

(с) Никита Культин, 2021.
Никакая часть публикации не может быть использована без разрешения автора.