Основные виды сортировок и примеры их реализации

Памятка для тех, кто готовится к собеседованию на позицию разработчика

Основные виды сортировок и примеры их реализации

Разработка

На собеседованиях будущим стажёрам-разработчикам дают задания на знание алгоритмов, в том числе на знание структур данных, алгоритмов сортировки и поиска. Академия Яндекса составила список для подготовки с методами сортировки, примерами их реализации на С++ и гифками, чтобы лучше понять, как они работают.

Пузырьковая сортировка и её улучшения

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

alt

Сортировка пузырьком — один из самых известных алгоритмов сортировки. Здесь нужно последовательно сравнивать значения соседних элементов и менять числа местами, если предыдущее оказывается больше последующего. Таким образом элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале.

Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.

#include <cstddef>
#include <utility>

template<typename T>
void bubble_sort(T array[], std::size_t size)
{
    for (std::size_t idx_i = 0; idx_i < size - 1; idx_i++)
    {
        for (std::size_t idx_j = 0; idx_j < size - idx_i - 1; idx_j++)
        {
            if (array[idx_j + 1] < array[idx_j])
            {
                std::swap(array[idx_j], array[idx_j + 1]);
            }
        }
    }
}

Сортировка перемешиванием (шейкерная сортировка)

alt

Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.

#include <cstddef>
#include <utility>
void ShakerSort(int *a, int n) {
   int left, right, i;
   left = 0;
   right= n - 1;
   while (left <= right) {
       for (i = right; i >= left; i--) {
           if (a[i-1] > a[i]) {
               swap(a[i-1], a[i]);
           }
       }
       left++;
       for (i = left; i <= right; i++) {
           if (a[i-1] > a[i]) {
               swap(a[i-1], a[i]);
           }
       }
       right--;
   }
}

Сортировка расчёской

alt

Сортировка расчёской — улучшение сортировки пузырьком. Её идея состоит в том, чтобы «устранить» элементы с небольшими значения в конце массива, которые замедляют работу алгоритма. Если при пузырьковой и шейкерной сортировках при переборе массива сравниваются соседние элементы, то при «расчёсывании» сначала берётся достаточно большое расстояние между сравниваемыми значениями, а потом оно сужается вплоть до минимального.

Первоначальный разрыв нужно выбирать не случайным образом, а с учётом специальной величины — фактора уменьшения, оптимальное значение которого равно 1,247. Сначала расстояние между элементами будет равняться размеру массива, поделённому на 1,247; на каждом последующем шаге расстояние будет снова делиться на фактор уменьшения — и так до окончания работы алгоритма.

 int comb(vector<double> sort)
    {
        int n = 0; // Количество перестановок
		double factor = 1.247; // Фактор уменьшения
		double step = sort.size() - 1;

		while (step >= 1)
		{
			for (int i = 0; i + step < sort.size(); ++i)
			{
				if (sort[i] > sort[i + step])
				{
					swap(sort[i], sort[i + step]);
					n++;
				}
			}
			step /= fakt;
		}
		// сортировка пузырьком
		for (int i = 0; i < sort.size() - 1; i++)
		{
			bool swapped = false;
			for (int j = 0; j < sort.size() - i - 1; j++)
			{
				if (sort[j] > sort[j + 1]) {
					swap(sort[j], sort[j + 1]);
					swapped = true;
					++n;
				}
			}

			if (!swapped)
				break;
		}
		return n;
	}

Простые сортировки

Сортировка вставками

alt

При сортировке вставками массив постепенно перебирается слева направо. При этом каждый последующий элемент размещается так, чтобы он оказался между ближайшими элементами с минимальным и максимальным значением.

void exch(Item &A, Item &B)
{
    Item t = A; A = B; B = t;
}

template <typename Item>
void compexch(Item &A, Item &B)
{
    if (B < A) exch(A, B);
}

template <typename Item>
void insertion_sort(Item a[], int L, int R)
{
    for(int i = R; i > L; i--)
        compexch(a[i - 1], a[i]);

    for (int i = L + 2; i <= R; i++)
    {
        int j = i;
        Item cur = a[j];
        while (a[j - 1] > cur)
        {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = cur;
    }
}

Сортировка выбором

alt

Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсортированного элемента. Этот шаг нужно повторять до тех пор, пока в массиве не закончатся неотсортированные подмассивы.

using namespace std;
  
void swap(int *xp, int *yp) 
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} 
  
void selectionSort(int arr[], int n) 
{ 
    int i, j, min_idx; 
  
    for (i = 0; i < n-1; i++) 
    { 
        // Найти минимальный элемент в неотсортированном массиве
        min_idx = i; 
        for (j = i+1; j < n; j++) 
        if (arr[j] < arr[min_idx]) 
            min_idx = j; 
  
        // Поменять найденный минимум местами с первым элементом
        swap(&arr[min_idx], &arr[i]); 
    } 
} 
  
void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        cout << arr[i] << " "; 
    cout << endl; 
} 

Эффективные сортировки

Быстрая сортировка

alt

Этот алгоритм состоит из трёх шагов. Сначала из массива нужно выбрать один элемент — его обычно называют опорным. Затем другие элементы в массиве перераспределяют так, чтобы элементы меньше опорного оказались до него, а большие или равные — после. А дальше рекурсивно применяют первые два шага к подмассивам справа и слева от опорного значения.

Быструю сортировку изобрели в 1960 году для машинного перевода: тогда словари хранились на магнитных лентах, а сортировка слов обрабатываемого текста позволяла получить переводы за один прогон ленты, без перемотки назад.

int partition (double *a, int p, int r)
  {
    double x = *(a+r);
    int i = p - 1;
    int j;
    double tmp;
    for (j = p; j < r; j++)
    {
      if (*(a+j) <= x)
      {
        i++;
        tmp = *(a+i);
        *(a+i) = *(a+j);
        *(a+j) = tmp;
      }
    }
    tmp = *(a+r);
    *(a+r) = *(a+i+1);
    *(a+i+1) = tmp;
    return i + 1;
  }
 
 void quicksort (double *a, int p, int r)
  {
    int q;
    if (p < r)    {
      q = partition (a, p, r);
      quicksort (a, p, q-1);
      quicksort (a, q+1, r);
    }
  }

Сортировка слиянием

alt

Сортировка слиянием пригодится для таких структур данных, в которых доступ к элементам осуществляется последовательно (например, для потоков). Здесь массив разбивается на две примерно равные части и каждая из них сортируется по отдельности. Затем два отсортированных подмассива сливаются в один.

#include <stdio.h>
#include <stdlib.h>
// Функция сортировки двухпутевым слиянием
void merge(int *a, int n)
{
  int mid = n / 2; // Находим середину сортируемой последовательности
  if (n % 2 == 1)
    mid++;
  int h = 1; // Задать шаг
  // Выделяем память под формируемую последовательность
  int *c = (int*)malloc(n * sizeof(int));
  int step;
  while (h < n) 
  {
    step = h;
    int i = 0;   // Индекс первого пути
    int j = mid; // Индекс второго пути
    int k = 0;   // Индекс элемента в итоговой последовательности
    while (step <= mid) 
    {
      while ((i < step) && (j < n) && (j < (mid + step))) 
      { // Пока не дошли до конца пути заполняем следующий элемент формируемой последовательности меньшим из двух 
        if (a[i] < a[j])  
        {
          c[k] = a[i];
          i++; k++;
        }
        else {
          c[k] = a[j];
          j++; k++;
        }
      }
      while (i < step) 
      { // Переписываем оставшиеся элементы первого пути
        c[k] = a[i];
        i++; k++;
      }
      while ((j < (mid + step)) && (j<n)) 
      {  // Переписываем оставшиеся элементы второго пути
        c[k] = a[j];
        j++; k++;
      }
      step = step + h; // Переходим к следующему этапу
    }
    h = h * 2;
    // Переносим упорядоченную последовательность в исходный массив
    for (i = 0; i<n; i++)
      a[i] = c[i];
  }
}
int main() 
{
  int a[8];
  // Заполняем массива случайными числами
  for (int i = 0; i<8; i++)
    a[i] = rand() % 20 - 10;
  // Выводим элементы массива до сортировки
  for (int i = 0; i<8; i++)
    printf("%d ", a[i]);
  printf("\n");
  merge(a, 8);
  // Выводим элементы массива после сортировки
  for (int i = 0; i<8; i++)
    printf("%d ", a[i]);
  printf("\n");
  getchar();
  return 0;
}

Пирамидальная сортировка

alt

При этой сортировке сначала строится пирамида из элементов исходного массива. Пирамида (или двоичная куча) — это способ представления элементов, при котором от каждого узла может отходить не больше двух ответвлений. А значение в родительском узле должно быть больше значений в его двух дочерних узлах.

alt

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

#include <iostream>

using namespace std;

// Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является
// индексом в arr[]. n - размер кучи

void heapify(int arr[], int n, int i)
{
    int largest = i;   
// Инициализируем наибольший элемент как корень
    int l = 2*i + 1; // левый = 2*i + 1
    int r = 2*i + 2; // правый = 2*i + 2

 // Если левый дочерний элемент больше корня
    if (l < n && arr[l] > arr[largest])
        largest = l;

   // Если правый дочерний элемент больше, чем самый большой элемент на данный момент
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // Если самый большой элемент не корень
    if (largest != i)
    {
        swap(arr[i], arr[largest]);

// Рекурсивно преобразуем в двоичную кучу поддерево
        heapify(arr, n, largest);
    }
}

// Основная функция, выполняющая пирамидальную сортировку
void heapSort(int arr[], int n)
{
  // Построение кучи
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

   // Один за другим извлекаем элементы из кучи
    for (int i=n-1; i>=0; i--)
    {
        // Перемещаем текущий корень в конец
        swap(arr[0], arr[i]);

        // вызываем процедуру heapify на уменьшенной куче
        heapify(arr, i, 0);
    }
}

/* Вспомогательная функция для вывода на экран массива размера n*/
void printArray(int arr[], int n)
{
    for (int i=0; i<n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}

Сортировка деревом

Эта сортировка оптимальна, когда данные получаются напрямую при чтении с потока (например, из файла или консоли).

При этой сортировке сначала строится дерево из элементов исходного массива. Двоичным деревом называют упорядоченную структуру данных, в которой каждому родительскому элементу ставятся в соответствие два дочерних. Причём для каждого элемента выполнено следующее правило: левый дочерний элемент всегда меньше, а правый преемник всегда больше или равен предшествующему.

При добавлении в дерево нового элемента его последовательно сравнивают с нижестоящими узлами. Если элемент больше или равен родителю, то он идет в правое поддерево и сравнивается уже с правым дочерним элементом, в обратном случае он идёт в левое поддерево.

Если мы будем рекурсивно обходить дерево по правилу «левый дочерний элемент — родительский элемент — правый дочерний элемент», то, записав все элементы в массив, мы получим упорядоченное в порядке возрастания множество.

#include <vector>
#include <iostream>

using namespace std;

class BinaryTree
{
protected:
  // Узел бинарного дерева
  struct BinaryTreeNode
  {
    shared_ptr<BinaryTreeNode> left, right; // Левое и правое поддерево
    int key; // ключ
  };

  shared_ptr<BinaryTreeNode> m_root; // Корень дерева
  
protected:
  // Рекурсивная процедура вставки ключа
  // cur_node - текущий элемент дерева, с которым сравнивается вставляемый
  // node_to_insert - вставляемый элемент
  void insert_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const shared_ptr<BinaryTreeNode>& node_to_insert)
  {
      assert(cur_node != nullptr);
      // Сравнение
      bool insertIsLess = node_to_insert->key < cur_node->key;
      if(insertIsLess)
      {
        // Вставка в левое поддерево
        if(cur_node->left == nullptr)
          cur_node->left = node_to_insert;
        else
          insert_recursive(cur_node->left, node_to_insert);
      }
      else
      {
        // Вставка в правое поддерево
        if(cur_node->right == nullptr)
          cur_node->right = node_to_insert;
        else
          insert_recursive(cur_node->right, node_to_insert);
      }
  }

public:
  void insert(int key)
  {
    shared_ptr<BinaryTreeNode> node_to_insert(new BinaryTreeNode);
    node_to_insert->key = key;

    if(m_root == nullptr)
    {
        m_root = node_to_insert;
        return;
    }

    insert_recursive(m_root, node_to_insert);
  }

public:
  typedef function<void(int key)> Visitor;

protected:
  // Рекурсивная процедура обхода дерева
  // cur_node - посещаемый в данный момент элемент
  void visit_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const Visitor& visitor)
  {
    assert(cur_node != nullptr);

    // Сначала посещаем левое поддерево
    if(cur_node->left != nullptr)
      visit_recursive(cur_node->left, visitor);

    // Потом текущий элемент
    visitor(cur_node->key);

    // Затем правое поддерево
    if(cur_node->right != nullptr)
      visit_recursive(cur_node->right, visitor);
  }

public:
  void visit(const Visitor& visitor)
  {
    if(m_root == nullptr)
      return;
    visit_recursive(m_root, visitor);
  }
};

int main()
{
  BinaryTree tree;
  // Добавление элементов в дерево
  vector<int> data_to_sort = {10, 1, 7, 3, 12, 7, 39};
  for(int value : data_to_sort)
  {
    tree.insert(value);
  }
  // Обход дерева
  tree.visit([](int visited_key)
  {
    cout<<visited_key<<" ";
  });
  cout<<endl;

  // Результат выполнения: 1 3 7 7 10 12 39
  return 0;
}

Больше по теме

Разработка

5 способов побольше узнать об алгоритмах

От Википедии до курсов ШАДа и MIT

Разработка

Python: простые, но полезные советы по оптимизации кода

Санитарная обработка данных, пропуск начала итерируемого объекта и другие приёмы

Разработка

Как проходит проектная часть Школы разработки интерфейсов?

История команды, которая разработала личный кабинет для кандидата на обучение в Школе

Анализ данных, Разработка

Чем занимается разработчик инфраструктуры и как им стать

«Для нас все остальные разработчики Яндекса — пользователи»

Разработка

Язык программирования Rust: видеозаписи лекций курса от CS центра

Освойте безопасный язык программирования для браузеров

Разработка

Спорт для разработчиков: как устроено олимпиадное программирование

Ключевые соревнования, советы по подготовке и работе в команде

Разработка

Подборка игр и тренажёров для начинающих разработчиков интерфейсов

Освойте базовый синтаксис HTML и CSS, технику Pixel Perfect и красивую вёрстку