Классические алгоритмы сортировки и поиска на примере С++

Обычно, если необходимо найти элемент в контейнере или провести сортировку, есть смысл использовать уже имеющийся функционал стандартной библиотеки: функции find(), find_if() и sort() хорошо справляются со своей задачей.

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

Сортировка выбором. Квадратическая сложность

1. Находим самый маленький элемент (если сортируем в порядке возрастания);
2. Меняем его местами с первым элементом.
3. Сдвигаем область поиска на 1 элемент вперед
4. Повторяем шаги 1-2 для новой области.

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

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

Реализуем на С++ (будем честными, работа с «голыми» массивами больше подходит С, чем С++, но нас интересует рабочий пример, а не контейнеры):

template <typename T>
void sort(T *arr, int arr_size) //принимаем на вход массив элементов типа Т
{
   T min; //значение минимального элемента
   int min_index; //индекс минимального
   bool was_min = false;
     for (int i = 0; i < arr_size - 1; ++i)
      {
	min = arr[i];//предполагаем, что текущий элемент - минимальный
	min_index = i;
	was_min = false;
	for (int j = i+1; j < arr_size; ++j)
	{
	   if (arr[j] < min)
	   {
		min = arr[j];
		min_index = j;
		was_min = true;
	    }
	}
	if (was_min)
	{
	    T tmp = arr[i];
	    arr[i] = arr[min_index];
	    arr[min_index] = tmp;
	}
     }
}

Сортировка вставкой. Квадратичная сложности в худшем варианте, O(n)- в лучшем.

1. Считаем, что первый элемент отсортирован.
2. Для всех последующих элементов, проверяем идем вложенным циклом назад:
3. Если предыдущий больше текущего, меняем их местами.
4. Повторяем, пока не достигнем начала списка.
5. Повторяем шаги 2-4 для следующего элемента.

template <typename T>
void sort (T arr[], int arr_size)
{
  for(int i = 1; i< arr_size; ++i)
  {
    for(int j = i; j>0; --j)
    {
      if(arr[j] < arr[j-1])
      {
        T tmp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = tmp;
      }        
    }
  }
}

Сортировка «пузырьком». Сложность квадратическая для лучшего и худшего случая.

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

Но делает это немного по-другому:

1. Берем первый элемент.
2. Сравниваем со следующим.
3. Если текущий больше следующего — меняем их местами.
4. Повторяем пп. 1-3 до предпоследнего элемента массива.
5. Повторяем пункты 1-4 для элемента «текущий +1».

Для экономии времени и ресурсов внутренний цикл можем сократить до arr_size 1-i. То есть, каждую итерацию мы будем доходить не до самого конца, а только до последнего не отсортированного элемента.

template <typename T>
void sort(T arr[], int arr_size)
{
  for (int i = 0; i < arr_size-1; ++i)
  {
    for(int j = 0; j <arr_size-1-i; ++j)
   {
     if(arr[j] > arr[j+1])
     {
      T tmp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = tmp;
     }
   }
  }
}

Сортировка слиянием. Log n при худшем и лучшем варианте.

Сортировка слиянием по скорости является явным победителем из ранее представленных алгоритмов. Но подобная сортировка предполагает использование дополнительной памяти и постоянного копирования элементов, что может быть не выгодным при использовании пользовательских типов.

Итак, как это работает:

1. Делим массив на две половины до тех пор, пока у нас не останется массив размером 1 или 2 элемента.
2. Сортируем этот отрезок массива.
3. Сохраняем отсортированный отрезок массив в новый массив.
4. Повторяем для предыдущего отрезка.
5. Проводим слияние двух отрезков.

Выглядит немного запутанно, не так ли?

Попробуем реализовать это в коде. Для начала создадим функцию, которая будет проводить слияние двух отрезков. Её задача получить на вход массив для сортировки, индекс первого элемента (начало первого отрезка), середину — она же начало второго отрезка, и конец второго отрезка.

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

template <typename T>
void merge( T arr[],int first_index, int mid_index, int last_index)
{
 //если левая границы подмассивов накладываются друг на друга, выходим из функции
 if(first_index >= last_index || mid_index < first_index || mid_index > last_index) return;
 
 //если размер подмассива для обмена составляет два элемента и первый больше второго - меняем их местами
//и выходим из функции
 if(last_index == first_index +1)
{ 
  if(arr[first_index] > arr[last_index])
  {
   T tmp = arr[first_index];
   arr[first_index] = arr[last_index];
   arr[last_index] = tmp;
  }
  return;  
} 
 
//в противном случае нам нужно провести слияние двух частей массива:
// от arr[first_index] до arr[mid_index]
// и от arr[mid_index+1] до arr[last_index]
   
 //создаем временный массив-буфер
 // т.к. размер буфера будет зависеть от ходя программы, используем динамическое выделение памяти
// в противном случае можно создать буфер такого же размера, как и входящий массив (если его размер задан глобальной константой)
 T * tmp_arr = new T [last_index - first_index +1];

  //копируем в него все элементы соответствующих подмассивов
  for(int i = 0, tmp_first = first_index; tmp_first<= last_index;++i)
  {
   tmp_arr[i] = arr[tmp_first++];
  }

 //счетчики j и k - для отделения отрезков подмассивов в нашем новом буферном массива. Соответственно j - для левой половины, k - для правой
 for(int i = first_index, j = 0, k = mid_index-first_index+1;
     i <=last_index; ++i)
 {
   if(j > mid_index - first_index)
   {
     arr[i] = tmp_arr[k++];
   }
   else if (k > last_index - first_index)
   {
     arr[i] = tmp_arr[j++];
   }
   else
   {
    arr[i] = (tmp_arr[j] < tmp_arr[k]) ? tmp_arr[j++] : tmp_arr[k++];
   }
 }

delete [] tmp_arr;
}

Самое сложное позади. Итак еще раз, что только что произошло:

1. Функция получила на вход массив, и фактически два его отрезка начало, середину и конец.
2. Если рекурсивная функция, которая вызывает merge уже «переступила» границы подмассивов, мы просто выходим из функции.
3. Если диапазон элементов в массиве, который мы получили, составляет всего два элемента — расставляем их в нужном порядке и выходим из функции.
4. Создаем временный массив и копируем в него элементы в текущем, не отсортированном, порядке.
5. Далее проверяем на граничные элементы. Если это первый или последний элементы отрезков — без зазрения совести добавляем их в начало или конец нашего изначального массива.
6. Для всех остальных сравниваем элементы из двух отрезков и добавляем меньший из них обратно в наш массив.

Теперь нам нужна только рекурсивная функция сортировки, которая и будет проводить деление на отрезки и вызов функции merge.

Как для любой рекурсии важно определить условие выхода их функции. В нашем случаем мы постоянно разделяем массив на две части — правую и левую. Если в какой-то момент первый индекс левой стороны станет больше, чем первый индекс правой — это будет значить, что мы обошли массив полностью.

template <typename T>
void sort(T arr[], int first_index, int last_index)
{
  //условие выхода
  if(first_index >= last_index) return;
  
//делим массив пополам
int mid_index = first_index +(last_index - first_index) /2;

sort(arr, first_index, mid_index);
sort(arr, mid_index+1, last_index);
merge(arr, first_index, mid_index, last_index);
}

Теперь у нас есть отсортированный массив и самое время заняться бинарным поиском.

Бинарный поиск. Сложность log n в худшем случае, и O(n) — в лучшем.

Бинарный поиск — крайне быстрый способ поиска. Вот только работает он исключительно в отсортированном массиве (контейнере).

Бинарный поиск работает по принципу «разделяй и властвуй»:

1. Взять массив и найти средний элемент (length /2).
2. Проверить, является ли средний элемент искомым?
3. Если нет, проводим еще две проверки.
4. Средний элемент меньше искомого? Повторяем шаги 1-3 для элементов от средний+1 до length-1
5. Средний элемент больше искомого? Повторяем шаги 1-3 для элементов от нуля до средний -1
6. Если размер массива для поиска нулевой, значит элемент отсутствует в массиве.

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

Для упрощения будем возвращать номер элемента или arr_size +1, если элемент отсутствует в массиве.

template <typename T>
int find (T arr[], int arr_size, T elem)
{
  int mid_elem_index = arr_size/2;
  int first_elem_index = 0, last_elem_index = arr_size-1; 

  if(elem < arr[first_elem_index] || elem > arr[last_elem_index])
 {
  return arr_size+1;
 }  
 
  while (last_elem_index - first_elem_index >= 0)
{
  if(elem == arr[mid_elem_index])
  {
   return mid_elem_index;
  }
  if(elem > arr[mid_elem_index])
 {
   first_elem_index = mid_elem_index+1;
   mid_elem_index = (mid_elem_index+1 + last_elem_index)/2;
 }
if(elem < arr[mid_elem_index])
 { 
   last_elem_index = mid_elem_index-1;
   mid_elem_index = mid_elem_index /2;
 }
}

return arr_size+1;
}