Пузырьковая сортировка и все-все-все (по одноимённой статье на habr.com)

!!НАШ БЛОГ ПЕРЕЕХАЛ!!

Мы создали свой сайт! Все материалы, опубликованные в этом блоге, переехали туда.

Наш новый сайт maddevelop.ru

А данную статью вы можете найти по ссылке

Глупая сортировка

Перебираем в массиве пары чисел (0 и 1, 1 и 2, 2 и 3 и так далее). Как только попадается пара, в которой первое число больше второго, меняем их местами и начинаем перебор с самого начала.

Временная сложность - O(n*n*n).

static int[] Stupid (int[] firstArray)
{
  int curr = 0;
  int i = 0;
  while (i != firstArray.Length - 1)
  {
    if (firstArray[i] <= firstArray[i + 1])
    {
      i++;
      continue;
    }             
    else
    {
    Replace(array, i, i + 1);
    i = 0;
    }
  }            
  return firstArray;
}

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

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

Временная сложность - O(n*n).

static int[] Bubble(int[] array)
{        
  int counter = 0;
  int curr = 0;
  for (int i = 0; i < array.Length - 1; i++)
  {
    for (int j = 0; j < array.Length - i - 1; j++) 
    {
      if (array[j] > array[j + 1])
      {
        Replace(array, i, i + 1);
      }
      counter++;
    }
  }
  return array;
}

Сортировка перемешиванием

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

Временная сложность алгоритма не меняется - O(n*n).

static int[] Shake(int[] array)
{
  int counter = 0;
  int left = 0;
  int right = array.Length - 1;
  while (left < right)
  {
    for (int i = left; i < right; i++)
    {
      if (array[i] > array[i + 1])
        Replace(array, i, i + 1);
      counter++;
    }
    right--;
    for (int i = right; i > left; i--)
    {
      if (array[i] < array[i - 1])
        Replace(array, i - 1, i);
      counter++;
    }
    left++;
  }
  return array;
}

Чётно-нечётная сортировка

Суть алгоритма состоит в том, что сначала сравниваются 0 и 1, 2 и 3, 4 и 5 и т.д. элементы, т.е. первое число в паре - чётное, а при следующем проходе - 1 и 2, 3 и 4, 5 и 6 и т.д. элементы, т.е. первым числом в паре берётся нечётное. Процесс заканчивается, когда два прохода подряд не дают перестановок. Алгоритм работает несколько быстрее сортировки пузырьком.

Однако временная сложность остаётся равной O(n*n).

static int[] EvenOdd(int[] array)
{
  int change = 0;
  int proxod = 0;
  int result = 1;
  do
  {
    for (int i = 0; i < array.Length / 2; i++)
    {
      if (array[i * 2] > array[i * 2 + 1])
      {
        Replace(array, i * 2, i * 2 + 1);
        change++;
      }
    }
    ++proxod;
    if (proxod == 2)
      if (change == 0)
        result = 0;
      else
      {
        proxod = 0;
        change = 0;
      }
    for (int i = 0; i < (array.Length % 2 == 0 ? array.Length / 2 - 1 : array.Length); i++)
    {
      if (array[i * 2 + 1] > array[i * 2 + 2])
      {
        Replace(array, i * 2 + 1, i * 2 + 2);
        change++;
      }
    }
    ++proxod;
    if (proxod == 2)
      if (change == 0)
        result = 0;
      else
      {
        proxod = 0;
        change = 0;
      }
  }
  while (result != 0);
  return array;
}

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

В этой сортировке сравниваются не соседние элементы массива. Расстояние между ними вычисляется для каждого прохода по формуле: delta = delta / 1.247, где delta первого прохода равняется количеству элементов в массиве. Значение delta при этом округляется до ближайшего целого. Поясним для массива с длиной 10:

1. delta = 10 / 1.247 = 8.02
2. delta = 8 / 1.247 = 6.42
3. delta = 6 / 1.247 = 4.81
4. delta = 5 / 1.247 = 4.01
5. delta = 4 / 1.247 = 3.21
6. delta = 3 / 1.247 = 2.41

После того, как округлённое значение delta становится равным 2, происходит досортировка пузырьком.

Худшая временная сложность - O(n*n)

Лучшая временная сложность - (n * lg(n))

Среднее значение сложности - (n*n / 2 в степени p)

static int[] Comb(int[] array)
{
  double smallFactor = 1.247;
  int length = array.Length;
  int koef = (int)Math.Round(array.Length / smallFactor);
  while (koef != 2)
  {
    for (int i = 0; i <= length - koef; i++)
    {
      if (array[i] > array[i + koef - 1])
        Replace(array, i, i + koef - 1);
    }
    koef = (int)Math.Round(koef / smallFactor);                
  }
  int success = 0;
  while (success < length - 1)
  {
    success = 0;
    for (int i = 0; i < length - 1; i++)
    {
      if (array[i] > array[i + 1])
        Replace(array, i, i + 1);
      else
        success++;
    }
  }
  return array;
}

Источник

https://m.habr.com/ru/post/204600

Ещё больше интересной информации на нашем Telegram канале.