LiveStreet

Наверное, большинство программистов скажут, что первый алгоритм, с которым они познакомились, был алгоритм сортировки. Пузырьковую сортировку наверное во всех ВУЗ-ах по программированию приводят в качестве примера сортировки.
Поэтому я решил описать самые популярные алгоритмы сортировок.

Сортировка пузырьком

Сортировка пузырьком, как и сортировка выбором сравнительно неэффективная. Их примерное время работы равно О(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+1; 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(!) раз. Для таких объемов чисел существуют другие алгоритмы сортировки, о которых мы узнаем в следующей серии нашей передачи ;)