Какова должна быть временная сложность моего алгоритма сортировки?

Question

Вчера я пошел на собеседование,

Он попросил меня написать программу для сортировки массива в порядке возрастания.

Я написал программу, которая заключается в следующем,

var mySortOne = function(myArray){ 
    var num = 0, 
     temp = 0, 
     isSwipe = false, 
     counter = 0;  

    for(num = 0; num < myArray.length; num++){ 
     print((++counter)+" => "+myArray); 
     if (((num+1) < myArray.length) && (myArray[num] > myArray[num+1])){ 
      temp = myArray[num+1]; 
      myArray[num + 1] = myArray[num]; 
      myArray[num] = temp; 
      isSwipe = true; 
     } 
     if(isSwipe){ 
      isSwipe = false; 
      num = -1; 
     } 
    } 

    print("\n FINAL "+myArray); 
}; 

mySortOne([45,12,78,22,4]); 

Интервьюер не был удовлетворен, он сказал: «Я не прошу для оптимального решения, но ваш алгоритм сортировки является худшим, что п^2.»

Так что я написал второе решение, которое заключается в следующем,

var mySortTwo = function(myArray){ 
    var num = 0, 
     MAX = myArray.length, 
     isSwipe = false, 
     temp = 0, 
     counter = 0; 

    do{ 
     isSwipe = false; 
     for(num = 0; num < MAX; num++){ 
      print((++counter)+" => "+myArray); 
      if(((num + 1) < MAX) && (myArray[num] > myArray[num+1])){ 
       temp = myArray[num + 1]; 
       myArray[num + 1] = myArray[num]; 
       myArray[num] = temp; 
       isSwipe = true;    
      } 
     } 
     MAX--; 
    }while(isSwipe); 

    print("\n FINAL "+myArray); 
}; 

mySortTwo([45,12,78,22,4]); 

Но до сих пор он не был удовлетворен.

У меня были некоторые операторы печати обоих алгоритмов.

выход первого алгоритма является

1 => 45,12,78,22,4 
2 => 12,45,78,22,4 
3 => 12,45,78,22,4 
4 => 12,45,78,22,4 
5 => 12,45,22,78,4 
6 => 12,45,22,78,4 
7 => 12,22,45,78,4 
8 => 12,22,45,78,4 
9 => 12,22,45,78,4 
10 => 12,22,45,78,4 
11 => 12,22,45,4,78 
12 => 12,22,45,4,78 
13 => 12,22,45,4,78 
14 => 12,22,4,45,78 
15 => 12,22,4,45,78 
16 => 12,4,22,45,78 
17 => 4,12,22,45,78 
18 => 4,12,22,45,78 
19 => 4,12,22,45,78 
20 => 4,12,22,45,78 
21 => 4,12,22,45,78 

FINAL 4,12,22,45,78 

И выход второго алгоритма заключается в следующем,

1 => 45,12,78,22,4 
2 => 12,45,78,22,4 
3 => 12,45,78,22,4 
4 => 12,45,22,78,4 
5 => 12,45,22,4,78 
6 => 12,45,22,4,78 
7 => 12,45,22,4,78 
8 => 12,22,45,4,78 
9 => 12,22,4,45,78 
10 => 12,22,4,45,78 
11 => 12,22,4,45,78 
12 => 12,4,22,45,78 
13 => 12,4,22,45,78 
14 => 4,12,22,45,78 
15 => 4,12,22,45,78 

FINAL 4,12,22,45,78 

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

Но то, что я считаю моим вторым решением, является самой пузырной сортировкой.

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

Answer 1

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

1. Когда кто-то говорит, что алгоритм является O (N^2), что они означают время это займет, будет пропорциональна п^2, поэтому при двойном н, время станет в 4 раза (примерно). Это связано с тем, что число петель увеличивается. т. е. для O (n^2) существует n петель, причем каждая петля повторяется n раз или меньше. При сортировке пузырьков в каждом цикле происходит разворот . В вашем случае в каждом свопе запускается новый цикл. Так что сложность увеличилась на одну величину. Таким образом, ваш алгоритм O (n^3).

2. isSwipe, который вы использовали, является одной из лучших вещей о сортировке пузырьков. Это дает алгоритму возможность определять, отсортирован ли массив и остановить дальнейшую обработку. Таким образом, наилучшая сложность случая становится o (n), но в выборе сортировки ее все еще o (n^2). В вашем случае isSwipe был бесполезен. Поскольку для сравнения установлено значение true, оно становится истинным, когда сравнение возвращает true, а так как n устанавливается в -1, если isSwipe имеет значение true, n устанавливается равным -1, если сравнение возвращает true. Так что я могу изменить свой алгоритм к этому, и это дало бы тот же результат:

   var mySortOne = function(myArray){ 
       var num = 0, 
       temp = 0, 
       isSwipe = false, 
       counter = 0;  
   
       for(num = 0; num < myArray.length; num++){ 
        print((++counter)+" => "+myArray); 
        if (((num+1) < myArray.length) && (myArray[num] > myArray[num+1])){ 
         temp = myArray[num+1]; 
         myArray[num + 1] = myArray[num]; 
         myArray[num] = temp; 
         num = -1; 
        } 
       } 
       print("\n FINAL "+myArray); 
   }; 
   

   или короче, вы не используете isSwipe вообще.

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

Answer 2

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

Answer 3

1. Да, оба ваших алгоритма слишком много итерации. Они имеют сложность O(n*n). В случае небольшого n - ваш алгоритм хорош. Однако this JSFiddle shows, что для n = 100000, MergeSort сортирует массив на 263 мс, пока ваш вид занимает 100 раз больше - 23901мс (24 секунды!) Для завершения.

2. Оба алгоритма являются видами BubbleSort. Однако ваш код слишком сложный, имея такую ​​же сложность. Как я думаю, «у нас может быть лучшее решение с использованием простой сортировки пузырьков» означает «Мы могли бы написать простой BubbleSort и иметь тот же результат».

3. Улучшение алгоритма медленной сортировки, вероятно, не самый лучший вариант. Вы можете выбрать другой. Существует много алгоритмов, которые работают для O(n*log(n)). Что касается меня, я предпочитаю MergeSort и HeapSort, потому что забываю, как работает QuickSort. Более того, MergeSort является стабильным алгоритмом сортировки.

Answer 4

Оба ваших алгоритмов Bubble sort, потому что вы сравниваете и своп смежных элементов. Я не проверял, действительно ли они работают, но по крайней мере предполагаемая логика выглядит правильно.

Первый, вопреки видимости, является предназначен быть Bubble рода. Число для петель не диктует число итераций. См. here для примера сортировки Bubble, который использует один цикл.

Однако ваша первая реализация выглядит O(n^3), потому что вы перезагружаете переменную итерации после каждой свопинга. Если вы настаиваете на использовании одного цикла, я предлагаю вам цикл до n^2 и устранить сброс, который вы делаете, как вы можете видеть в предыдущей ссылке. Благодаря Tali для указания этого.

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

do{ 
    isSwipe = false; 
    newMax = 0; 
    for(num = 0; num < MAX; num++){ 
     print((++counter)+" => "+myArray); 
     if(((num + 1) < MAX) && (myArray[num] > myArray[num+1])){ 
      temp = myArray[num + 1]; 
      myArray[num + 1] = myArray[num]; 
      myArray[num] = temp; 
      isSwipe = true;    
      newMax = i + 1; ///////////////////// here //////////////////// 
     } 
    } 
    MAX = newMax; 
    // no need for this anymore MAX--; 
}while(isSwipe); 

Но он по-прежнему будет квадратным. Однако - это, но оптимизация могла бы быть выполнена.

Более продвинутая оптимизация - Cocktail sort, но это также квадратично в худшем случае.