Алгоритм сортировки вставками ведет себя по-разному, когда помещается в функцию - PullRequest
Новая
       38

Алгоритм сортировки вставками ведет себя по-разному, когда помещается в функцию

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

У меня есть следующий код для реализации сортировки вставкой: 

int main()
{   
    const int SIZE = 10;
    int a[SIZE] = {8, 6, 10, 2, 16, 4, 18, 14, 12, 10};

    //insertionSort(a, SIZE);

    // The following code is used in the insertionSort() function call above. To use the function, uncomment the function call above, and comment out the code below

    // Start of code used by insertionSort() function
    int temp;
    for (int i=1; i < SIZE; i++)
    {
        for (int j=i; a[j] < a[j-1]; j--)
        {
            temp = a[j];
            a[j] = a[j-1];
            a[j-1] = temp;
        }
    }
    // End of code used by insertionSort() function

    return 0;   
}

void insertionSort(int a[], const int SIZE)
{
    int temp;
    for (int i=1; i < SIZE; i++)
    {
        for (int j=i; a[j] < a[j-1]; j--)
        {
            temp = a[j];
            a[j] = a[j-1];
            a[j-1] = temp;
        }
    }
}

Алгоритм работает нормально, когда код используется в main (), но он выдает неправильные результаты при вызове с помощью inserttionSort ().

Я определил, что проблема заключается в следующем: условие внутреннего цикла (a [j] 0 && a [j]

Я хотел бы знать, почему это поведение проявляется только тогда, когда цикл выполняется внутри inserttionSort (), но не когда он выполняется в main ().

1 Ответ

3 голосов
/ 17 июня 2019

Эта петля 

    for (int j=i; a[j] < a[j-1]; j--)
    {
        temp = a[j];
        a[j] = a[j-1];
        a[j-1] = temp;
    }

вызывает неопределенное поведение, поскольку нет проверки, что j должно быть больше 0.

В противном случае, когда, например, j равно 0, доступ к массиву осуществляется с использованием индекса -1

a[0] < a[-1]

Вот демонстрационная программа с обновленным циклом 

#include <iostream>
#include <utility>

int main() 
{
    int a[] = { 8, 6, 10, 2, 16, 4, 18, 14, 12, 10 };
    const size_t SIZE = sizeof( a ) / sizeof( *a );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    for ( size_t i = 1; i < SIZE; i++ )
    {
        for ( size_t j = i; j != 0 && a[j] < a[j-1]; --j )
        {
            std::swap( a[j-1], a[j] );
        }
    }

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    return 0;
}

Его вывод 

8 6 10 2 16 4 18 14 12 10 
2 4 6 8 10 10 12 14 16 18

И включая алгоритм в функцию 

#include <iostream>
#include <utility>

void insertionSort( int a[], size_t n )
{
    for ( size_t i = 1; i < n; i++ )
    {
        for ( size_t j = i; j != 0 && a[j] < a[j-1]; --j )
        {
            std::swap( a[j-1], a[j] );
        }
    }
}

int main() 
{
    int a[] = { 8, 6, 10, 2, 16, 4, 18, 14, 12, 10 };
    const size_t SIZE = sizeof( a ) / sizeof( *a );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    insertionSort( a, SIZE );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    return 0;
}

Вывод такой же, как показано выше 

8 6 10 2 16 4 18 14 12 10 
2 4 6 8 10 10 12 14 16 18
...