3672

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

Лекция

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

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

Украинкский

2012-11-05

42.5 KB

43 чел.

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

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

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


 

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

26912. Вены тазовой конечности 2.56 KB
  большеберцовую вену в. Tarsea pertorans они переходят в дорсальную вену стопы в. Saphena medialis она впадает в бедренную вену.
26913. Морфофункциональная х-ка и анатомический состав лимфатической системы 4.82 KB
  Морфофункциональная хка и анатомический состав лимфатической системы. Лимфатическая сма выполняет в орг. Она отводит лимфу из тканей в краниальную полую вену. Лимфатич.
26914. Лимфатические узлы головы и шеи 5.94 KB
  Лимфатические узлы головы 1 Околоушной лимфатический узел – ln. 2 Подчелюстной лимфатический узел –ln. 3 Медиальный заглоточный лимфатический узел ln. Отток лимфы в трахеальный лимфатический проток.
26915. Лимфатические узлы грудной и тазовой конечности 4.96 KB
  Аxillaris лежит каудально от плечевого сустава на медиальной поверхности большой круглой мышцы. axillaris primae costae– лежит медиально от плечевого сустава в плоскости первого ребра. rhomboideus лежит близ шейного угла лопатки под одноименной мышцей; б заостный лимфатический узел – ln. infraspinatus лежит у каудального края одноименной мышцы.
26916. Соотношение права и морали 4.54 KB
  ПРАВОсистема нормправил поведениякоторые исходят от госвавыражают волю и интересы определенных слоев населения или большинства общества сформулированы в специальных гос документахнормативных актах охраняются от нарушений мерами госпринуждения.Правовые нормы создаются либо санкционируются госвом и им же отменяются.Нормы морали создаются не госвом непосредственноа возникают и развиваются спонтаннов процессе практической деятельности людей.В любом госве действует только одноим же созданное право.
26917. Соотношение права и корпоративных норм 4.24 KB
  НОРМЫ ОБЩЕСТВЕННЫХ ОРГАНИЗАЦИЙкорпоративные нормыправила поведенияустанавливаемые самими организациямиохраняемые с помощью мер общественного воздействияпредусмотренных уставми этих организаций.Правовые нормы создаются либо санкционируются госвом и им же отменяются.Корпоративные нормы создаются организациями.Корпоративные нормы охраняются общественым мнением членов организаций и мерамипредусмотренными уставами организаций.
26918. СОЦИАЛЬНЫЕ НОРМЫ 3.86 KB
  Соотношение социальных и технических н СОЦИАЛЬНЫЕ НОРМЫправила поведенияиспользуемые для регулирования общественных отношений.К ним относятся правовыеморальныекорпоративные нормы и др. Социальные нормы это правила социально значимого поведения людей. ТЕХНИЧЕСКИЕ НОРМЫэто совокупность нормопределяющих правила рационального обращения с орудиями труда предметами материального мира в целом.
26919. Предмет, метод и функции теории государства и права 7.59 KB
  Предмет метод и функции теории государства и права.философия праваметодологические проблемы правоведения; 2.социология прававопросы эффективного действия законодательства; 3.Специальная юридическая теорияпроблемы источников права классификацию юридических норм юридических фактов коллизии норм толкование и применение юридических норм.
26920. Власть в первобытном обществе и его социально-нормативная сфера 4.44 KB
  Власть в первобытном обществе и его социальнонормативная сфера. Обществосовокупность индивидов имеющих общие интересы которые носят постоянный и объективный характер взаимодействующих и сотрудничающих на основе этих интересов имеющих организованную силувласть. Власть это явление социальное. Власть заключается в том что один субъект дает указания а второй их выполняет.