Проблема с выбором сортировки и использованием метода findMin в C

Question

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

Вот метод сортировки Я использую с помощью метода findMin:

void sortMin2(int A[]) { 
    int outer; 
    int minIndex; 
    for(outer = 0; outer < 5; outer++) { 
     minIndex = findMin(A, outer, 5); 
     if(minIndex != outer) { 
       swap(&A[minIndex], &A[outer]); 
     }//end if 
    } // end for 
} 

int findMin(int A[], int i, int j) { 
    int k; // for loop 
    int index = 0; 
    for(k = (i + 1); k < (j+1); k++) { 
     if(A[k] < A[index]) { 
      index = k; 
     } // end if 
    } // end for 
    return index; 
} // end findMin 

void swap(int *i, int *j) { 
    int temp = *i; 
    *i = *j; 
    *j = temp; 
} // end swap 

А вот мой выходной, когда я запускаю его на массив из пяти значений:

Array Before: 4, 10, 9, 1, 3, 
4, 10, 9, 1, 3, 
1, 10, 9, 4, 3, 
10, 1, 9, 4, 3, 
10, 1, 3, 4, 9, 
10, 1, 3, 9, 4, 
Array after: 4, 1, 3, 9, 10, 

Теперь здесь это мой метод сортировки по выбору, который действительно работает (т. е. правильно сортирует его).

void selectionSort2(int A[]) { 
    int outer; // for loops 
    int inner; 
    int minimum = 0; 
    //int minIndex = 0; 
    for(outer = 0; outer < 5; outer++) { 
     //minIndex = findMin(A, 0, 19); 
     minimum = outer; 
     for(inner = outer + 1; inner < 5; inner++) { 
      if(A[minimum] > A[inner]) { 
       minimum = inner; 
      } // end if 
     } // end inner for 

     if(minimum != outer) { 
      swap(&A[minimum], &A[outer]); 
     } // end if 
    } // end outer for 
} 

Кто-нибудь видит, почему моя функция sortMin2 на самом деле не сортирует его?

Answer 1

Некоторые вещи, внутри кода, не в правильном смысле.

Почему в способе findMin(...), цикл for имеет k < (j+1) как завершающий состояние. Как вы думаете, это должно быть k < j? Поскольку j + 1 приведет к 6, отсюда цикл будет идти до j = 5, что приведет к неопределенному поведению (так как это больше, чем границы массива A). Индексы массивов начинаются с 0. Поскольку размер 5, следовательно, индексы находятся в диапазоне 0 - 4.

Кроме того, значение index не меняется. Он всегда начинается с 0 на каждой итерации. Вместо этого он должен быть int index = i, внутри функции findMin(...), как и в Selection Sort, мы находим самый маленький элемент и положим его слева, на его законное положение, поэтому в следующий раз мы начинаем с места, впереди этого места.

И внутри функции sortMin2(...) вы не смогли позвонить swap(...), если у вас есть новый индекс для обмена значениями.

Вот модифицированная версия, из сниппета:

int findMin(int A[], int i, int j) { 
    int k; // for loop 
    int index = i; 
    for(k = (i + 1); k < (j); k++) { 
     if(A[k] < A[index]) { 
      index = k; 
     } // end if 
    } // end for 
    return index; 
} // end findMin 

void swap(int *i, int *j) { 
    int temp = *i; 
    *i = *j; 
    *j = temp; 
} // e 

void display(int A[]) 
{ 
    int i = 0; 
    for (i = 0; i < 5; ++i) 
     printf("%d\t", A[i]); 
    printf("\n"); 
} 

void sortMin2(int A[]) { 
    int outer = 0; 
    int minIndex = -1; 
    for(outer = 0; outer < 5; outer++) { 
     minIndex = findMin(A, outer, 5); 
     if(minIndex != outer) { 
      swap(&A[minIndex], &A[outer]); 
      display(A); 
     }//end if 
    } // end for 
}