Логика пузырьковой сортировки, количество итераций - PullRequest
Новая
       6

Логика пузырьковой сортировки, количество итераций

0 голосов
/ 30 октября 2018

У меня есть следующий код: 

// C program for implementation of Bubble sort 
#include <stdio.h> 

void swap(int *xp, int *yp) 
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} 

// A function to implement bubble sort 
void bubbleSort(int arr[], int n) 
{ 
   int i, j; 
   for (i = 0; i < n-1; i++)       

       // Last i elements are already in place    
       for (j = 0; j < n-i-1; j++)  
           if (arr[j] > arr[j+1]) 
              swap(&arr[j], &arr[j+1]); 
} 

/* Function to print an array */
void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("n"); 
} 

// Driver program to test above functions 
int main() 
{ 
    int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    bubbleSort(arr, n); 
    printf("Sorted array: \n"); 
    printArray(arr, n); 
    return 0; 
}

Единственная часть, которая меня смущает, это где i < n-1 в первом цикле for и J< n-i-1 во внутреннем цикле for внутри функции BubbleSort. Почему они оба не установлены на i <= n-1 и J<=n-i-1? Например, первая итерация будет равна n = 7, поэтому это означает, что она должна пройти цикл 6 раз во внешнем цикле и 6 раз во внутреннем цикле for. Но без знака <= это будет всего 5 итераций на цикл. На веб-сайте он показал, что оба цикла проходят 6 итераций, однако я не уверен, как бы это произошло без <=.

Источник: https://www.geeksforgeeks.org/bubble-sort/

1 Ответ

0 голосов
/ 30 октября 2018

Обратите внимание на использование arr[j+1]. Допустим, ваш массив имеет n = 7. Тогда, когда i = 0 и j = n - i - 1 = 6, вы получите доступ к arr[j+1] = arr[6 + 1] = arr[7]. Однако у arr было всего 7 элементов для начала, поэтому индекс 7 выходит за пределы, поскольку индексы начинаются с 0, а arr[6] является седьмым элементом.

Что касается того, почему это не имеет значения, последний элемент массива уже переставляется при сравнении его с последним элементом. Или, если в массиве только 1 элемент, он уже отсортирован.

...