怎么能做插入排序，而是把GPA从最高到最低打印出来呢？

Question

我被要求写一个代码，进行插入排序，将 GPA 从高到低排序。这是我的代码，它正在为我打印相同的输入列表 :( 没有发生任何变化！因此，gpa 最低的学生应该排序到数组的末尾。输出只是对没有 ID 的 GPA 进行排序. 重点是我需要按 GPA 对学生进行排序，并确保旁边有他们的 ID。

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

typedef struct
{
   int ID;
   float GPA;
}STUDENT;

// method that sorts the array in descending order of GPA
void InsertionSortModified(STUDENT *StuAry,int N)
{
    int walk;
    float temp;
    bool located;

    for(int current =1; current <= N; current++){
        located=false;
        temp = StuAry[current].GPA;

        for(walk = current-1; walk>=0 && !located;)
        {
           if( temp > StuAry[walk].GPA)
           {
              StuAry[walk+1].GPA = StuAry[walk].GPA;
              walk --;
           }
            else
                located=true;
            StuAry[walk+1].GPA=temp;
        }
    }
}


void printArray(STUDENT *StuAry,int N)
{
   for(int i=0;i<N;i++)
       printf("%d %.2f\n",StuAry[i].ID,StuAry[i].GPA);
   printf("\n");
}

// testing main method
int main()
{
   STUDENT StuAry[]={{1,65.2},{2,75.3},{3,34.5},{4,99.9}};
   int N=4;
   printf("Before Sorting: \n");
   printArray(StuAry,N);
   InsertionSortModified(StuAry,N);
   printf("After Sorting: \n");
   printArray(StuAry,N);

   return 0;

}

//Now the problem is the output:
//Before sorting:
//1 56.20
//2 75.30
//3 34.50 
//4 99.90

//After sorting: //Notice her the integer(ID) it's not changing

//1 99.90
//2 75.30
//3 65.20
//4 34.50

Answer 1

步行>=0

你的温度应该是一个浮点数

Answer 2

添加此答案以保持简单易懂 我没有从第 0 个索引开始，而是从 N-1 索引开始，并与右侧的大多数元素进行比较，简而言之，与通用插入排序正好相反。

#include <stdio.h>

typedef struct
{
   int ID;
   float GPA;

}STUDENT;

void InsertionSortModified(STUDENT *StuAry,int N) 
{ 
    int i, key, j; 
    STUDENT pnt;
    for (i = N-2; i >= 0; i--) {
        pnt = StuAry[i];
        key = StuAry[i].GPA; 
        j = i + 1; 

        while (j < N && StuAry[j].GPA > key) { 
            StuAry[j - 1] = StuAry[j]; 
            j = j + 1; 
        } 
        StuAry[j - 1] = pnt; 
    } 
} 

void printArray(STUDENT *StuAry,int N)
{
   for(int i=0;i<N;i++)
       printf("%d %.2f\n",StuAry[i].ID,StuAry[i].GPA);
   printf("\n");
}

// testing main method
int main()
{
   STUDENT StuAry[]={{1,65.2},{2,75.3},{3,34.5},{4,99.9}, {5, 12.21}, {6, 98}};
   int N=6;
   printf("Before Sorting: \n");
   printArray(StuAry,N);
   InsertionSortModified(StuAry,N);
   printf("After Sorting: \n");
   printArray(StuAry,N);

   return 0;

}

Answer 3

据我了解，对于初学者，您需要按数据成员 GPA 对 STUDENT 类型的对象进行排序。这意味着在排序过程中，如果需要，您需要交换整个对象，而不是交换数据成员 FPA.

的值

所以这些陈述

temp = StuAry[current].GPA;
//...
StuAry[walk+1].GPA = StuAry[walk].GPA;
//...
StuAry[walk+1].GPA=temp;

没有意义。

在此for循环中

    for(walk = current-1; walk>=0 && !located;)
    {
       if( temp > StuAry[walk].GPA)
       {
          StuAry[walk+1].GPA = StuAry[walk].GPA;
          walk --;
       }
        else
            located=true;
        StuAry[walk+1].GPA=temp;
    }

声明

        StuAry[walk+1].GPA=temp;

在循环的每次迭代中执行，因为它不是else语句的子语句

        else
            located=true;

        StuAry[walk+1].GPA=temp;

函数如下面的演示程序所示。

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

typedef struct
{
   int ID;
   float GPA;
}STUDENT;

void insertion_sort( STUDENT a[], size_t n )
{
    for ( size_t i = 1; i < n; i++ )
    {
        STUDENT current = a[i];

        size_t j = i;
        while ( j != 0 && a[j-1].GPA < current.GPA )
        {
            a[j] = a[j-1];
            --j;
        }

        if ( j != i ) a[j] = current;
    }
}

int main(void) 
{
    enum { N = 10 };
    STUDENT a[N];

    srand( ( unsigned int )time( NULL ) );

    for ( size_t i = 0; i < N; i++ )
    {
        a[i].ID  = ( int )i;
        a[i].GPA = ( rand() % N ) / ( float )N;
    }

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

    insertion_sort( a, N );

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

    return 0;
}

程序输出可能看起来像

(0, 0.4) (1, 0.4) (2, 0.1) (3, 0.7) (4, 0.3) (5, 0.7) (6, 0.9) (7, 0.1) (8, 0.2) (9, 0.0) 
(6, 0.9) (3, 0.7) (5, 0.7) (0, 0.4) (1, 0.4) (4, 0.3) (8, 0.2) (2, 0.1) (7, 0.1) (9, 0.0)

如果你希望如果两个对象具有相同的 GPA 将按 ID 的升序排序，那么 while 语句中的条件可以如下所示。

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

typedef struct
{
   int ID;
   float GPA;
}STUDENT;

void insertion_sort( STUDENT a[], size_t n )
{
    for ( size_t i = 1; i < n; i++ )
    {
        STUDENT current = a[i];

        size_t j = i;
        while ( j != 0 && 
                ( a[j-1].GPA < current.GPA || 
                  ( !( current.GPA < a[j-1].GPA ) && current.ID < a[j-1].ID  ) ) )
        {
            a[j] = a[j-1];
            --j;
        }

        if ( j != i ) a[j] = current;
    }
}

int main(void) 
{
    enum { N = 10 };
    STUDENT a[N];

    srand( ( unsigned int )time( NULL ) );

    for ( size_t i = 0; i < N; i++ )
    {
        a[i].ID  = ( int )i;
        a[i].GPA = ( rand() % N ) / ( float )N;
    }

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

    insertion_sort( a, N );

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

    return 0;
}

程序输出可能看起来像

(0, 0.0) (1, 0.7) (2, 0.8) (3, 0.8) (4, 0.4) (5, 0.6) (6, 0.0) (7, 0.3) (8, 0.7) (9, 0.2) 
(2, 0.8) (3, 0.8) (1, 0.7) (8, 0.7) (5, 0.6) (4, 0.4) (7, 0.3) (9, 0.2) (0, 0.0) (6, 0.0)

例如，前两个记录具有相同的 GPA

(2, 0.8) 和 (3, 0.8)

按 ID 升序排列。

您可以编写一个通用排序函数，它接受一个提供所需条件的函数。例如

void insertion_sort( STUDENT a[], size_t n, int cmp( const void *, const void * ) )
{
    for ( size_t i = 1; i < n; i++ )
    {
        STUDENT current = a[i];

        size_t j = i;
        while ( j != 0 && cmp( &a[j-1], &current ) > 0 )
        {
            a[j] = a[j-1];
            --j;
        }

        if ( j != i ) a[j] = current;
    }
}

所以您只需要提供一个比较函数来比较数组的两个元素。

这是一个演示程序

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

typedef struct
{
   int ID;
   float GPA;
}STUDENT;

int cmp_ascending( const void *a, const void *b )
{
    const STUDENT *left  = a;
    const STUDENT *right = b;

    return ( right->GPA < left->GPA ) - ( left->GPA < right->GPA );
}

int cmp_descending( const void *a, const void *b )
{
    const STUDENT *left  = a;
    const STUDENT *right = b;

    return ( left->GPA < right->GPA ) - ( right->GPA < left->GPA );
}

void insertion_sort( STUDENT a[], size_t n, int cmp( const void *, const void * ) )
{
    for ( size_t i = 1; i < n; i++ )
    {
        STUDENT current = a[i];

        size_t j = i;
        while ( j != 0 && cmp( &a[j-1], &current ) > 0 )
        {
            a[j] = a[j-1];
            --j;
        }

        if ( j != i ) a[j] = current;
    }
}

int main(void) 
{
    enum { N = 10 };
    STUDENT a[N];

    srand( ( unsigned int )time( NULL ) );

    for ( size_t i = 0; i < N; i++ )
    {
        a[i].ID  = ( int )i;
        a[i].GPA = ( rand() % N ) / ( float )N;
    }

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

    insertion_sort( a, N, cmp_ascending );

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

    insertion_sort( a, N, cmp_descending );

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

    return 0;
}

它的输出可能看起来像

(0, 0.5) (1, 0.9) (2, 0.6) (3, 0.3) (4, 0.2) (5, 0.6) (6, 0.1) (7, 0.3) (8, 0.0) (9, 0.3) 
(8, 0.0) (6, 0.1) (4, 0.2) (3, 0.3) (7, 0.3) (9, 0.3) (0, 0.5) (2, 0.6) (5, 0.6) (1, 0.9) 
(1, 0.9) (2, 0.6) (5, 0.6) (0, 0.5) (3, 0.3) (7, 0.3) (9, 0.3) (4, 0.2) (6, 0.1) (8, 0.0)

首先数组按升序排序，然后按降序排序。

怎么能做插入排序，而是把GPA从最高到最低打印出来呢？

How can do insertion sorting, but to print the highest to the lowest GPA?

c

sorting

struct

insertion-sort

function-definition