为什么我的插入排序只能对90％的数据进行排序？

Question

我必须读取一个CSV文件，然后按升序排序其数据基础。情节扭曲是将90％的数据正确排序，但其他10％不是。 CSV文件中的日期以此表格为01/17/2015（/天/年）编写。我对代码进行了一些测试，并注意到，如果我运行两次插入排序，那么未分类的10％的数据是完美分类的。我的问题是为什么会发生这种情况，这是我的代码或该算法的问题。它在大多数情况下都正确运行，如果我运行它的启示，则将文件完美地分类，这使我认为唯一的问题是算法而不是我的代码。

#include <stdio.h>

typedef struct
{
    int month;
    int day;
    int year;
    float T_degC;
    float PO4uM;
    float SiO3uM;
    float NO2uM;
    float NO3uM;
    float Salnty;
    float O2ml_L;
} hello;

int insertionSort(hello hellos[], int records);

int main()
{
    FILE* file;

    file = fopen("ocean1.csv", "r");

    if (file == NULL)
    {
        printf("Error opening file. \n");
        return 1;
    }

    hello hellos[1405];

    int read = 0;
    int records = 0; // dhladh struct

    do
    {
        read = fscanf(file,
                      "%d/%d/%d, %f, %f, %f, %f, %f, %f, %f",
                      &hellos[records].month,
                      &hellos[records].day,
                      &hellos[records].year,
                      &hellos[records].T_degC,
                      &hellos[records].PO4uM,
                      &hellos[records].SiO3uM,
                      &hellos[records].NO2uM,
                      &hellos[records].NO3uM,
                      &hellos[records].Salnty,
                      &hellos[records].O2ml_L);

        if (read == 10)
        {
            records++;
        }
        if (read != 10 && feof(file) == 0)
        {
            printf("File format incorrect.\n");
            return 1;
        }
        if (ferror(file))
        {

            printf("Error reading file.\n");
            return 1;
        }

    } while (!feof(file));

    fclose(file);

    printf("\n%d records read.\n\n", records);

    insertionSort(hellos, records);
    // insertionSort(hellos, records);

    //Εκτυπωση των αποτελεσματων.

    for (int i = 0; i < records; i++)
    {
        printf("\n%d, %d, %d, %f, %f, %f, %f, %f, %f, %f",
               hellos[i].month,
               hellos[i].day,
               hellos[i].year,
               hellos[i].T_degC,
               hellos[i].PO4uM,
               hellos[i].SiO3uM,
               hellos[i].NO2uM,
               hellos[i].NO3uM,
               hellos[i].Salnty,
               hellos[i].O2ml_L);

        printf("\n");
    }
    return 0;
}

int insertionSort(hello hellos[], int records)
{
    int i;
    hello key;

    for (int j = 1; j < records; j++)
    {
        key = hellos[j];
        i = j - 1;

        printf("\n\n%d", i);
        // printf("\n%d", key.month);
        // printf("\n%d", hellos[i].month);

        if (key.year < hellos[i].year)
        {
            // printf("\nmpla");
            while (i >= 0 && key.year < hellos[i].year)
            {
                hellos[i + 1] = hellos[i];
                i = i - 1;
            }
            hellos[i + 1] = key;
        }
        else if (key.year == hellos[i].year)
        {
            // printf("\nmpla2");
            if (key.month < hellos[i].month)
            {
                // printf("\nmpla3");
                while (i >= 0 && key.month < hellos[i].month && key.year == hellos[i].year)
                {
                    hellos[i + 1] = hellos[i];
                    i = i - 1;
                }
                hellos[i + 1] = key;
            }
            else if (key.month == hellos[i].month)
            {
                // printf("\nmpla4");
                if (key.day < hellos[i].day)
                {
                    // printf("\nmpla5");
                    while (i >= 0 && key.day < hellos[i].day && key.month == hellos[i].month)
                    {
                        hellos[i + 1] = hellos[i];
                        i = i - 1;
                    }
                    hellos[i + 1] = key;
                }
                else if (key.day == hellos[i].day)
                {
                    // printf("\nmpla6");
                    if (key.T_degC < hellos[i].T_degC)
                    {
                        // printf("\nmpla7");
                        while (i >= 0 && key.day == hellos[i].day && key.month == hellos[i].month &&
                               key.year == hellos[i].year)
                        {
                            hellos[i + 1] = hellos[i];
                            i = i - 1;
                        }
                        hellos[i + 1] = key;
                    }
                }
            }
        }
    }
    return 0;
}

以下是我的CSV数据的一些示例：

02/02/2015,20.37,0.22,0,0,0,33.685,5.5
02/01/2015,17.71,0.28,0.5,0,0,33.676,5.93
01/30/2015,10.85,1.32,16.5,0.05,14.8,33.752,4.19
01/31/2015,10.54,1.85,27.4,0.02,21.5,33.881,2.75
01/29/2015,10.49,1.98,30,0.02,22.6,33.946,2.41
01/28/2015,10.39,2.03,30.7,0.02,23,33.96,2.37
01/27/2015,10.22,2.1,31.8,0.02,23.6,33.982,2.31
01/26/2015,9.75,2.19,34.7,0.01,24.8,34.029,2.39
01/25/2015,18.43,0.11,1,0,0,33.464,5.83
01/24/2015,18.25,0.04,2,0,0,33.452,5.95
01/22/2015,15.6,0.19,3.8,0.04,0.7,33.423,5.91
01/23/2015,12.7,0.41,6,0.1,1.4,33.393,5.88
01/21/2015,10.98,1.09,16.6,0.07,14.1,33.481,4.04
01/20/2015,10.93,1.55,23.8,0.04,19.1,33.531,2.82
01/19/2015,10.74,1.67,26.7,0.04,20.7,33.583,2.55
01/16/2015,10.27,1.66,27.8,0.01,21.2,33.636,2.71
01/15/2015,10.02,1.76,34.4,0.03,24.3,33.747,2.11
01/17/2015,20.22,0.15,1,0,0,33.654,5.34
01/18/2015,20.22,0.15,1,0,0,33.654,5.34

Answer 1

首先，我建议您有点思考，并找出一种编写本文的方法，而无需多次重复该排序算法。 提示：您只需要一个函数即可比较两个hellos，并确定第一个功能是小于第二个功能，等于它，还是大于它。

在当前的问题上：您在// printf（“ \ nmpla5”）下有逻辑错误显然，错误地对列表进行分类。 编辑：实际上，仅修复了您的预期代码中的错误，然后一天，然后温度）。尝试再次编写所有内容，这段时间设计了您的实现，请牢记比较功能（比较两个条目）。

Answer 2

对于初学者，它不是C ++代码。这是一个C代码。

逻辑错误隐藏在if-else语句中。

例如，请考虑例如此代码段

        if (key.month < hellos[i].month)
        {
            // printf("\nmpla3");
            while (i >= 0 && key.month < hellos[i].month && key.year == hellos[i].year)
            {
                hellos[i + 1] = hellos[i];
                i = i - 1;
            }
            hellos[i + 1] = key;
        }
        else if (key.month == hellos[i].month)
        {
            //...
        }

，如果key.month小于hellos [i] .month，那么否则语句

else if (key.month == hellos[i].month)

将无法获得控件，尽管可以有对象（之后前面的if语句）带有key.month等于hellos [i] .month，但key.day小于Hellos [i] .day。

我建议编写一个单独的比较函数，类似于QSort使用的功能，并称其为比较结构类型的两个对象。例如，

int cmp( const void *a, const void *b )
{
    const hello *left  = a;
    const hello *right = b;

    int result = ( right->year < left->year ) - ( left->year < right->year );

    if ( result == 0 )
    {
        result = ( right->month < left->month ) - ( left->month < right->month );
        if ( result == 0 )
        {
            result = ( right->day < left->day ) - ( left->day < right->day );
        }
    }

    return result;
}        

这里是一个演示程序，该程序基于调用QSort使用此功能。

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

typedef struct
{
    int month;
    int day;
    int year;
} hello;

int cmp( const void *a, const void *b )
{
    const hello *left  = a;
    const hello *right = b;

    int result = ( right->year < left->year ) - ( left->year < right->year );

    if ( result == 0 )
    {
        result = ( right->month < left->month ) - ( left->month < right->month );
        if ( result == 0 )
        {
            result = ( right->day < left->day ) - ( left->day < right->day );
        }
    }

    return result;
}

int main( void )
{
    hello hellos[] =
    {
        { 02, 02, 2015 },
        { 02, 01, 2015 },
        { 01, 30, 2015 },
        { 01, 31, 2015 },
        { 01, 29, 2015 },
        { 01, 28, 2015 },
    };
    size_t N = sizeof( hellos ) / sizeof( *hellos );

    qsort( hellos, N, sizeof( hello ), cmp );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%02d/%02d/%d\n", hellos[i].month, hellos[i].day, hellos[i].year );
    }
}

程序输出为

01/28/2015
01/29/2015
01/30/2015
01/31/2015
02/01/2015
02/02/2015

您可以在您的功能中仅在一个if语句中插入比较函数的调用和以下循环时，例如

if ( cmp( &key, &hellos[i] ) < 0 )
{
    //...
}

将您的评论考虑到我的答案，似乎您无法了解应该做什么。因此，我将包括一个演示程序。

#include <stdio.h>

typedef struct
{
    int month;
    int day;
    int year;
} hello;

int cmp( const void *a, const void *b )
{
    const hello *left  = a;
    const hello *right = b;

    int result = ( right->year < left->year ) - ( left->year < right->year );

    if ( result == 0 )
    {
        result = ( right->month < left->month ) - ( left->month < right->month );
        if ( result == 0 )
        {
            result = ( right->day < left->day ) - ( left->day < right->day );
        }
    }

    return result;
}

void insertionSort( hello hellos[], size_t records )
{
    for ( size_t i = 1; i < records; i++ )
    {
        if ( cmp( &hellos[i], &hellos[i-1] ) < 0 )
        {
            hello tmp = hellos[i];
            size_t j = i;

            while ( j != 0 && cmp( &tmp, &hellos[j -1] ) < 0 )  
            {   --j;
                hellos[j + 1] = hellos[j];               
            } 

            hellos[j] = tmp;
        }
    }
}

int main( void )
{
    hello hellos[] =
    {
        { 02, 02, 2015 },
        { 02, 01, 2015 },
        { 01, 30, 2015 },
        { 01, 31, 2015 },
        { 01, 29, 2015 },
        { 01, 28, 2015 },
    };
    size_t N = sizeof( hellos ) / sizeof( *hellos );

    insertionSort( hellos, N );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%02d/%02d/%d\n", hellos[i].month, hellos[i].day, hellos[i].year );
    }
}

程序输出与上面显示的相同

01/28/2015
01/29/2015
01/30/2015
01/31/2015
02/01/2015
02/02/2015

或在C ++中相同，使用标准C ++函数std :: TIE在标题＆lt; tuple＆gt;中声明。

类似

if ( std::tie( key.year, key.month, key.day ) < 
     std::tie( hellos[i].year, hellos[i].month, hellos[i].day ) ) 
{
    //...
} 

Answer 3

所以我终于想到了一个主意。因此，我的想法是，而不是在if语句中使用if语句，而是认为这可能是为语句做多次的更好的解决方案。一个是一年，一个是一个月，一个是一天，所以我可以根据一个月的一年首先基于一年的代码进行排序，最后也是一天的。这是代码：

#include <stdio.h>

typedef struct 
{
int month;
int day;
int year;
float T_degC;
float PO4uM;
float SiO3uM;
float NO2uM;
float NO3uM;
float Salnty;
float O2ml_L;
}
hello;

int insertionSort(hello hellos[], int records);

int main()
{
FILE *file;

file = fopen("ocean.csv", "r");

if(file == NULL)
{
    printf("Error opening file. \n");
    return 1;
}

hello hellos[1405];

int read = 0;
int records = 0;   //dhladh struct

do
{
    read = fscanf(file,
                        "%d/%d/%d, %f, %f, %f, %f, %f, %f, %f",
                        &hellos[records].month,
                        &hellos[records].day,
                        &hellos[records].year,
                        &hellos[records].T_degC,
                        &hellos[records].PO4uM,
                        &hellos[records].SiO3uM,
                        &hellos[records].NO2uM,
                        &hellos[records].NO3uM,
                        &hellos[records].Salnty,
                        &hellos[records].O2ml_L);

    if(read == 10)
    {
        records++;  

    }
    if(read != 10 && feof(file) ==0)
    {
        printf("File format incorrect.\n");
        return 1;
    }
    if(ferror(file))
    {

        printf("Error reading file.\n");
        return 1;
    }

} while (!feof(file));

fclose(file);


printf("\n%d records read.\n\n", records);

insertionSort(hellos, records);
//insertionSort(hellos, records);

//Εκτυπωση των αποτελεσματων.

for(int i=0; i<records; i++)
{
    printf("\n%d, %d, %d, %f, %f, %f, %f, %f, %f, %f",
                        hellos[i].month,
                        hellos[i].day,
                        hellos[i].year,
                        hellos[i].T_degC,
                        hellos[i].PO4uM,
                        hellos[i].SiO3uM,
                        hellos[i].NO2uM,
                        hellos[i].NO3uM,
                        hellos[i].Salnty,
                        hellos[i].O2ml_L);

    printf("\n");
}
return 0;
    }

    int insertionSort(hello hellos[], int records)
    {
int i;
hello key;

for(int j=1; j<records; j++)
{
    key = hellos[j];
    i = j-1;
    if(key.year < hellos[i].year)
    {
        while(i >= 0 && (key.year < hellos[i].year))
        {
            hellos[i+1] = hellos[i];
            i = i-1;  
        }
        hellos[i+1] = key;
    }
}

for(int k=1; k<records; k++)
{
    key = hellos[k];
    i = k-1;
    if((key.month < hellos[i].month) && (key.year == hellos[i].year))
    {
        while(i >= 0 && (key.month < hellos[i].month) && (key.year == hellos[i].year))
        {
            hellos[i+1] = hellos[i];
            i = i-1;  
        }
        hellos[i+1] = key;
    }
}

for(int l=1; l<records; l++)
{
    key = hellos[l];
    i = l-1;
    if((key.day < hellos[i].day) && (key.month == hellos[i].month) && (key.year == hellos[i].year))
    {
        while(i >= 0 && (key.day < hellos[i].day) && (key.month == hellos[i].month) && (key.year == hellos[i].year))
        {
            hellos[i+1] = hellos[i];
            i = i-1;  
        }
        hellos[i+1] = key;
    }
}
return 0;
   }