Массив сохраняет одно и то же число из списка чисел дважды

Что делает моя программа, так это то, что она берет массив чисел, которые были прочитаны из файла, и сортирует их методами сортировки выбором и пузырьковой сортировкой. При сортировке методом пузырьковой сортировки в массиве два раза подряд отображается одно число. Это также всегда второе число, которое копируется. Я проверил, действительно ли по какой-либо причине число дважды передается в новый массив, но это не так. Я также пробовал другой входной файл, то же самое происходит в том же месте. Это также обрезает последний номер в списке. Я не вижу ничего очевидного в моем коде, из-за которого это происходит.

Список, который вызывает программа, выглядит следующим образом:

10

50

78

83

92

100

0

4

72

3

19

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int findMin(int arr[], int start, int size);
void printArr(int arr[], int size);
void selectionSort(int arr[], int size);
void bubbleSort(int arr[], int size);

int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        printf("Syntax Error: ./<exec> <infile>\n");
        exit(1);
    }

    FILE *ifp = NULL;
    ifp = fopen(argv[1], "r");

    if(ifp == NULL)
    {
        printf("Could not open %s for reading\n", argv[1]);
        exit(1);
    }

    int counter;
    int j = 0;

    fscanf(ifp, "%d", &counter);

    int array[counter];
    int arrB[counter];
    for(j = 0; j < counter; ++j)
    {
        fscanf(ifp, "%d", &array[j]);
    }

    for(j = 0; j < counter; j++)
    {
        arrB[j] = array[j];
    }
    int size = sizeof(array) / sizeof(int);

    printf("Before: ");
    printArr(array, size);

    selectionSort(array, size);
    bubbleSort(arrB, size);

    fclose(ifp);

    return 0;
}
int findMin(int arr[], int start, int size)
{
    int i = 0;
    int minLoc = start;
    int minVal = arr[minLoc];

    for ( i = start + 1; i < size; ++i)
    {
        if (arr[i] < minVal)
        {
            minVal = arr[i];
            minLoc = i;
        }
    }

    return minLoc;
}

void printArr(int arr[], int size)
{
    int i = 0;

    for(i = 0; i < size; ++i)
        printf("%3d ", arr[i]);
    printf("\n");
}
void selectionSort(int arr[], int size)
{
    int i = 0;
    int minLoc = 0;
    int tmp = 0;
    for(i = 0; i < size; ++i)
    {
        minLoc = findMin(arr, i, size);
        tmp = arr[i];
        arr[i] = arr[minLoc];
        arr[minLoc] = tmp;
    }

    printf("** Selection Sort **\n After: ");
    printArr(arr, size);

}
void bubbleSort(int arr[], int size)
{
    int i = 0;
    int j = 0;
    int tmp = 0;

    for(j = 0; j < size; j++)
    {
        for(i = 0; i < size; ++i)
        {
            if(arr[i] > arr[i+1])
            {
                tmp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = tmp;
            }
        }
    }
    printf("** Bubble Sort **\n After: ");
    printArr(arr, size);

}

person mychem97    schedule 16.04.2017    source источник
comment
for(i = 0; i < size; ++i) { if(arr[i] > arr[i+1]) вызывает подозрения, так как осуществляется доступ к arr[size] - границы массива пройдены. Предложите попробовать for(i = 1; i < size; ++i) { if(arr[i-1] > arr[i]) и настроить своп.   -  person chux - Reinstate Monica    schedule 16.04.2017
comment
Просто запустил ваш код. Выход вроде в порядке. Вот что я получил: До: 50 78 83 92 100 0 4 72 3 19 ** Сортировка выбором ** После: 0 3 4 19 50 72 78 83 92 100 ** Сортировка пузырьком ** После: 0 3 4 19 50 72 78 83 92 100   -  person Nguai al    schedule 16.04.2017
comment
@chux Это исправлено! Спасибо!   -  person mychem97    schedule 16.04.2017


Ответы (1)


bubbleSort() обращается за пределами массива. Таким образом, неопределенное поведение (UB).

for(j = 0; j < size; j++) {
    for(i = 0; i < size; ++i) {
        if(arr[i] > arr[i+1]) {   // Here code access outside bounds when i = size - 1
            ... Code swaps arr[i], arr[i+1];
        }
    }
}

Вместо

for(j = 0; j < size; j++) {
    for(i = 1; i < size; ++i) {
        if(arr[i-1] > arr[i]) {
            ... Code swaps arr[i-1], arr[i];
        }
    }
}
person chux - Reinstate Monica    schedule 16.04.2017
comment
@АлексЛоп. Я предпочитаю if(arr[i-1] > arr[i]), чтобы справиться с экстремальным случаем: при использовании size_t в качестве типа unsigned для индексации/размера лучший тип для индекса массива, такой как int, может быть слишком узким, ваш size-1 является проблемой, когда size == 0 как то есть SIZE_MAX. Конечно, это крайнее внимание. - person chux - Reinstate Monica; 16.04.2017