сортировка выбора не сортируется правильно

Question

Мой алгоритм сортировки выбора не работает правильно. Я застрял на этом довольно долго. Я решил это с помощью указателей, но по какой-то причине он сортируется неправильно.

void sortArray(int arr[], size_t n)  
{  
    int i;  
    int j;
    int min_idx;  
    int min;  

    for (i = 0; i < n - 2; i++)  
    {  
        min = arr[i];
        min_idx = i;  
        for (j = (i+1); j < n - 1; j++)  
        {
            if (arr[j] < arr[min])  
            {
                min = arr[j];
                min_idx = j;
            }
        }   
        //swap(arr[min_idx], arr[i]);
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;      
    } 
}

До

10 9 8 7 6 5 4 3 0 0

После

0 9 7 3 6 4 5 8 10 0

Но помощь будет принята с благодарностью.

Answer 1

Есть три небольшие ошибки.

Две ошибки по одной на ваших условиях l oop и одна ошибка имени переменной (min вместо min_idx).

Исправление этих трех ошибок дает нам ...

void sortArray(int arr[], size_t n)  
{  
    int i;  
    int j;
    int min_idx;   

    for (i = 0; i < n - 1; i++)  
    {  
        min_idx = i;  
        for (j = (i+1); j < n; j++)  
        {
        if (arr[j] < arr[min_idx])  
            {
            min_idx = j;
            }
        }   
        //swap(arr[min_idx], arr[i]);
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;      
    } 
}

Также удалена неиспользуемая переменная min.

Answer 2

В функции есть как минимум две ошибки.

Первый - это то, что последний элемент массива с индексом n-1 не участвует в сортировке массива из-за условий в loops

for (i = 0; i < n - 2; i++)  
{  
    min = arr[i];
    min_idx = i;  
    for (j = (i+1); j < n - 1; j++)  
    //..

Вторая ошибка заключается в том, что в этом операторе if

if (arr[j] < arr[min])  

в качестве индекса используется min вместо min_index в операнде arr[min].

Обратите внимание на то, что когда n равно 0 или 1, то при условии l oop

for (i = 0; i < n - 2; i++)  

выражение n - 2 даст большое значение без знака, которое приводит к неопределенному поведению функции.

И эти переменные

int i;  
int j;
int min_idx; 

должны иметь тип size_t вместо типа int.

Также объявляйте переменные в минимальной области, где они используются.

Функция может быть определена следующим образом.

void sortArray( int arr[], size_t n )  
{  
    for ( size_t i = 0; i < n; i++ )  
    {  
        size_t min_idx = i;  

        for ( size_t j = i + 1; j < n; j++ )  
        {
            if ( arr[j] < arr[min_idx] )  
            {
                min_idx = j;
            }
        }   

        if ( i != min_idx )
        {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }      
    } 
}

Вот демонстрационная программа.

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

void sortArray( int arr[], size_t n )  
{  
    for ( size_t i = 0; i < n; i++ )  
    {  
        size_t min_idx = i;  

        for ( size_t j = i + 1; j < n; j++ )  
        {
            if ( arr[j] < arr[min_idx] )  
            {
                min_idx = j;
            }
        }   

        if ( i != min_idx )
        {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }      
    } 
}

int main(void) 
{
    srand( ( unsigned int )time( NULL ) );

    while ( 1 )
    {
        printf( "Enter the size of an integer array: " );

        size_t n = 0;

        if ( scanf( "%zu", &n ) != 1 || n == 0 ) break;

        putchar( '\n' );

        int a[n];

        for ( size_t i = 0; i < n; i++ )
        {
            a[i] = rand() % n;
        }

        printf( "Source array: " );

        for ( size_t i = 0; i < n; i++ )
        {
            printf( "%d ", a[i] );
        }
        putchar( '\n' );

        sortArray( a, n );

        printf( "Sorted array: " );

        for ( size_t i = 0; i < n; i++ )
        {
            printf( "%d ", a[i] );
        }
        putchar( '\n' );

        putchar( '\n' );
    }

    return 0;
}

Его вывод может выглядеть как

Enter the size of an integer array: 10

Source array: 4 1 1 3 1 8 7 4 0 9 
Sorted array: 0 1 1 1 3 4 4 7 8 9 

Enter the size of an integer array: 0

Answer 3

Ваш внутренний if использует неправильный индекс. Это должно быть

if (arr[j] < arr[min_idx])

или, поскольку arr[min_idx] уже сохранено в min

if (arr[j] < min)

Вы также на один индекс меньше в вашей сортировке. Вы никогда не смотрите на arr[n - 1].