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

Question

хорошо, так что я работаю с различными методами сортировки в C. самый базовый - "Bubble Sort" Таким образом, базовое определение пузырьковой сортировки - это замена двух последовательных блоков в массиве в зависимости от того, каким образом вы хотите их отсортировать. есть всего «n элементов», которые проверяются, чтобы поменять местами «n-1», и в конце компилятор запускает функцию еще раз, чтобы проверить, выполнена ли сортировка правильно, поэтому сложность времени равна O (n ^ 2 ).

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

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

#include<stdio.h>
int main()
{
        int n;
        printf("Enter the size of Array: ");
        scanf("%d",&n);
        int a[n];
        int i;
        printf("Enter The Elements Of Array:\n");
        for(i=0;i<n;i++)
        {
                scanf("%d",&a[i]);
        }
        for(i=0;i<n;i++)
        {
                int j;
                for(j=n-1;j>i;j--)
                {
                        if (a[j] < a[j-1])
                        {
                                int temp;
                                temp=a[j];
                                a[j]=a[j-1];
                                a[j-1]=temp;
                        }
                }
        }
        printf("\n\nSorted Array Is:  ");
        for(i=0;i<n;i++)
        {
                printf("%d  ",a[i]);
        }
        printf("\n");
        return 0;
}

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<stdio.h>
int main()
{
        int n;
        printf("Enter The Size Of Array: ");
        scanf("%d",&n);
        int a[n],i;
        printf("Enter The Elements Of Array:\n");
        for(i=0;i<n;i++)
        {
                scanf("%d",&a[i]);
        }
        int temp;
        for(i=0;i<n-1;i++)
        {
                int j;
                for(j=0;j<n-i-1;j++)
                {
                        if(a[j]>a[j+1])
                        {
                                temp=a[j];
                                a[j]=a[j+1];
                                a[j+1]=temp;
                        }
                }
        }
        printf("Sorted Array Is: ");
        for(i=0;i<n;i++)
        {
                printf("%d  ", a[i]);
        }
        printf("\n");
        return 0;
}

В Первой Программе обмен происходит с конечной части. Большее число выталкивается вперед. Во второй программе, обмен происходит с фронта. Меньшее число выдвигается к концу один за другим

Answer 1

На первый взгляд, да, за исключением незначительных ошибок, оба типа пузырей.Нет ничего особенного в том, в каком направлении идет пузырение;большинство реализаций всплывают «вверх» слева направо, но не существует жесткого и быстрого правила, которое запрещает пузыриться «вниз» справа налево.

Как правило, если возникает вопрос «Есть ли болееодин способ сделать это? ", в программировании ответ" Да ".

Answer 2

То, что у вас есть, не Bubble Sort. Пузырьковая сортировка выглядит так:

do {
   sorted = true
   sweep through the array, swapping adjacent elements into sorted order
   if we swap any elements, set sorted = false
} while (sorted == false)

Настоящая Bubble Sort не имеет внешнего предела с фиксированным числом итераций и не имеет внутреннего цикла, который выполняет меньше операций с увеличением количества итераций внешнего цикла. Да; эти аспекты дизайна глупы, но вот что такое Bubble Sort.

Существует более серьезный алгоритм, связанный с Bubble Sort, называемый Insertion Sort. Вид вставки такой:

dest_array = []   // start with empty destination array
for each element in source_array
   insert element at appropriate spot in dest_array

Сортировка вставкой может быть реализована в одном массиве. Первоначально весь массив состоит из source_array [], а dest_array [] - это область нулевой длины в конце source_array []:

[...source_array...][] <- dest array

. Мы начинаем сортировку, удаляя элемент e из source_array [] прямо на границе, где начинается dest_array []:

[...source_array...][e][]   <- [e] is removed from source_array

[...source_array...][   ]   <- dest_array acquires an empty spot

[...source-array...][e]     <- [e] is inserted into dest_array, in order

Мы продолжаем повторять это: source_array продолжает уменьшаться, а отсортированный dest_array увеличивается, пока не займет все пространство.

Insertion Sort имеет структуру, напоминающую ваш код: треугольная итерация с внешним циклом, который имеет фиксированное количество итераций, соответствующее количеству элементов, и внутренний цикл, который становится длиннее (так как dest_array увеличивается дольше). Вставка каждого элемента в правильное место в dest_array может быть выполнена серией перестановок смежных элементов.

То, что вы реализовали, называется Выбором сортировки. Вы постоянно выбираете самый высокий (или самый низкий) элемент из оставшегося source_array раздела и перемещаете его до конца, тем самым создавая dest_array раздел в порядке. У вас есть два варианта сортировки выбора: многократное перемещение самого высокого элемента в верхний раздел или многократное перемещение самого низкого элемента в нижний раздел. В любом случае этот верхний или нижний раздел займет весь массив, оставив его отсортированным.

Выбор сортировки, сортировка вставкой и сортировка по пузырькам - это разные алгоритмы. Bubble Sort - это своего рода шутка с двумя другими. Нет никакой причины использовать Bubble Sort вместо Selection или Insertion. Эти два являются респектабельными: они имеют свое применение, как сортировка небольшого количества вещей в крошечном пространстве. (Скажем, вам пришлось отсортировать небольшую таблицу значений в крошечный фрагмент машинного кода загрузчика или чего-то еще.)