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

Сортування елементів у одновимірних масивах

Задача 1. При роботі з масивами даних не рідко виникає завдання їх сортування за зростанням або спаданням, тобто упорядкування. Це означає, що елементи того ж масиву потрібно розташувати строго по порядку. Наприклад, в разі сортування за зростанням попередній елемент повинен бути менше наступного (або дорівнює йому).

Розв’язання

Існує безліч методів сортування. Одні з них є більш ефективними, інші - простіше для розуміння. Досить простий для розуміння є сортування методом бульбашки, який також називають методом простого обміну. У чому ж він полягає, і чому у нього така дивна назва: "метод бульбашки"?

Як відомо повітря легше води, тому бульбашки повітря спливають. Це просто аналогія. У сортуванні методом бульбашки по зростанню легші (з меншим значенням) елементи поступово "спливають" в початок масиву, а більш важкі один за одним опускаються на дно (до кінця масиву).

Алгоритм і особливості цього сортування такі:

1.     При першому проході по масиву елементи попарно порівнюються між собою: перший з другим, потім другий з третім, слідом третій з четвертим і т.д. Якщо попередній елемент виявляється більше наступного, то їх міняють місцями.

2.     Не важко здогадатися, що поступово найбільше число виявляється останнім. Інша частина масиву залишається відсортованої, хоча деяке переміщення елементів з меншим значенням в початок масиву спостерігається.

3.     При другому проході нема чого порівнювати останній елемент з передостаннім. Останній елемент вже стоїть на своєму місці. Значить, число порівнянь буде на одне менше.

4.     На третьому проході вже не треба порівнювати передостанній і третій елемент з кінця. Тому число порівнянь буде на два менше, ніж при першому проході.

5.     В кінці кінців, при проході по масиву, коли залишаються тільки два елементи, які треба порівняти, виконується тільки одне порівняння.

6.     Після цього перший елемент нема з чим порівнювати, і, отже, останній прохід по масиву не потрібен. Іншими словами, кількість проходів по масиву m-1, де m - це кількість елементів масиву.

7.     Кількість порівнянь в кожному проході одно m-i, де i - це номер проходу по масиву (перший, другий, третій і т.д.).

8.     При обміні елементів масиву зазвичай використовується "буферна" (третя) змінна, куди тимчасово поміщається значення одного з елементів.

Програма на мові Паскаль:

const

    m = 10;

var

    arr: array[1..m] of integer;

    i, j, k: integer;

begin

    randomize;

    write ('Початковий масив: ');

    for i := 1 to m do begin

        arr[i] := random(256);

        write (arr[i]:4);

    end;

    writeln; writeln;

    for i := 1 to m-1 do

        for j := 1 to m-i do

            if arr[j] > arr[j+1] then begin

                k := arr[j];

                arr[j] := arr[j+1];

                arr[j+1] := k

            end;

    write ('Відсортований масив: ');

    for i := 1 to m do

        write (arr[i]:4);

    writeln;

readln

end.

Найшвидший  алгоритм Хоора(Гоара) для сортування одновимірного масиву у вигляді процедури мовою програмування Pascal

Ця процедура, після її оголошення, сортує масив mas, який складається з елементів типу integer.

Procedure QuickSort(first, last :integer);
Var v, x, left, right :integer;
begin
  left := first;
  right := last;
  v := mas[(left + right) div 2];
  while left <= right do
    begin
    while mas[left] < v do
      left := left + 1;
    while mas[right] > v do
      right := right - 1;
    if left <= right then
      begin
        x := mas[left];
        mas[left] := mas[right];
        mas[right] := x;
        left := left + 1;
        right := right - 1;
      end;
    end;
  if first < right then 
    QuickSort(first, right);
  if left < last then
    QuickSort(left, last);
end;

Задача 2. Випадковим чином задається двомірний масив(цe таблиця чисeл) , що складається із nxn елементів, якщо n менше 100. Вивести масив на екран у вигляді  таблиці чисел та знайти суму елементів, що розташовані на  обох діагоналях масиву. Вивести одномірними масивами елементи окрeмо верхнього і окрeмо нижнього трикутника   матриці без головної діагоналі  знайти суму елементів верхнього трикутника   та сума елементів нижнього  трикутника квадратної матриці nxn.

Розв′язання.

Program Summa_trukutnuk_matriza;

const m=100;  n=100;

var  sum,f,s,  d, c:real;    b:array[1..m*n] of real;

 xn:array[1..m*n] of real;     xv:array[1..m*n] of real;      a:array[1..m,1..n] of real;

i,j,p, g, k:integer;

begin

writeln('  Ввeдіть кількість рядків квадратного масиву,  яка мeншe 100 ');

readln(k);    s:=0;

for i:=1 to k do

for j:=1 to k do  begin

a[i,j]:=int(random*20-10);

b[(i-1)*k+j]:=a[i,j];   end;  writeln('   ');

writeln(' Масив випадкових чисeл: ');  writeln('   ');

for i:=1  to k do   begin

for j:=1  to k do  begin      write('  a[',i,';',j,']:= ',a[i,j]  {'  b[',i-1*k+j,']= ',b[(i-1)*k+j]});

end; writeln('   '); end;

s:=0;   for i:=1 to k do  begin   s:=s+a[i,i];  end;

f:=0;  for i:=1 to k do  begin  f:=f+a[i,k+1-i]; end;

     if   k mod 2 =1 then   sum:=s+f- a[k div 2 +1, k div 2 +1]   else   sum:=s+f;

p:=1;  g:=1;    for i:=1  to k do   begin

for j:=k  downto 1 do  begin

  if   i<j  then  begin

  xv[g]:= a[i,j];  g:=g+1; end;  end; end;

  for i:=1  to k do   begin

  for j:=1  to i-1 do  begin

  if   i>j  then  begin

  xn[p]:= a[i,j];   p:= p+1; end; end;  end;

writeln(' Масив   чисeл нижнього трикутника матриці : ');

          d:=0;  for i:=1  to   ((k-1)*k) div 2     do     begin    d:=d+ xn[i];

write('  xn[',i,']= ', xn[i]); end; writeln('   ');

writeln(' Масив   чисeл вeрхнього трикутника матриці :  ');

           c:=0;  for i:=1  to ((k-1)*k) div 2    do   begin

c:=c+ xv[i];  write('  xv[', i, ']= ', xv[i]);   end;    writeln('   ');

writeln('  Сума чисел головної діагоналі матриці:', s); writeln('    ');

writeln('  Сума  чисел  бічної  діагоналі матриці :', f); writeln('    ');

writeln('  Сума чисел на обох діагоналях: ', sum);   writeln('    ');

writeln('  Сума чисел верхнього трикутника матриці ' , c);  writeln('    ');

writeln('  Сума чисел нижнього трикутника матриці  ' ,  d);    writeln('    ');       end.

Задача 3. Вагони

(Час: 1 сек. Пам'ять: 16 Мб Складність: 23%)

Щодня диспетчеру залізничної станції доводиться переставляти вагони в багатьох поїздах, щоб вони йшли в заданому порядку. Для цього диспетчер може розчепити прийшов на станцію складу в довільних місцях і переставити утворилися зчіпки з одного або декількох вагонів в довільному порядку. Порядок вагонів в одній зчепленні міняти не можна, також не можна розгорнути всю зчеплення так, щоб останній вагон в зчепленні виявився першим в ній.

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

За час ${\displaystyle \;O(n^{2})}$

• Сортування вибором — ( англ.  Selection sort ) — пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку.
• Сортування вставкою — (англ. Insertion sort) — Визначаємо місце де поточний елемент повинен знаходитися в упорядкованому списку, і вставляємо його туди.
• Сортування обміном (сортування бульбашкою ( англ.  Bubble sort )) — для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку.
• Сортування методом бінарної вставки

За час ${\displaystyle O(n\log \;n)}$

• Плавне сортування (англ. Smoothsort)

• пірамідальне сортування
• швидке сортування
• сортування злиттям

За час ${\displaystyle \;O(n)}$ з використанням додаткової інформації про елементи

• Сортування підрахунком
• Сортування за розрядами
• Сортування комірками

За час ${\displaystyle O(n\log ^{2}\;n)}$

• Сортування злиттям модифіковане
• Сортування Шелла

За час ${\displaystyle O(nn!)}$

• Сортування перестановкою
• Випадкове сортування

В даному розділі розглянуто набір реалізацій А.Нікітін на мові Pascal стандартних алгоритмів, застосовуваних при вирішенні завдань олімпіадного програмування.

• Підрахунок різних букв в слові
• Перестановка букв в слові (циклічний зсув вправо)
• Перевірка рядки на "паліндромний"
• Друк всіх дільників натурального числа A
• Друк всіх скоєних чисел до 10000
• Друк всіх простих чисел до 500
• Підрахунок суми цифр числа
• Підрахунок суми елементів одновимірного масиву
• Підрахунок суми елементів двомірного масиву
• Пошук максимального елемента в масиві
• Пошук мінімального елемента в масиві
• Пошук середнього арифметичного в масиві
• Друк всіх елементів масиву з інтервалу C..D
• Циклічний зсув елементів масиву вправо
• Друк самого часто зустрічається елемента з масиву
• Чи всі елементи масиву різні?
• Сортування масиву "бульбашкою"
• Рішення рівняння: A * x ^ 2 + B * x + C = 0
• Обчислення довжини відрізка | AB |
• Яка точка (A або B) ближче до початку координат
• Обчислення площі трикутника по 3 вершин
• Чи потрапляє точка M (x, y) в коло з центром O (Xc, Yc) і радіусом R
• Перекладу десяткового числа в двійкове
• Перекладу двійкового числа в десяткове
• Перекладу десяткового числа в шістнадцяткове
• Перекладу шістнадцятирічного числа в десяткове
• Рекурсивні алгоритми: знаходження НСД і НСК двох чисел
• Рекурсивні алгоритми: обчислення факторіала
• Рекурсивні алгоритми: генерація перестановок
• Рекурсивні алгоритми: швидке сортування
• Рішення системи 2-х рівнянь з двома невідомими
• Рішення системи 3-х рівнянь з трьома невідомими
• Визначення перетину двох відрізків
• Визначення положення точки відносно сектора
• Положення точки щодо вектора
• Положення точки щодо трикутника (варіант 1)
• Положення точки щодо трикутника (варіант 2)
• Моделювання додавання двійкових чисел
• Моделювання віднімання двійкових чисел
• Зведення цілого числа в натуральну ступінь (варіант 1)
• Зведення цілого числа в натуральну ступінь (варіант 2)
• Множення довгих натуральних десяткових чисел
• Кодування: приклад простий кодування (зрушення по ключу)
• Обробка тексту: підрахунок кількості слів в тексті
• Обробка тексту: виділення слів з тексту
• Обробка тексту: виділення чисел з тексту
• Обробка тексту: дозвіл введення тільки цифр
• Обробка тексту: переклад в маленькі букви (нижній регістр)
• Обробка тексту: переклад в заголовні букви (верхній регістр)
• Обробка тексту: видалення з тексту Комметаріі типу {...}
• Бек-трекінг: Міста
• Бек-трекінг: Прохід по лабіринту
• Бек-трекінг: Доміно
• Бек-трекінг: Послідовність
• Бек-трекінг: Магічний квадрат