Алгоритми →  Алгоритми сортувань. Частина 1

Напевно, більшість програмістів скажуть, що перший алгоритм, з яким вони познайомилися, був алгоритм сортування. Бульбашкове сортування, напевно, у всіх ВНЗ-ах з програмування приводять як приклад сортування.
Тому я вирішив описати самі популярні алгоритми.

Сортування бульбашкою

Алгоритм сортування бульбашкою, як і сортування вибором порівняно неефективний. Його приблизний час роботи О(n^2), де n - кількість елементів масиву.
Цей метод сортування характеризується дуже простим кодом і алгоритмом. Наведу покроково роботу сортування бульбашкою:
5 4 3 2 1 // початкова паслідовність елементів
4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
3 4 2 1 5
3 2 4 1 5
3 2 1 4 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5 // результат

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

Аналогічне сортування можна виконати, коли найбільший елемент буде «спливати», а найменший «тонути», тобто навпаки.
Реалізація алгоритму:
#include <iostream>
#include <cstdlib>
using namespace std;

const int SIZE = 25;
int array[SIZE];

// заповнення масиву випадковими числами
void GenerationArray()
{
  // прив'язка до часу для генерації чисел без повторень
  srand(time(0));

  for (int i=0; i<SIZE; i++)
  {
    // заповнення масиву числами <100
    array[i] = rand()%100;
  }
}

// виведення масиву на екран
void ShowArray()
{
  for (int i=0; i<SIZE; i++)
  {
    cout << array[i] << " ";
  }

  cout << endl;
}

int main()
{
  int temp;

  GenerationArray();
  ShowArray();

  // сортування бульбашкою
  for (int x=SIZE; x>0; x--)
  {
    for (int i=0; i<SIZE-1; i++)
    {
      // якщо число більше за попереднє
      if (array[i] > array[i+1])
      {
        // міняємо їх місцями
        temp = array[i];
        array[i] = array[i+1];
        array[i+1] = temp;
      }
    }
  }

  ShowArray();

  return 0;
}
Сортування вибором

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

Покрокова робота сортування:
5 4 6 9 3 2 1 7 8 // початкова послідовність
1 4 6 9 3 2 5 7 8
1 2 6 9 3 4 5 7 8
1 2 3 9 6 4 5 7 8
1 2 3 4 6 9 5 7 8
1 2 3 4 5 9 6 7 8
1 2 3 4 5 6 9 7 8
1 2 3 4 5 6 7 9 8
1 2 3 4 5 6 7 8 9 // результат

Реалізація алгоритму:
#include <iostream>
#include <cstdlib>
using namespace std;

const int SIZE = 25;
int array[SIZE];

// заповнення масиву випадковими числами
void GenerationArray()
{
  // прив'язка до часу для генерації чисел без повторень
  srand(time(0));

  for (int i=0; i<SIZE; i++)
  {
    // заповнення масиву числами <100
    array[i] = rand()%100;
  }
}

// виведення масиву на екран
void ShowArray()
{
  for (int i=0; i<SIZE; i++)
  {
    cout << array[i] << " ";
  }

  cout << endl;
}

int main()
{
  int temp, start = 0, min_position, min_element;

  GenerationArray();
  ShowArray();

  // сортування вибором
  while (start != SIZE-1)
  {
    // припустимо, що елемент з індексом лівої межі мінімальний
    min_element = array[start];
    // запам'ятовуємо індекс цього елемента
    min_position = start;

    // шукаємо мінімальний елемент у підмасиві
    for (int i=start; i<SIZE; i++)
    {
      if (array[i] < min_element)
      {
        min_element = array[i];
        min_position = i;
      }
    }

    // якщо елемент з індексом лівої межі не мінімальний,
    // міняємо його місцями з знайденим мінімальним числом
    if (min_position != start)
    {
      temp = array[start];
      array[start] = array[min_position];
      array[min_position] = temp;
    }

    start++;
  }

  ShowArray();

  return 0;
}
Час сортування 100 тисяч елементів сортуванням бульбашкою склав 1 хвилину 38.731 секунд, у той час як алгоритм сортування вибором виконав це завдання за 28.313 секунд. Але все одно обидва алгоритми не підходять для сортування великих масивів чисел. При збільшенні числа елементів у 10 разів, кількість циклів буде зростати в 100(!) разів. Для таких обсягів чисел існують інші алгоритми сортування, про які ми дізнаємося у наступній серії нашої передачі;)

коментарі:

+1bignyak 08.01.2011 12:27
Чим мені подобається ruby так тим, що викликавши в програмі наприклад
[5, 4, 6, 9, 3, 2, 1, 7, 8].sort
На виході отримаємо відсортований в порядку зростання масив чисел.
Євген 08.01.2011 15:41
Ну тут теж можна зробити бібліотеку, потім буде щось подібне:
bubble_sort(array);
quick_sort(array);
І це дає право вибору, який алгоритм використати, які бібліотеки використовувати (boost...) :)
+1Мирослав 09.01.2011 10:05
Запевняю вас - в ruby можна розширити стандартний клас масивів будь яким методом з будь якою логікою :) . Навіть гірше - можна конкретний екземпляр класу розширити якимось методом :)
Євген 09.01.2011 15:31
ну я не працював з рубі, але по прикладу bignyak пожумав що там один якийсь метод використовується
+3tercius 08.01.2011 13:17
маленька підказка: комбінація теґів <pre><code></code></pre>
{
   вміє зберігати відступи в коді
}
спробуйте )
+1Євген 08.01.2011 15:44
дякую :)
yoru020697 19.03.2015 13:49
а якщо потрібно відсортувати масив навпаки? тобно від найбільшого до нацмешного. що потрубно змінити? ніяк не второпаю

додати коментар: