Определите, полностью ли отсортирован массив

В настоящее время я создаю эту программу на языке C, целью которой является сортировка статического массива, содержащего несколько элементов, с помощью алгоритма сортировки пузырьков. Сортировка пузырьков может быть не быстрым и эффективным алгоритмом, но я использую его в образовательных целях.

Эта программа работает почти так, как я хотел, она выполняет сортировку, но у меня возникла следующая проблема:

  • Мой цикл do-while продолжает повторяться, даже если сам массив полностью отсортирован. Прямо сейчас он зацикливается навсегда, и я хочу, чтобы он остановился, когда весь массив будет правильно отсортирован.

Как я могу определить, отсортирован ли весь массив, а затем остановить итерацию, когда он будет полностью отсортирован?

Вот мой код:

#include <stdio.h> 

int main()
{
    int list[] = {5,1,5,4,3,2,1};
    int length = sizeof(list) / sizeof(int);

    printf("Unsorted array\n");
    printf("-----------------------------\n\n");

    for (int i = 0; i < length; i++)
    {
        if (i < length - 1)
            printf("%d, ", list[i]);
        else
            printf("%d", list[i]);
    }

    do
    {
        for (int i = 0; i < length - 1; i++)
        {

            if (list[i] > list[i + 1])
            {
                printf("\n* Moving %d and %d", list[i], list[i + 1]);
                int temp = list[i + 1];
                list[i + 1] = list[i];
                list[i] = temp;
            }

            else
            {
                getchar();
            }

            getchar();
        }
        printf("-----------------------------\n");

        for (int i = 0; i < length; i++)
        {
            if (i < length - 1)
                printf("%d, ", list[i]);
            else
                printf("%d", list[i]);
        }

    } while (1);

    printf("Goodbye!\n");
    getchar();
    return 0;
}
# arrays algorithm sorting
Источник
  • 0
    en.wikipedia.org/wiki/Bubble_sort объясняет, как узнать, когда прекратить работу.
Codelisting
за 0 против
Лучший ответ

Как вы думаете, почему ваша сортировка пузырей должна продолжаться вечно?

В конце одной итерации вашего внутреннего цикла for самый большой элемент «всплывет» (отсюда и название) до конца массива. Так что вы будете знать, что он находится в нужном месте.

Это означает, что на следующей итерации вам нужно будет отсортировать пузырьками только первуюlength - 2 элементы. На третьей итерации вам нужно будет отсортировать только первуюlength - 3 элементы и так далее, пока в какой-то момент вы не обнаружите, что сортируете первыеlength - length элементы. В этот момент вы знаете, что нужно остановиться.

Так что вашиdo ... while цикл может быть циклом for.

for (int sortLength = 1 ; sortLength < length ; ++ sortLength) // replaces your do while loop
{
    for (int i = 0 ; i < length - sortLength ; ++i)
    {
        // Element swap stuff same as before
    }

    // print loop same as before
}
за 2 против

Вы можете использоватьflag переменная, чтобы проверить, был ли обмен на предыдущей итерации. Если нет, массив уже отсортирован и выходит из цикла.

int flag = 0;
for (int i = 0; i < length - 1; i++)
{

    if (list[i] > list[i + 1])
    {
        printf("\n* Moving %d and %d", list[i], list[i + 1]);
        int temp = list[i + 1];
        list[i + 1] = list[i];
        list[i] = temp;
        flag = 1;
    }
    else
    {
        getchar();
    }

     getchar();
}

if (!flag) break;
за 1 против

Ваше письмо:

do [...] while (1)

это означает, что цикл while никогда не закончится,1 будет оцениватьсяtrue , если в цикле нет разрыва или перехода (спасибо Flikk).

  • 0
    Если в цикле нет разрыва или перехода
  • 0
    @Flikk, но его нет.
  • 0
    Я знаю об этой ситуации, но это было временное решение.
Codelisting
Популярные категории
На заметку программисту