Эффективность/производительность алгоритма сортировки

Question

Я новичок в программировании и просто играл с сортировкой и сделал этот алгоритм. Он похож на пузырь, но он сравнивает не соседние пары, а пары, такие как: первый и второй, первый и третий .... второй и третий, второй и четвертый и т. Д. Не могли бы вы рассказать мне, какова эффективность/эффективность алгоритма или сравнить его с пузырем? Или, по крайней мере, посоветуйте мне, как решить проблему самостоятельно. Меня интересует, насколько пузырь лучше, чем этот. Спасибо.

void sortArray(int a[]) { 

int q, x, temp; 

for (q = 0; q < SIZE - 1; q++) { 
    for (x = q + 1; x < SIZE; x++) { 
     if (a[q] < a[x]) { 
      temp = a[q]; 
      a[q] = a[x]; 
      a[x] = temp; 
     } 
    } 
} 

}

Answer 1

Ваш вид похож на классический сорт пузыря и должен иметь по существу такую ​​же производительность.

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

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

Асимптотический, хотя все три сорта будет принимать O (N^2) время - в частности, будут N*(N-1)/2 итерации внутреннего контура.

Answer 2

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

Answer 3

Короткий ответ - ваш алгоритм имеет сложность O (n) - точно так же, как и пузырьковая сортировка, т. Е. Сложность обоих алгоритмов по существу одинакова.