Bubble-Sort не сортируется в C (псевдокод Кормена) - PullRequest
0 голосов
/ 16 января 2019

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

Это мой подход к псевдокоду Кормена:

void BUBBLE_SORT(int a[200], int n) {
    int i, j, aux;

    for (i = 1; i <= n - 1; i++) {
        for (j = n; j < i + 1; j++) {
            if (a[j] < a[j - 1]) {
                aux = a[j];
                a[j] = a[j + 1];
                a[j + 1] = aux;
            }
        }
    }
}

Я попробовал другой фрагмент кода, найденный в интернете, но результат не изменился:

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

Я хотел бы знать, где мое понимание не помогло в понимании реализации Кормена и получить сортировку пузырьковработать!

Ответы [ 2 ]

0 голосов
/ 16 января 2019

Ошибки в вашей реализации:

  1. Вы начинаете считать ваш массив с 1-го индекса. Но в C программирование массива начинается с 0-й позиции. [Вы должны исправить i = 0 вместо i = 1]
  2. Внутренний цикл должен работать с j = n-1 с j = i + 1 и значением j должно уменьшаться.
  3. Вы сравниваете a [j] с a [j-1] но вы меняете a [j] с a [j + 1] . у вас должен быть обмен a [j] с a [j-1]

См. Изменения в коде ниже. Надеюсь, это будет полезно:

int i, j, aux;
for(i=0;i<n-1;i++){
    for(j=n-1;j>=i+1;j--){
        if(a[j]<a[j-1]){
            aux=a[j];
            a[j]=a[j-1];
            a[j-1]=aux;
        }
    }
}
0 голосов
/ 16 января 2019

Существует как минимум три вопроса:

  1. Псевдокод предполагает, что индексы массива идут от 1 до length. В массивах C индексируются от 0 до length-1; Ваш код не подходит для этого.

  2. Внутренний цикл в псевдокоде идет downto i+1, но ваш внутренний цикл пытается подсчитать up :

    for(j=n;j<i+1;j++)
    

    должно быть

    for (j = n; j > i; j--)
    
  3. Псевдокод меняет местами A[j] и A[j-1], но ваш код C меняет местами A[j] и A[j+1].

...