Смущен этим вложенным циклом - PullRequest
Новая
       17

Смущен этим вложенным циклом

0 голосов
/ 21 июня 2019

Почему это для цикла печати / сортировки всех 10 целых чисел. Он начинается с i = N - 1, который больше или равен 0, поэтому он переходит к следующему циклу for. Здесь J равно 1, которое меньше или равно i, поэтому оно компилируется.

У меня проблема в том, что первая итерация будет i = 9 и j = 1, 8 и 2, 7 и 3, 6 и 4, 5 и 5 и наконец 4 и 6 (точка остановки),

где j не меньше или равно i. Разве он не должен компилироваться только столько раз, сколько он запускает 5 раз вместо 10, которые он выполняет 

#include <stdio.h>

int arr[10] = { 3,6,1,2,3,8,4,1,7,2};

void bubble(int a[], int N);

int main(void)
{
    int i;
    putchar('\n');
    for (i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    bubble(arr,10);
    putchar('\n');

    for (i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

void bubble(int a[], int N)
{
    int i, j, t;
    for (i = N-1; i >= 0; i--)
    {
        for (j = 1; j <= i; j++)
        {
            if (a[j-1] > a[j])
            {
                t = a[j-1];
                a[j-1] = a[j];
                a[j] = t;
            }
        }
    }
}

Конкретный код, которым я не оборачиваюсь, это 

for (i = N-1; i >= 0; i--)
{
    for (j = 1; j <= i; j++)
    {
        if (a[j-1] > a[j])
        {
            t = a[j-1];
            a[j-1] = a[j];
            a[j] = t;
        }
    }
}

Результат верен и возвращает правильный массив отсортированных целых чисел

Ответы [ 2 ]

1 голос
/ 21 июня 2019

2 петли являются вложенными. Поведение заключается в том, что для каждой итерации внешнего цикла выполняется полный внутренний цикл. Это означает, что для фиксированного i, j принимает значения от 1 до i: 

i = 9, j = 1;
i = 9, j = 2;
i = 9, j = 3;
...
i = 9, j = 9;

Теперь выполнение заканчивается во внутреннем цикле и возвращается к внешнему, уменьшая значение i. 

i = 8, j = 1;
i = 8, j = 2;
...
i = 8, j = 8;

i = 7, j = 1;
...
i = 7, j = 7

i = 6, j = 1
...
i = 6, j = 6

Это продолжается до тех пор, пока вы не доберетесь до i = 1, j = 1. Что касается типа пузырьков, я думаю, что вы можете найти некоторые интересные визуализации в Интернете, например, https://www.youtube.com/watch?v=67k3I2GxTH8

0 голосов
/ 21 июня 2019

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

Это потому, что в пузырьковой сортировке в конце каждой итерации максимальный элемент в массиве от 0 до (N - i) (где N = размер массива, а i - номер итерации, учитывая, что он варьируется от 1 до N), устанавливается в его фактическое положение

Давайте рассмотрим пример массива A = {2, 5, 6, 1, 9, 8}

после 1-й итерации A = {2, 5, 1, 6, 8, 9}

после 2-й итерации A = {2, 1, 5, 6, 8, 9}

после 3-й итерации A = {1, 2, 5, 6, 8, 9}

после 4-й итерации A = {1, 2, 5, 6, 8, 9}

после 5-й итерации A = {1, 2, 5, 6, 8, 9}

Как видите, после 1-й итерации 9 - самый высокий элемент, находится в правильной позиции Аналогично во 2-й итерации 8 есть, в 3-й итерации 6 есть и т. Д.

Надеюсь, это было полезно.

...