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


 

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

78846. Наука и власть 29.5 KB
  Наука и власть Любая власть как институционализированная государственноправовые институты так и не институционализированная например власть старшего в семье власть учителя в школе власть женщины над любящим ее мужчиной и т. Власть государственная необходима для организации общественного производства которое немыслимо без подчинения участников единой воле а также для регулирования взаимоотношений между людьми в обществе. Проблема наука и власть имеет два аспекта: 1 проблема самой науки как формы власти;...
78847. Наука и нравственность. Этика науки 29 KB
  Этика науки Современная наука имеет ряд особенностей качественно отличающих ее от науки даже недавнего прошлого. Довольно быстро обнаружились и некоторые опасности связанные с возможным применением достижений современной науки. Этика науки изучает нравственные основы научной деятельности. Этические проблемы науки рождались в связи с развитием физики биологии в частности генетики психологии.
78848. Научная рациональность и ее типы 29 KB
  Научная рациональность и ее типы Основными свойствами научной рациональности являются: объектная предметность эмпирическая или теоретическая однозначность доказанность проверяемость способность к улучшению. Наука это прежде всего специфическая форма культуры порождающая особую агрессивную форму рациональности развивающуюся в сложном историческом социокультурном контексте. Анализ научной рациональности и научного знания является комплексным междисциплинарным исследованием предусматривающим синтез различных видов и форм знаний. ...
78849. Научное, ненаучное, псевдонаучное знание 30.5 KB
  Научное ненаучное псевдонаучное знание. Научное знание система знаний о законах природы общества мышления. Научное знание составляет основу научной картины мира и отражает законы его развития. Научное знание: является результатом постижения действительности и когнитивной основой человеческой деятельности; социально обусловлено; и обладает различной степенью достоверности.
78850. Метатеоретический уровень научного знания 26.5 KB
  мета за после это теория о теории: объектом научного анализа для метатеории выступает сама теория. Метатеоретический подход не просто реорганизует научное знание является не только способом научного анализа теории но производит в ней сдвиги содержательного порядка порождает новое знание. Рефлексия является своеобразным способом развития самого содержания знания одним из важных путей разработки теории Дело в том что плодотворен сам по себе выход за пределы теории отстраненный взгляд на нее. На основе метатеории в процессе...
78852. Философские основания науки 27 KB
  Философские основания науки Предисловие: Философское основание науки представляет особой один из элементов философии науки направление в философии изучающее научную деятельность ее особенности и характеристики; ее цель устанавливать правильность научных суждений и теорий и объяснять место и роль науки в современной культуре наряду с теоретическим и эмпирическим знанием. Философские основания науки. Философские основания науки. Функции функция философского обоснования: Любая новая идея для того чтобы стать либо частью картины мира...
78853. Структура эмпирического знания. Проблема факта 28.5 KB
  Проблема факта Эмпирические факты образуют базис на который опираются научные теории. Факты фиксируются в языке науки в высказываниях типа: более половины опрошенных в городе недовольны экологией городской среды и т. Вернадский: эмпирические факты хлеб науки. Проблема факта: Эмпирические факты содержат не только информацию об изучаемых явлениях но и как правило включают ошибки наблюдателя и т.
78854. Структура теоретического знания 29 KB
  Теоретический уровень научного познания как и эмпирический имеет ряд подуровней среди которых можно выделить следующие по степени общности: а аксиомы теоретические законы; б частные теоретические законы описывающие структуру свойства и поведение идеализированных объектов; в частные единичные высказывания утверждающие нечто о конкретных во времени и пространстве состояниях свойствах и отношениях некоторых идеализированных объектов 2 вида научных законов: 1Универсальные и частные законы. Универсальными принято называть законы...