3672

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

Лекция

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

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

Украинкский

2012-11-05

42.5 KB

48 чел.

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

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

Існують різні методи сортування. Будемо розглядати кожний з методів на прикладі завдання сортування по зростанню масиву з 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();


 

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

42770. Розрахунок фізичних властивостей вільного та супутнього вуглеводневих газів одного з родовищ України за їх компонентним складом 1.97 MB
  Процес експлуатації нафтових і газових свердловин вимагає виконання низки розрахунків фізичних властивостей компонентів, що видобуваються, які істотно залежать від термобаричних умов, за яких вони знаходяться.
42771. Технология производства и характеристики качества стального гнутого швеллера 100x80x3,0мм из стали марки Ст3пс 391.61 KB
  В наибольшей степени этим требованиям соответствуют стальные конструкции выполненные из холодногнутых профилей ХГП так как данный вид профилей обладает широкими конструктивными достоинствами: высокая точность размеров хорошее качество поверхности повышенное сопротивление различного рода нагрузкам обеспечивают преимущества холодногнутых профилей перед горячекатаными. Одной из разновидностью сортовых гнутых профилей является швеллер. Механические свойства гнутых профилей определяют на заготовке в соответствии с ГОСТ 16523[10]. На...
42772. ТРАНСПОРТНЫЙ НАЛОГ: ОБЩАЯ ХАРАКТЕРИСТИКА И ОСОБЕННОСТИ ИСЧИСЛЕНИЯ И ВЗИМАНИЯ С ФИЗИЧЕСКИХ ЛИЦ НА ТЕРРИТОРИИ ИРКУТСКОЙ ОБЛАСТИ 881.15 KB
  Налогоплательщики транспортного налога Объект налогообложения транспортного налога Налоговые ставки транспортного налога Транспортный налог является основным источником финансирования дорожной отрасли, и от своевременности его поступления напрямую зависят сроки и качество исполнения строительных программ
42773. Социальная реабилитация инвалидов и методика её осуществления 441.99 KB
  Сущность и содержание социальной реабилитации Основные цели и задачи социальной реабилитации Принципы социальной реабилитации Инвалиды составляют особую категорию населения, численность которой постоянно увеличивается. Мировым сообществом социальная защита инвалидов рассматривается как проблема первостепенной важности.
42774. Проектирование системы теплоснабжения промышленного предприятия 219.1 KB
  Определение количества теплоты на подогрев воды для горячего водоснабжения Выбор основного и вспомогательного оборудования системы транспорта теплоты Выбор основного и вспомогательного оборудования источника теплоты.Определение потребности в топливе для производства теплоты.
42775. Организация работы коктейль-бара «Малибу» 804 KB
  Целью работы является рассмотрение вновь созданного коктейль - бара на 50 посадочных мест. Моему коктейль-бару я решил дать название «Малибу», так как моим основным спонсором является «Allied Distillers Limited»
42776. Компьютерная реализация решения инженерной задачи по решению дифференциальных уравнений в частных производных 1.38 MB
  Микроэлектроника является одной из наиболее динамично развивающихся и востребованных отраслей науки и техники. Элементы современных СБИС и микрооптикоэлектромеханических систем (МОЭМС) представляют собой сложные структуры, в основу функционирования которых положены разнообразные физические эффекты. Разработка подобных элементов практически невозможна без решения уравнений математической физики, представляющих
42777. Разработка технологического процесса механической обработки шкива в условиях ЗАО «МРК» 190.3 KB
  Технический прогресс в машиностроении характеризуется как улучшением конструкций машин, так и непрерывным технологии их производства. Развитие новых прогрессивных технологических процессов обработки способствует конструированию современных машин и снижению их себестоимости. Актуальной является задача повышения качества выпускаемых машин и, в первую очередь, их точности
42778. Особенности развития силовых способностей у школьников старшей возрастной группы 351.46 KB
  Динамика силовых качеств детей старшего школьного возраста под воздействием занятий физическими упражнениями. Данный режим работы мышц имеет место в силовых упражнениях с преодолением внешнего отягощения штанги гирь гантелей отягощений на блочном устройстве. Величина прикладываемой к снаряду силы при выполнении упражнения в изотоническом режиме изменяется по ходу траектории движения так как изменяются рычаги приложения силы в различных фазах движений. Упражнения со штангой или другим аналогичным снарядом с высокой скоростью...