Столкнувшись с трудностью в алгоритме сортировки пузырьков в C

Question

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

#include <stdio.h>

int main() {
    int ctr, inner, outer, didSwap, temp;
    int nums[10] = {
        78,
        16,
        21,
        7,
        13,
        9,
        22,
        52,
        67,
        19
    };

    //Listing the array before sorting

    for (ctr = 0; ctr < 10; ctr++) {
        printf("%d\n", nums[ctr]);
    }

    //Sorting the arrays

    for (outer = 0; outer < 9; outer++) {
        didSwap = 0;
        for (inner = outer; inner < 10; inner++) {
            if (nums[inner] < nums[outer]) {
                temp = nums[inner];
                nums[inner] = nums[outer];
                nums[outer] = temp;
                didSwap = 1;
            }
        }
        if (didSwap == 0) {
            break;
        }
    }

    //Listing the array after sorting

    printf("\n\nThis is the sorted array\n");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%d\n", nums[ctr]);
    }

    return 0;
}

Код работает нормально, но я хочу понять, как во втором для l oop написано inner = outer, и в следующем операторе if сравниваются элементы массива, в которых один из них имеет тот же номер, что и внутренний, а другой - тот же номер, что и внешний. И поскольку мы сказали, что inner = outer, это означает, что мы сравниваем один и тот же элемент. Я думаю об этом, если outer = 0, а с inner = outer, то inner тоже будет 0, поэтому следующий оператор if будет if (nums[0] < nums[0]), и это не имеет никакого смысла.

Я знаю, что я, вероятно, ошибаюсь, потому что код работает нормально, но что я не так думаю?

Заранее спасибо.

Answer 1

Суть вашей Bubble Sort заключается в том, что при каждом сканировании «пузырь» является наибольшим значением, которое когда-либо наблюдалось, поэтому в конце сканирования наибольшее значение «пузырилось» до самого верха. Затем вы повторяете с самого начала, но каждый раз (ясно) у вас появляется на одну меньшую ценность, которую вы должны учитывать. Кроме того, если в конце сканирования ничего не перемещается, тогда все в порядке, и вы можете остановиться.

Таким образом, Bubble Sort может выглядеть следующим образом:

    for (int n = 10 ; n > 0 ; n--)
      {
        bool no_swaps ;

        no_swaps = true ;
        for (int i = 1 ; i < n ; ++i)
          {
            if (nums[i-1] > nums[i])
              {
                int temp ;
                temp = nums[i-1];
                nums[i-1] = nums[i];
                nums[i]   = temp;
                no_swaps = false ;
              } ;
          } ;

        if (no_swaps)
          break ;
      } ;

Или:

    for (int n = 10 ; n > 0 ; n--)
      {
        bool no_swaps ;
        int bubb ;

        no_swaps = true ;
        bubb = nums[0] ;
        for (int i = 1 ; i < n ; ++i)
          {
            int this ;

            this = nums[i] ;
            if (bubb <= this)
              bubb = this ;
            else
              {
                nums[i-1] = this ;
                nums[i]   = bubb ;
                no_swaps = false;
              } ;
          } ;

        if (no_swaps)
          break ;
      } ;

, что, возможно, проясняет, что одноименный «пузырь» (bubb) является наибольшим значением, найденным в текущем сканировании (или самым правым наибольшим, если видели 2 или более с этим значением ).

Если вы удалите didSwap из своего списка, он будет работать нормально. Как и Bubble Sort, каждый проход вашего рода перемещает один элемент в конечный пункт назначения. Ваша сортировка всегда выполняет (n-1)*(n-2)/2 сравнения, что соответствует наихудшему случаю для Bubble Sort. Но лучший вариант сортировки пузырьков - (n-1) - если значения уже в порядке!

Так что настоящая Bubble Sort имеет преимущество перед вашим видом. Тем не менее, Bubble Sort также обычно O (n ^ 2) и, следовательно, примерно так же полезен, как шоколадный чайник, за исключением случаев, когда n маленький.

Answer 2

Это не глупый вопрос. Вы успешно заметили неэффективность. Внутренняя l oop первая итерация действительно бессмысленна, но не вызовет никаких проблем. Правильный путь - начать с outer + 1 вместо outer.

Answer 3

Что если ваш массив уже имеет наибольшее (или наименьшее число) на первой позиции. Ваша программа остановится, когда external равно 0. (Потому что didSwap равен 0). Если вы хотите использовать некоторые переменные, такие как didSwap или lastSwapIndex, пузырьковая сортировка следует сравнить массив [x] и массив [x-1]. Ваш алгоритм выглядит как сортировка Selection больше, чем Bubble sort.

Answer 4

Действительно, инициализация inner во внутреннем l oop может быть изменена на inner = outer + 1, так как тест всегда будет ложным в первой итерации.

Обратите внимание, однако что если первый элемент также является наименьшим, все тесты в этом inner l oop будут ложными, а didSwap не будет установлен в 1, вызывая external Я oop, чтобы остановиться тоже. Это неправильно, если остальная часть массива не отсортирована.

Вы можете решить эту проблему, изменив l oop на:

for (outer = 0; outer < 9; outer++) {
    for (inner = outer + 1; inner < 10; inner++) {
        if (nums[inner] < nums[outer]) {
            temp = nums[inner];
            nums[inner] = nums[outer];
            nums[outer] = temp;
        }
    }
}

, который будет выполнять 45 итераций во всех случаях .

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

for (outer = 10; outer-- > 0; ) {
    didSwap = 0;
    for (inner = 0; inner < outer; inner++) {
        if (nums[inner] > nums[inner + 1]) {
            temp = nums[inner];
            nums[inner] = nums[inner + 1];
            nums[inner + 1] = temp;
            didSwap = 1;
        }
    }
    if (didSwap == 0) {
        break;
    }
}

Это будет выполняться за линейное время, если массив уже отсортирован, но все еще принять O (N ² ) итераций в среднем.