3672

Алгоритми сортування в одновимірних масивах

Лекция

Информатика, кибернетика и программирование

Алгоритми сортування в одновимірних масивах Найпростіше завдання сортування полягає в упорядкуванні елементів масиву по зростанню або убуванню. Іншим завданням є впорядкування елементів масиву відповідно до деякого критерію. Звичайно як такий критер...

Украинкский

2012-11-05

42.5 KB

47 чел.

Алгоритми сортування в одновимірних масивах

Найпростіше завдання сортування полягає в упорядкуванні елементів масиву по зростанню або убуванню. Іншим завданням є впорядкування елементів масиву відповідно до деякого критерію. Звичайно як такий критерій виступають значення певної функції, аргументами якої виступають елементи масиву. Цю функцію прийнято називати функцією, що впорядковує.

Існують різні методи сортування. Будемо розглядати кожний з методів на прикладі завдання сортування по зростанню масиву з N цілих чисел.

Сортування вибором

Ідея методу полягає в тім, що перебуває максимальний елемент масиву й міняється місцями з останнім елементом (з номером N). Потім, максимум шукається серед елементів з першого до передостаннього й ставиться на N-1 місце, і так далі. Необхідно знайти N-1 максимум. Можна шукати не максимум, а мінімум і ставити його на перше, друге й так далі місце. Також застосовують модифікацію цього методу з одночасним пошуком максимуму й мінімуму. У цьому випадку кількість кроків зовнішнього циклу N div 2.

Обчислювальна складність сортування вибором - величина порядку N*N, що звичайно записують як O(N*N). Це порозумівається тим, що кількість порівнянь при пошуку першого максимуму дорівнює N-1. Потім N-2, N-3, і так далі до 1, разом: N*(N-1)/2.

Приклад 22.1.: Сортування вибором по зростанню масиву A з N цілих чисел.

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n + 2];

Random r = new Random();

int i;

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

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

for (i = n; i >= 2; i--)

{

int i1 = 1; //{ m - місце max }

for (int j = 2; j <= i; j++)

if (a[j] > a[i1]) i1 = j;

//міняємо місцями елементи з номером m і номером k}

int x = a[i1]; a[i1] = a[i]; a[i] = x;

for (int k = 1; k <= n; k++)

{

Console.Write(a[k] + " ");

}Console.WriteLine();

}

Console.ReadLine();

Приклад 22.2. : Те ж завдання з одночасним вибором max й min.

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n + 2];

Random r = new Random();

int i;

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

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

for (i = 1; i <= n/2 ; i++)

//{max й min шукаються серед елементів з i до n-i+1}

{

int i1 = i; //{ - місце max }

int i2 = i; //{ - місце min }

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

{

if (a[j] > a[i1]) i1 = j;

if (a[j] < a[i2]) i2 = j;

}

Console.WriteLine(a[i1] + " " + i1 + " " + a[i2] + " " + i2);

//міняємо місцями елементи з номером i1 і номером i}

int x = a[i2]; a[i2] = a[i]; a[i] = x;

//якщо max стояв на місці i, то зараз він на місці i2;

if (i1==i) i1=i2;

//міняємо місцями елементи з номером i1 і номером n-k+1

x = a[i1]; a[i1] = a[n - i + 1]; a[n - i + 1] = x;

for (int k = 1; k <= n; k++)

{

Console.Write(a[k] + " ");

}Console.WriteLine();

}

Сортування обміном (методом "пухирця")

Ідея методу полягає в тім, що послідовно рівняються пари сусідніх елементів масиву. Якщо вони розташовуються не в тім порядку, то робимо перестановку, міняючи місцями пари сусідніх елементів. Після одного такого проходу на останнім місці номер N виявиться максимальний елемент ("сплив" перший "пухирець"). Наступний прохід повинен розглядати елементи до передостаннього й так далі. Усього потрібно N-1 прохід. Обчислювальна складність сортування обміном O(N*N).

Приклад 22.3. Сортування обміном по зростанню масиву A з N цілих чисел. (Базовий варіант)

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n + 2];

Random r = new Random();

int i;

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

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

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

{

for (int j = 1; j <= n - 1; j++)

{

if (a[j] > a[j + 1])

{

int x = a[j]; a[j] = a[j + 1]; a[j + 1] = x;

}

}

for (int k = 1; k <= n; k++)

{

Console.Write(a[k] + " ");

} Console.WriteLine();

}

Console.ReadLine();

Можна помітити, що якщо при виконанні чергового проходу в сортуванні обміном не зроблений ні однієї перестановки, те це означає, що масив уже впорядкований. Таким чином, можна модифікувати алгоритм, щоб наступний прохід робився тільки при наявності перестановок у попередньому.

Приклад 22.4. : Сортування обміном з перевіркою факту перестановки.

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n + 2];

Random r = new Random();

int i;

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

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

int l = n - 1;

int f = 1;

while (f == 1)

{

f = 0;

for (int j = 1; j <= l; j++)

if (a[j] > a[j + 1])

{

int x = a[j]; a[j] = a[j + 1]; a[j + 1] = x; f = 1;

}

l = l - 1;

for (int k = 1; k <= n; k++)

{

Console.Write(a[k] + " ");

} Console.WriteLine();

}

Console.ReadLine();

Наступна модифікація алгоритму сортування обміном виходить при запам'ятовуванні місця останньої перестановки. Якщо при черговому проході останньою парою елементів, які помінялися місцями, були A[i] й A[i+1], то елементи масиву з i+1 до останнього вже коштують на своїх місцях. Використання цієї інформації дозволяє нам зробити кількість пар для наступного проходу рівним i-1.

Приклад 22.5. : Сортування обміном із запам'ятовуванням місця останньої перестановки.

Console.WriteLine("Введите число ");

int n = Int32.Parse(Console.ReadLine());

int[] a = new int[n + 2];

Random r = new Random();

int i;

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

{

a[i] = r.Next(100);

Console.Write(a[i] + " ");

}

Console.WriteLine();

int l = n - 1;

while (l>0)

{

int m = 0;

for (int j = 1; j <= l; j++)

if (a[j] > a[j + 1])

{

int x = a[j]; a[j] = a[j + 1]; a[j + 1] = x; m = j;

}

l = m - 1;

for (int k = 1; k <= n; k++)

{

Console.Write(a[k] + " ");

} Console.WriteLine();

}

Console.ReadLine();


 

А также другие работы, которые могут Вас заинтересовать

21717. Экономико-организационные проблемы разгрузки предприятий при дефиците мощности и прохождении максимумов нагрузки в энергосистеме 113.5 KB
  Экономикоорганизационные проблемы разгрузки предприятий при дефиците мощности и прохождении максимумов нагрузки в энергосистеме До настоящего времени работы по созданию экономически обоснованных рекомендаций по управлению электропотреблением промышленных предприятий практически не имели ни методической базы ни руководящих указаний позволяющих обеспечивать минимум экономических потерь от изменения режимов функционирования. Выполнение отмеченных условий связано с трудностями изза неопределенности а в отдельных случаях элементарного незнания...
21718. Задачи надёжности электроснабжения 203.5 KB
  Чтобы качественно сравнивать между собой события по степени их возможности нужно с каждым событием связать определенное число которое тем больше чем более возможно событие его вероятность. Найти вероятность исправной работы РП. Если вероятность одного события не изменяется от того произошло или не произошло другое событие то такие события называются независимыми и наоборот. Вероятность суммы n несовместных событий равна сумме вероятностей этих событий: где .
21719. Показатели надежности ЭМС 141 KB
  Вероятность безотказной работы ВБР– это вероятность того что при определенных условиях эксплуатации в заданном интервале времени не произойдет ни одного отказа. Кривые вероятности безотказной работы и вероятности отказов Вероятность отказа Qt– это вероятность того что при определенных условиях эксплуатации в заданном интервале времени произойдет хотя бы один отказ. Отказ и безотказная работа – события противоположенные и несовместимые 2 Частота отказов at– есть отношение отказавших изделий в единицу времени к первоначальному числу...
21720. Расчёт надежности при последовательном (основном) соединении элементов 225.5 KB
  С точки зрения надежности различают последовательные параллельные и системы со сложной структурой. Расчёт надежности при последовательном основном соединении элементов при таком соединении отказ технического изделия наступает при отказе одного из его узлов. Для повышения надежности систем и элементов применяют резервирование: Резервирование – это применение дополнительных средств иили возможностей с целью сохранения работоспособного состояния объекта при отказе одного или нескольких его элементов. Резервирование основано на...
21721. Модели отказов электроустановок 177.5 KB
  Вероятность безотказной работы такой системы определяется как вероятность безотказной работы всех элементов в течение времени t: где n – число элементов последовательно соединенной системы; –событие безотказной работы; – вероятность безотказной работы iго элемента. В случае невосстанавливаемых элементов вероятность отказа системы определяется как вероятность совпадения отказов или m элементов в течение расчётного времени. Если отказы одного элемента не зависят от отказов других элементов то формулы для оценки вероятности безотказной...
21722. МОДЕЛИ ОЦЕНКИ НАДЕЖНОСТИ ЭМС 117.5 KB
  Распределение экстремальных значений Пусть имеется случайная выборка объемом n взятая из бесконечной совокупности имеющей распределение Fx где х– непрерывная случайная величина.1 Так как разрушение материала связано с существованием наиболее слабой точки в работах по теории надежности рассматривается распределение экстремальных значений. Здесь будет рассмотрено распределение наименьших значений однако этот подход может быть использован и при выводе распределений наибольших значений. Функция распределения наименьших значений функция...
21723. Модели надёжности установок с восстановлением 310 KB
  Модели надёжности установок с восстановлением При экспоненциальном законе распределения времени восстановления и времени между отказами для расчёта показателей надёжности установки с восстановлением пригоден математический аппарат марковских случайных процессов. Дискретный случайный процесс называется марковском если все вероятностные характеристики будущего протекания этого процесса при зависят лишь от того в каком состоянии этот процесс находился в настоящий момент времени и не зависят от того каким образом этот процесс протекал до...
21724. Общие принципы определения ущерба от нарушений электроснабжения 80 KB
  Общие принципы определения ущерба от нарушений электроснабжения Проблема оценки ущерба от нарушений электроснабжения вызываемых отказами электрооборудования возникает как при проектировании так и при эксплуатации энергетических объектов. При проектировании потребность в характеристике ущерба ощущается как правило когда определяется экономическая эффективность капитальных вложений при выборе вариантов технических и организационнохозяйственных решений влияющих на степень надежности электроснабжения потребителей. При эксплуатации...
21725. Технико-экономическая оценка последствий от нарушений электроснабжения объектов производственных систем 240 KB
  Техникоэкономическая оценка последствий от нарушений электроснабжения объектов производственных систем 8.1 Модель поведения участка производства при нарушениях его электроснабжения По характеру последствий все отказы участков производственной системы можно разделить на три группы: 1 не обесценивающие производственную продукцию; 2 частично обесценивающие; 3 полностью обесценивающие. В этом случае длительность простоя производственного участка соответствует длительности нарушения электроснабжения . Большинство нарушений электроснабжения...