Более быстрый вариант сортировки пузырьков с использованием бинарного подхода - PullRequest
Новая
       14

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

0 голосов
/ 21 апреля 2019

Я занимался подготовкой вопросов к собеседованию и в процессе предложил небольшой вариант Bubble Sort, который включает в себя то, что я узнал о бинарном поиске, во внутренний цикл подкачки.Таким образом, временная сложность приводит к примерно 50% -ному снижению по сравнению с O (n ^ 2).Я предполагаю, что мой вопрос - я трачу свое время на Bubble?Должен ли я просто изучить Bucket Sort и покончить с этим?

Я тестировал со следующим вводом. 

int[] nums = { 9878, 1, 4, 8, 5, 7, 88, 1, 54, 2, 2, 9878, 5, 7, 3, 11, 1, 4, 8, 5, 7, 88, 1, 54, 2, 2, 5, 7, 3, 11 };

public static int[] sortWBinary(int[] ar)
{
      var swapped = true;
      for (int i = 0; i < ar.Length && swapped; i++)
      {
          swapped = false;
          for (int k = i, j = ar.Length - 1; k < ar.Length - i - 1 && j > 0; k++, j--)
          {
              if (ar[k] > ar[k + 1])
              {
                  var temp = ar[k];
                  ar[k] = ar[k + 1];
                  ar[k + 1] = temp;
                  swapped = true;
              }

              if (ar[j - 1] > ar[j])
              {
                  var temp = ar[j - 1];
                  ar[j - 1] = ar[j];
                  ar[j] = temp;
                  swapped = true;
              }

          }
      }

      return ar;
  }

VS. 

public static int[] sortWoBinary(int[] ar)
{
    var swapped = true;
    for (int i = 0; i < ar.Length && swapped; i++)
    {
        swapped = false;
        for (int k = 0; k < ar.Length - i - 1; k++)
        {
            if (ar[k] > ar[k + 1])
            {
                var temp = ar[k];
                ar[k] = ar[k + 1];
                ar[k + 1] = temp;
                swapped = true;
            }
        }
    }
    return ar;
}

1 Ответ

0 голосов
/ 22 апреля 2019

Для сортировки узнайте разницу между O(n log(n)) и O(n^2) и знайте, что вы всегда хотите использовать первое, если у вас достаточно данных, чтобы заботиться о том, что вы делаете.

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

  1. Что бы ни было в вашей библиотеке. Любой программист, который не знает, как достичь этого в первую очередь, представляет опасность для их кодовой базы и по этой причине не должен быть нанят.
  2. Внешние инструменты сортировки, такие как утилита Unix sort или функция ORDER BY в SQL. Когда вам нужно перебрать данные и сделать выбор, не засасывайте их в свою память, чтобы отсортировать, сначала сделайте их более эффективными.
  3. Слияние сортировки. (Для экспертов.) Ровно дважды в моей жизни мне нужно было написать сорт, и первых двух вариантов не хватило. Оба раза это была одна и та же история. Слишком много данных, чтобы использовать библиотечную процедуру, и не подходит для внешних инструментов по сложному ряду причин. Так что это должна быть внешняя сортировка (т.е. промежуточный файл хранится в памяти на диске). Если вам нужно написать внешнюю сортировку, сортировка слиянием - ваш друг.
  4. Quicksort. (При опросе экспертов-подражателей.) Иногда кто-то спрашивает вас, как на самом деле работает сортировка библиотеки. Я бы сказал: «Есть много способов, которыми это может работать, но долгое время быстрая сортировка была стандартом. Вы хотите, чтобы я показал, как это работает?» Обычно это ответ, который они хотят. Редко можно найти кого-то, кто знает, что быстрая сортировка была в значительной степени заменена тимсортом. Кто-то, кто действительно может копать дальше, и ему говорят: «В течение этого столетия платформы двигались в сторону тимсорта. Он был изобретен для Python, и был адаптирован для Java, Chrome и других платформ. Я должен был бы посмотреть, как он работает. «
  5. Radix sort. (При опросе smartasses.) Если кто-то спросит вас, можете ли вы сортировать быстрее, чем O(n log(n)), вам нужно знать об этом. Знание ответа, скорее всего, заставит их работать усерднее, чтобы показать, что их полномочия ботаника лучше, чем у вас. Это было бы знаком с моим желанием работать с ними.
...