Алгоритм сортировки пузырьков в C - Это так? - PullRequest
Новая
       7

Алгоритм сортировки пузырьков в C - Это так?

1 голос
/ 08 февраля 2020

В настоящее время я учусь на CS50x.

Я увлекаюсь алгоритмами поиска и сортировки. Пытаясь понять их в коде. Теперь по топике c пузырьковой сортировки: я создал то, что я считаю алгоритмом пузырьковой сортировки. Но я не мог вписаться в идею подсчета свопа, который должен быть установлен в ненулевое значение. Мой алгоритм (ниже) сортирует все числа. Куда бы я вписался в идею обмена? Если бы кто-то мог так любезно объяснить, я был бы очень благодарен. 


#import <stdio.h>
#import <cs50.h>

int main(void)
{

    // Creating an unsorted array

    int count = 10;

    int array[count];

    for (int z = 0; z < count; z++)
        scanf("%i", &array[z]);


    // Bubble Sort

    int buffer;

    for (int b = 0; b < count; b++)
    {

        int a = 0;

        while (a < count)
        {
            if (array[a] > array[a+1])
            {
                buffer = array[a];
                array[a] = array[a+1];
                array[a+1] = buffer;
            }
            a++;
        }

    }

    printf("Sorted: ");

    for (int b = 0; b < count; b++)
        printf("%i ", array[b]);

    printf("\n");

}

1 Ответ

1 голос
/ 13 февраля 2020

Директива #include, а не #import. Идея подсчета свопов состоит в том, чтобы сломать внешний l oop, если ничего не выходит из последовательности (потому что во внутреннем l oop не было необходимости в свопах). Этот код реализует следующее: 

#include <stdio.h>

int main(void)
{
    // Creating an unsorted array
    int count = 10;
    int array[count];

    for (int z = 0; z < count; z++)
        scanf("%i", &array[z]);

    putchar('\n');
    printf("%8s:", "Unsorted");
    for (int b = 0; b < count; b++)
        printf(" %i", array[b]);
    printf("\n");

    // Bubble Sort
    for (int b = 0; b < count; b++)
    {
        int a = 0;
        int num_swaps = 0;

        while (a < count - 1)
        {
            if (array[a] > array[a+1])
            {
                int buffer = array[a];
                array[a] = array[a+1];
                array[a+1] = buffer;
                num_swaps++;
            }
            a++;
        }
        if (num_swaps == 0)
            break;
    }

    printf("%8s:", "Sorted");
    for (int b = 0; b < count; b++)
        printf(" %i", array[b]);
    printf("\n");

    return 0;
}

Образцы прогонов (источник bs97.c скомпилирован в bs97; генератор случайных чисел домашнего приготовления random - используемые опции генерируют 10 чисел от 10 до 99 включительно): 

$ random -n 10 10 99 | bs97

Unsorted: 68 47 85 39 52 54 31 81 19 59
  Sorted: 19 31 39 47 52 54 59 68 81 85
$ random -n 10 10 99 | bs97

Unsorted: 75 85 36 11 35 87 59 63 26 36 
  Sorted: 11 26 35 36 36 59 63 75 85 87 
$ random -n 10 10 99 | bs97

Unsorted: 90 27 64 90 76 79 52 46 98 99
  Sorted: 27 46 52 64 76 79 90 90 98 99
$ random -n 10 10 99 | bs97

Unsorted: 53 60 87 89 38 68 73 10 69 84
  Sorted: 10 38 53 60 68 69 73 84 87 89
$

Обратите внимание, что код избегает конечных пробелов в выводе.

Вы также можете определить int num_swaps = 1; вне сортировки for l oop и проверить его в главном l oop условие: 

for (int b = 0; b < count - 1 && num_swaps > 0; b++)
{
    num_swaps = 0;

и уберите if (num_swaps == 0) break; с конца l oop. Внутренний l oop тоже может быть for l oop. И первый цикл внешнего l oop перемещает наибольшее значение в конец массива, так что вы можете сократить внутренний цикл, чтобы у него было меньше работы. Код печати также должен быть включен в функцию. 

#include <stdio.h>

static void dump_array(const char *tag, int size, int data[size])
{
    printf("%8s (%d):", tag, size);
    for (int i = 0; i < size; i++)
        printf(" %i", data[i]);
    printf("\n");
}

int main(void)
{
    // Creating an unsorted array
    int count = 10;
    int array[count];

    for (int z = 0; z < count; z++)
    {
        if (scanf("%i", &array[z]) != 1)
        {
            fprintf(stderr, "Failed to read number %d\n", z + 1);
            return 1;
        }
    }

    putchar('\n');
    dump_array("Unsorted", count, array);

    // Bubble Sort
    int num_swaps = 1;
    for (int b = 0; b < count - 1 && num_swaps > 0; b++)
    {
        num_swaps = 0;
        for (int a = 0; a < count - b - 1; a++)
        {
            if (array[a] > array[a + 1])
            {
                int buffer = array[a];
                array[a] = array[a + 1];
                array[a + 1] = buffer;
                num_swaps++;
            }
        }
    }

    dump_array("Sorted", count, array);

    return 0;
}

Пример вывода: 

$ random -n 10 10 99 | bs97

Unsorted (10): 31 82 81 40 12 17 70 44 90 12
  Sorted (10): 12 12 17 31 40 44 70 81 82 90
$
...