Любопытный метод пузырчатой ​​сортировки

Question

Я создал простой скрипт для сортировки пузырьков, который принимает массивы и сортирует их. Это всего лишь фрагмент кода. Но это код, который сортирует его. Я хочу сделать это так: вместо того, чтобы делать примерно девять сравнений, например, на каждом проходе, модифицировать сортировку пузырьков, чтобы сделать восемь или менее сравнений на втором проходе, семь на третьем проходе и так далее. Я полностью потерян, как реализовать это. Какова будет лучшая идея для этого?

        int bubbleSortArray(int array[])
        {
            for(int i=0;i<10;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(array[i]>array[j])
                    {
                        swap(array[i], array[j]);
                        amountOfSwaps += 1;
                    }
                }
            }

        printArray(array);
        return amountOfSwaps;

        }


       void swap(int & value1, int & value2)
       {
              int temp=value1; 
              value1=value2;
              value2=temp;
       }

Answer 1

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

Вот пример массива и модификации, которые будут сделаны на каждой итерации. Круглые скобки обозначают, какая часть массива проверяется на каждой итерации:

(7)5 3 8 6 9 4 2 0 1
(7 5)3 8 6 9 4 2 0 1
(7 5 3)8 6 9 4 2 0 1
(8 7 5 3)6 9 4 2 0 1
(8 7 6 5 3)9 4 2 0 1
(9 8 7 6 5 3)4 2 0 1
(9 8 7 6 5 4 3)2 0 1
(9 8 7 6 5 4 3 2)0 1
(9 8 7 6 5 4 3 2 0)1
(9 8 7 6 5 4 3 2 1 0)

Как вы можете видеть в первый раз, когда на самом деле ничего не сделано, и никогда не будет, потому что вы сравниваете один элемент с самим собой. Во второй раз вы теперь сравниваете два элемента, затем три, и так далее.

Чтобы ваш код начинал со сравнения их всех, а затем каждый раз делал на единицу меньше (как говорится в вашем вопросе), вы должны изменить цикл на следующее (примечание j <10-i): </p>

    for(int i=0;i<10;i++)
    {
        for(int j=0;j<10-i;j++)
        {

В любом случае это равноценно и будет работать в конце. Далее вы можете пропустить первое сравнение с самим собой, установив i = 1:

for(int i=1;i<10;i++)
    {
        for(int j=0;j<10-i;j++)
        {

Это исключит первое сравнение, которое вы искали. Это еще одна оптимизация.

Answer 2

Я думаю, что у вас есть цикл на j немного назад.Я думаю, вам нужно что-то вроде:

for (int i = 0; i < 10; i++) {
    for (int j = 1; j < 10 - i; j++) {
        // ...
    }
}

Answer 3

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

int bubbleSort(int *arry, size_t size)
{
  bool swapped;
  size_t upper_bound = size;
  int amountOfSwaps = 0;

  do
  {
    swapped = false;
    for(int i = 1; i < upper_bound; ++i)
    {
      if(arry[i] < arry[i - 1])
      {
        swap(arry[i], arry[i - 1]);
        swapped = true;
        ++amountOfSwaps;
      }
    }
    --upper_bound;
  }while(swapped);

  return amountOfSwaps;
}