C сортировка кода пузыря иногда не дает правильного вывода

Question

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

Оцените, кто-то может помочь, как решить эту проблему. C код и неверный вывод, как показано ниже

typedef struct
{
    char pname[2];
    int ptotime;
} data;

int main()
{
    int totalwait = 0;
    data name[] = {{'A', .ptotime = 4},
                   {'B', .ptotime = 6},
                   {'C', .ptotime = 3},
                   {'D', .ptotime = 7},
                   {'E', .ptotime = 2}};

    printf("Process Name\t Process Time \n");

    for (int j = 0; j < 5; j++)
    {
        printf("\t%s\t\t\t\t%d\n", name[j].pname, name[j].ptotime);
    }

    //Shortest job first (SJF) scheduling
    printf("\nShortest job first (SJF) scheduling \n");

    int swapped, temp;

    while (1)
    {
        swapped = 0;

        for (int x = 0; x < 5; x++)
        {
            if (name[x].ptotime >= name[x + 1].ptotime)
            {
                temp = name[x].ptotime;
                name[x].ptotime = name[x + 1].ptotime;
                name[x + 1].ptotime = temp;
                swapped = 1;
                char temp2[2];
                strcpy(temp2, name[x].pname);
                strcpy(name[x].pname, name[x + 1].pname);
                stpcpy(name[x + 1].pname, temp2);
            }
        }

        if (swapped == 0)
        {
            break;
        }
    }
    printf("Process Name\t Process Time \n");

    for (int j = 0; j < 5; j++)
    {
        printf("\t%s\t\t\t\t%d\n", name[j].pname, name[j].ptotime);
    }

    return 0;
}

Вывод

Process Name     Process Time
        A                               4
        B                               6
        C                               3
        D                               7
        E                               2

Shortest job first (SJF) scheduling
Process Name     Process Time
                                        0
        E                               2
        C                               3
        A                               4
        B                               6

Ожидаемый вывод

Process Name     Process Time
        A                               4
        B                               6
        C                               3
        D                               7
        E                               2

Shortest job first (SJF) scheduling
Process Name     Process Time
        E                               2
        C                               3
        A                               4
        B                               6
        D                               7

Answer 1

Для начинающих не используйте числа волхвов c как 5. Используйте именованные константы.

Имя массива инициализировано неправильно. Вы используете символьные литералы для инициализации элемента данных pname типа символьного массива без заключения символьных литералов в фигурные скобки.

data name[] = {{'A', .ptotime = 4},
                ^^^
//...

в этом l oop

    for (int x = 0; x < 5; x++)
    {
        if (name[x].ptotime >= name[x + 1].ptotime)
                                    ^^^^^
        //...

там это доступ за пределы массива. Таким образом, программа имеет неопределенное поведение.

Используйте локальные переменные, как, например, переменную swap в кратчайшей области, где они используются.

Чтобы поменять местами элементы имени массива, поменять местами не нужно каждый элемент данных каждого элемента массива. Вы можете поменять объекты целиком.

Вот демонстрационная программа.

#include <stdio.h>

typedef struct
{
    char pname[2];
    int ptotime;
} data;


int main( void ) 
{ 
    data name[] = 
    {
        { "A", .ptotime = 4 },
        { "B", .ptotime = 6 },
        { "C", .ptotime = 3 },
        { "D", .ptotime = 7 },
        { "E", .ptotime = 2 }
    };
    const size_t N = sizeof( name ) / sizeof( *name );

    printf("Process Name\t Process Time \n");

    for ( size_t i = 0; i < N; i++ ) 
    {
        printf( "\t%s\t\t\t\t%d\n", name[i].pname, name[i].ptotime );
    }

    putchar( '\n' );

    //Shortest job first (SJF) scheduling

    printf("\nShortest job first (SJF) scheduling \n");

    for ( int swapped = 1; swapped; )
    {
        swapped = 0;

        for ( int i = 1; i < N; i++ ) 
        {
            if ( name[i].ptotime < name[i-1].ptotime )
            {
                data tmp = name[i];
                name[i] = name[i-1];
                name[i-1] = tmp;

                swapped = 1;
            }
        }
    }

    printf("Process Name\t Process Time \n");

    for ( size_t i = 0; i < N; i++ ) 
    {
        printf( "\t%s\t\t\t\t%d\n", name[i].pname, name[i].ptotime );
    }

    return 0;
}

Ее вывод

Process Name     Process Time 
    A               4
    B               6
    C               3
    D               7
    E               2


Shortest job first (SJF) scheduling 
Process Name     Process Time 
    E               2
    C               3
    A               4
    B               6
    D               7

Answer 2

Изменение:

for(int x = 0; x < 5; x++) {

на:

for(int x = 0; x < 4; x++) {

Когда x=4, код сравнивается name[4] с name[5], но name[5] выходит за пределы ( единственными допустимыми элементами являются name[0] ... name[4]).

Answer 3

В вашем цикле обмена этот фрагмент кода:

for(int x = 0; x < 5; x++)

На последней итерации вы копируете значения от name[4+1] до name[4], то есть вы копируете значения 6-го элемента ваш массив из 5 элементов, это доступ за пределы ведьма неопределенное поведение .

Использование

for(int x = 0; x < 4; x++)

Таким образом, последний цикл будет копировать name[3+1] в name[3], 5-й элемент в 4-й элемент, с ожидаемым поведением.

Исправленный код

Answer 4

Здесь есть проблема:

for (int x = 0; x < 5; x++) {
      if (name[x].ptotime >= name[x + 1].ptotime) {

максимальное значение x может быть равно 4. Но тогда name[x + 1] получит доступ к одному элементу за пределами вашего массива, который имеет только 5 элементов. Доступ к массиву вне границ приводит к неопределенному поведению, и все ставки отключены.

Хотя могут быть и другие проблемы.