Шымкент 2022

жүктеу/скачать 1,44 Mb.

бет	14/43
Дата	28.03.2023
өлшемі	1,44 Mb.
	#76860

1 ... 10 11 12 13 14 15 16 17 ... 43

Сортировать элементы массива

Алгоритмы и массивы
Во многих задачах представление данных в виде массива значительно упрощает ее решение. Некоторые задачи вам знакомы из курса «Высшая математика», например, вычисление многочлена.

функция называется многочленом Pn(x) степени n. Значение ak здесь называется полиномиальным коэффициентом и может быть выражено в виде одномерного массива из n+1 элементов.
Зная массив коэффициентов полинома Pn(x), можно вычислить значение полинома в любой точке x. Обычно вычисление многочлена в точке x связано с реализацией некоторых алгоритмов, например, алгоритма Горнера, метода равного деления отрезка (если значение многочлена на концах отрезка имеет разный знак) , метод итераций, методы Ньютона, Лагранжа и др. Все эти алгоритмы связаны с обработкой массива полиномиальных коэффициентов.
В информатике есть свои проблемы, которые требуют представления данных в виде массива. Эта обработка данных имеет свои алгоритмы. Среди множества алгоритмов обработки данных выделяют алгоритмы сортировки (упорядочивания данных по какому-либо признаку) и поиска (выявления элемента данных по заданному признаку).
Алгоритм (метод) решения математических задач рассматривается в курсе «Высшая математика», поэтому в данной лекции рассматриваются только некоторые алгоритмы сортировки и поиска данных.
Сортировать элементы массива
В этом разделе мы рассмотрим алгоритмы и программные реализации только двух методов сортировки элементов массива.
Алгоритм сортировки по методу выбора. При методе выбора элементов массива алгоритм сортировки по убыванию предполагает следующие операции.
Считаем первый элемент массива, и сравниваем его значение с остальными элементами массива по очереди (от 2-го до последнего элемента). Если встречается элемент с большим значением, он заменяется первым элементом. Первая проверка массива приводит к тому, что первый элемент имеет наибольшее значение.
Затем смотрим на второй элемент, сравнивая его значение с остальными элементами массива по очереди (от 3-го до последнего элемента). В результате повторной проверки массива определяем значение второго элемента отсортированного массива. Таким образом, проверка повторяется до последнего элемента массива, при этом последняя проверка сравнивает только первый элемент массива с последним элементом массива.
Значение элементов результирующего массива располагается в порядке убывания.
Если количество элементов массива равно N, количество операций сравнения (ОС), выполняемых в алгоритме, рассчитывается следующим образом:
К.О. = (N-1)+(N-2)+(N-3)+ . . . + 2 +1=N·(N-1)/2 (7)
Это выражение описывает вычислительную эффективность алгоритма.
Задача 6.1. Создайте массив a из 11 случайных целых чисел в диапазоне от минус 50 до 50. Это должно быть выпущено. Отсортируйте элементы массива в порядке убывания и создайте новый массив.
Рассмотрим программную реализацию алгоритма сортировки элементов массива по убыванию.
Кодпрограммы:
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{
int i, j, b;
int[] a = new int[11];
Randomrnd = newRandom();
// создать и отобразить массив
Console.Write("Massivti syriptaganga dein: ");
for (i = 0; i <= 10; i++)
{
a[i] = rnd.Next() % 101 - 50;
Console.Write(" {0}", a[i]);
}
Console.WriteLine();
//сортировать элементы массива с помощью метода select
for (i = 0; i <= 9; i++)
for (j = i + 1; j <= 10; j++)
if (a[i] < a[j])
{ b = a[i]; a[i] = a[j]; a[j] = b; }
//дляотображениямассивапослесортировки
Console.Write("Massivti syriptagannan kein: ");
for (i = 0; i <= 10; i++)
Console.Write(" {0}", a[i]);
Console.WriteLine();
Console.ReadLine();
}
}
}

Работа программы:

Massivti syriptaganga dein: 11 16 47 9 5 14 41 18 -2 -31 49
Massivti syriptagannan kein: 49 47 41 18 16 14 11 9 5 -2 -31
6.2.2 Алгоритм шифрования «пузырь». Алгоритм попадания методом «пузырь» в порядке роста элементов массива рассматривает размещение следующих действий.
Сравниваем первый элемент массива со вторым, и если первый больше, то они меняются местами. После этого вторым элементом массива обычно являются салыстырылады, если егерский элемент улькен, то орындарын алмастырады жане и т. д.
В результате первого «сканирования» массива в конец записывается наибольшее значение элемента массива.
Снова берем первый элемент массива и сравниваем его со вторым элементом — повторяем весь процесс до элемента перед последним элементом массива — создаем его значение.
Это повторяется до последней операции сравнения.
Таким образом, значение элементов массива сортируется по возрастанию.
Алгоритмы «пузырькового» и селективного методов имеют одинаковую вычислительную эффективность.
В качестве примера рассмотрим предыдущую задачу 6.1.
Рассмотрим программную реализацию алгоритма сортировки элементов массива по убыванию методом «Пузырька».
Код программы:
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{
int i,j,b;
int[] a = new int[11];
Random rnd = new Random();
// создатьиотобразитьмассив
Console.Write("Massivti syriptaganga dein: ");
for (i = 0; i <= 10; i++)
{
a[i] = rnd.Next()%101 - 50;
Console.Write(" {0}", a[i]);
}
Console.WriteLine();
// Сортировка элементов массива методом «пузырька»

for (i=0; i<=9; i++)

for (j=0; j<=9-i; j++)
if (a[j]{ b=a[j];a[j]=a[j+1];a[j+1]=b;}
// сұрыптауданкейінмассивтіэкранғашығару
Console.Write("Massivti syriptagannan kein: ");
for (i=0; i<=10; i++)
Console.Write(" {0}", a[i]);
Console.WriteLine();
Console.ReadLine();
}
}
}
Работа программы:
Massivti syriptaganga dein: -26 -19 32 35 -19 -44 -35 36 10 -49 -5
Massivti syriptagannan kein: 36 35 32 10 -5 -19 -19 -26 -35 -44 -49

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

Если вы хотите познакомиться с другими алгоритмами сортировки, рекомендуем книгу Д. Кнута "Искусство компьютерного программирования", том 3 для вопросов "сортировка и поиск", 843 страницы.

жүктеу/скачать 1,44 Mb.

Достарыңызбен бөлісу:

1 ... 10 11 12 13 14 15 16 17 ... 43