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();


 

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

52123. Решение задач с помощью производной 63 KB
  Активизировать познавательную деятельность учащихся путем решения задач с практическим содержанием. Оборудование: Портреты ученых Карточки с заданиями для устных упражнений Таблица Чертежи к задачам математические модели Минизадачники Ход урока В мире не происходит ничего в чем бы ни был виден смысл какогонибудь максимума или минимума Леонард Эйлер I. Выдающиеся ученые: француз Пьер Ферма 16011665 англичанин Исаак Ньютон 16431727 немец Готфрид Лейбниц16461716 француз Жозеф Лагранж 17361813...
52124. Розвязування систем рівнянь методом заміни змінної 4.01 MB
  Мета: освітня: формувати поняття однорідного многочлена симетричного многочлена; формувати умінь і навичок розвязування систем рівнянь методом заміни змінної та вироблення вмінь і навичок застосовувати цей спосіб під час розвязування систем рівнянь; розвиваюча: формувати вміння знаходити звязок з раніше вивченим: переносити набуті знання в нові ситуації; стимулювати учнів до висловлювань без побоювань помилитися; заохочувати знаходити свій спосіб фіксації пояснення нового матеріалу; виховна: виховувати культуру математичних міркувань;...
52125. Решение нестандартных задач в курсе алгебры 8-9 класса 1.46 MB
  Доказать что значение выражения является натуральным числом. А При каком положительном значении параметра сумма квадратов корней уравнения равна 16 Ответ: Б При каком отрицательном значении параметра сумма квадратов корней уравнения Ответ: Доказать что значение выражения натуральное число. Доказать что значение выражения чётное число отрицательное. Построить график функции const Построить график функции: а б в Доказать что график функции это две...
52126. Методи розвязування показникових рівнянь 1.22 MB
  Мета: Систематизувати й узагальнити знання уміння та навички учнів із теми формувати вміння учнів розвязувати показникові рівняння різними способами: зведення до однієї основи до спільного...
52127. Розвязування вправ з використанням формул скороченого множення 150 KB
  Розвязування вправ з використанням формул скороченого множення. навчальна формувати удосконалити та поглибити знання та вміння учнів використовувати формули скороченого множення: при розвязуванні вправ формувати навички їх творчого застосування при розвязуванні завдань високого рівня складності; розвивальна розвивати логічне мислення математичну мову вміння чітко висловлювати думки узагальнювати активність; виховна інтерес до математики. Розвязування вправ на застосування формул скороченого множення: для виконання...
52128. Действия с многочленами 51 KB
  Развивающие: развитие логического мышления, активности, познавательного интереса учащихся, умения работать самостоятельно, четко высказывать свои мысли. Развитие коммукативной компетентности, компетентности продуктивной творческой деятельности.
52129. Винесення спільного множника за дужки 87 KB
  Мета: навчити учнів застосовувати даний спосіб під час розвязування задач, розвивати внутрішню мотивацію учнів до теми, що вивчається; навчити учнів прогнозувати очікувані результати уроку; відтворити необхідні знання та вміння для досягнення результатів уроку.
52131. Степінь з цілим показником 544 KB
  8 клас алгебра Тема уроку: Степінь з цілим показником. Мета уроку: Ввести поняття степеня з цілим показником. Тип уроку: урок вивчення нового матеріалу Обладнання: дидактичний матеріал таблиця підручники збірник завдань А. ХІД УРОКУ: 1.