как сохранить время цикла в Bubble-Sort Fuction в C - PullRequest
Новая
       14

как сохранить время цикла в Bubble-Sort Fuction в C

0 голосов
/ 30 декабря 2018

Я пытаюсь создать свою собственную функцию сортировки пузырьков на языке C. Как вы можете видеть нижеприведенный код, я пытаюсь использовать только цикл while / if для создания этой функции.Я поставил 5 чисел (1,3,2,5,4), чтобы размер этого массива был 5, и я получил 5 (я проверил это с помощью Python (C) tutor. Однако, он хорошо работает до tab [j]] получить 3. Я пытаюсь понять это, но не могу понять, почему он продолжает выходить, когда вкладка [j] получает 3. Не могли бы вы мне объяснить? Я был бы признателен.

Большое спасибо.

Вот мой код ниже: 

#include <stdio.h>

void ft_sort_integer_table(int *tab, int size)
{
    int i;
    int j;
    int tem;

    i = 0;
    j = 0;
    while(tab[i] < size)
    {
        if(tab[j] > tab[j+1])
        {
            tem = tab[j];
            tab[j] = tab[j+1];
            tab[j+1] = tem;
            printf("%d ", tab[j]);
            j++;
        }
        else if(tab[j] < tab[j+1])
        {
          printf("%d ",tab[j]);
          j++;
        }
        i++;
    }
}

int main(void)
{
    int tab[] = {1,3,2,5,4};
    int size = sizeof(tab)/sizeof(*tab);
    ft_sort_integer_table(tab, size);
    return(0);
}

Ответы [ 2 ]

0 голосов
/ 30 декабря 2018

Вам понадобится внутренний цикл в пузырьковой сортировке, который отвечает за перемещение самого большого элемента назад и выполнение перестановок i раз (эти большие элементы "пузырятся").Начните внутренний цикл в 0 на каждой итерации и итерируйте до size - i (мы знаем, что последние i элементы отсортированы и находятся в их конечных позициях).

i контролирует ваш внешний цикл идолжен быть увеличен в конце цикла (так же, как если бы вы использовали цикл for).j управляет внутренним циклом и должно увеличиваться в конце цикла.

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

Также стоит отметить, что (1) for циклы здесь более семантически уместны и (2) есть оптимизация, доступная путем добавленияboolean - как только вы пройдете через внутренний цикл, который не выполняет перестановок, закончите рано! 

#include <stdio.h>

void ft_sort_integer_table(int *tab, int size)
{
    int i = 0, j, tem;

    while (i < size)
    {
        j = 0;

        while (j < size - i)
        {
            if (tab[j] > tab[j+1])
            {
                tem = tab[j];
                tab[j] = tab[j+1];
                tab[j+1] = tem;
            }

            j++;
        }

        i++;
    }
}

int main(void)
{
    int tab[] = {1,3,2,5,4,6,7,1,5,6,8,9,1,4,5,1,2};
    int size = sizeof(tab) / sizeof(*tab);
    ft_sort_integer_table(tab, size);

    for (int i = 0; i < size; i++) 
    {
        printf("%d ", tab[i]);
    }

    return(0);
}

Вывод: 

1 1 1 1 2 2 3 4 4 5 5 5 6 6 7 8 9

Попробуйте!

0 голосов
/ 30 декабря 2018

Я пытаюсь понять это, но не могу понять, почему он продолжает работать, когда вкладка [j] получает 3.

Из вашего кода выше, jприращение таким же образом, как я.Это означает, что обе переменные будут иметь одинаковое значение, так как j будет увеличиваться на единицу после оператора if-then-else, и я также буду увеличиваться на единицу в конце каждого цикла.Поэтому tab [j] ссылается на то же значение, что и tab [i]

. С учетом сказанного, логическое условие в цикле while проверяет, меньше ли значение на вкладке [i], чем значениеразмер.

Когда i == 3, tab [i] == 5, поскольку в цикле меняются / меняются только значения в массиве индекса, меньшего, чем i.Поскольку переменная размера содержит это значение 5, tab [i]

Дополнительную информацию о сортировке пузырьков можно найти здесь, https://www.geeksforgeeks.org/bubble-sort/

...