Возможная ошибка в программе Bubddle C - PullRequest
Новая
       13

Возможная ошибка в программе Bubddle C

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

Я читал книгу "Организация и проектирование компьютеров" Паттерсона и Хеннеси (5-е издание) и нашел этот код сортировки пузырьков: 

void sort (int v[], int n)
{
    int i,j;
    for (i=0; i<n; i+=1) {
        for (j = i-1; j>=0 && v[j] > v[j+1]; j+=1) {
            swap(v,j);
        }
    }
}

void swap (int v[], int k) {
    int temp;
    temp = v[k];
    v[k] = v[k+1];
    v[k+1] = temp;
}

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

Это код, который я использовал: 

#include <stdio.h>

void swap (int v[], int k) {
    int temp;
    temp = v[k];
    v[k] = v[k+1];
    v[k+1] = temp;
}

void sort (int v[], int n)
{
    int i,j;
    for (i=0; i<n; i+=1) {
        printf("%d \n", i);
        for (j = i-1; j>=0 && v[j] > v[j+1]; j+=1) {
            printf("%d, %d \n", i, j);
            swap(v,j);
        }
    }
}

int main() {
    int x[3] = {5,1,2};
    int N = 3;

    sort(x, N);
    for(int i = 0; i < 3; i++) {
        printf("%d ", x[i]);
    }
    return 0;
}

Это был результат: 

/Users/mauritsdescamps/Desktop/test/cmake-build-debug/test
0 
1 
1, 0 
1, 1 
1, 2 
1, 3 
1, 4 
2 
2, 1 
2, 2 
2, 3 

Process finished with exit code 6

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

1 Ответ

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

Я тоже пробовал этот код.Я скомпилировал его с помощью GCC, и как-то у меня это сработало (состояние выхода программы было 0 и массив был отсортирован правильно).Но я также думаю, что это проблема второго цикла.Я бы изменил инструкцию j + = 1 на j- = 1.В противном случае второй цикл может закончиться бесконечным циклом.Кроме того, я бы изменил инструкцию i = 0 в первом цикле на инструкцию ai = 1, потому что она закончилась бы ненужной итерацией.

...