Блог

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

 #include <stdio.h>

int* selectionSort(int a_count, int *a);

int main(void)
{
    int a[] =     {4,2,3,4,4,9,98,98,3,3,3,4,2,98,1,98,98,1,1,4,98,2,98,3,9,9,3,1,4,1,98,9,9,2,9,4,2,2,9,98,4,98,1,3,4,9,1,98,98,4,2,3,98,98,1,99,9,98,98,3,98,98,4,98,2,98,4,2,1,1,9,2,4};
    int i, a_count = 73;
    int *result = selectionSort(a_count, a);
        for(i = 0; i < a_count; i  ){
            printf("%i ", result[i]);
        }
    return 0;
}   

int* selectionSort(int a_count, int* a) {
    int i, j, min = 0, tmp;
    for(i = 0; i < a_count - 1; i  ){
        min = i;
        printf("min_i = %in", min);
        for(j = i   1; j < a_count; j  ){
            printf("j = %i ", j);
                if(a[j] < a[min]){
                printf("%i < %in", a[j], a[min]);
                printf("min is changed: ");
                min = j;
                printf("min_j = %in", min);
            }
            tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
   }
   return a;
}
  

Большое спасибо за вашу помощь!

Вы меняете местами элемент i с элементом min на каждой итерации вашего цикла j . Это неверно и неэффективно. Выполните замену после завершения внутреннего цикла, так что min фактически содержит индекс минимального значения текущего подмассива, а не пока вы все еще пытаетесь выяснить, где находится этот элемент.

Возникает простая ошибка, которая заключается в том, что вы не дожидаетесь окончания внутреннего цикла, чтобы выполнить подкачку.

 int* selectionSort(int a_count, int* a) {
    int i, j, min = 0, tmp;
    for(i = 0; i < a_count - 1; i  ){
        min = i;
        printf("min_i = %in", min);
        for(j = i   1; j < a_count; j  ){
            printf("j = %i ", j);
                if(a[j] < a[min]){
                printf("%i < %in", a[j], a[min]);
                printf("min is changed: ");
                min = j;
                printf("min_j = %in", min);
            }
        }
        tmp = a[i];         //  three lines moved out of the loop
        a[i] = a[min];      //
        a[min] = tmp;       //
   }
   return a;
}
  

Теперь вывод правильный.

У вас есть два цикла, во внешнем цикле вы сначала устанавливаете min, затем во внутреннем цикле меняете min, что приводит к искажению значения min и делает ваш код подкачки неправильным. Вы можете удалить весь код около min, использовать i, j напрямую, тогда должно сработать. измените if (a[j] < a [min]) на if (a[j] < a [i])

 public static class SelectionSort
{
    static int min;
    public static void Sort(int[] data)
    {
        for (int i = 0; i < data.Length; i  )
        {
            for (int j = 0; j < data.Length; j  )
            {
                min = j;
                if (data[i] < data[j])
                    Swap(x: ref data[i], y: ref data[min]);
            }
        }
    }

    private static void Swap(ref int x, ref int y)
    {
        int temp = x;
        x = y;
        y = temp;
    }
}