arrayscsortinginsertion-sort

C insertion sort not sorting from least to greatest


I have an insertion sort that was working when it sorted integers, however I had to change it to sort an array of structs for a different project. The array is 10 people's names and ages. The array is first passed to a sorting function and then a for loop is set to iterate through the array. I think the issue I am having is the array is not looping correctly because the print out of the new array is in a mixed up order still. Here is the code I have...

#include <stdio.h>

#define SWAP(x,y) do {typeof(x) SWAP = x; x=y; y=SWAP;} while (0)


typedef struct Person{
        int age;
        char name[10];

}Person;

//-----------------------------

void sort(Person* arr,int n){

    int i, x, y;
    for (i=1;i<n;i++){
        x=arr[i].age;
        y = i-1;

        while(y>=0 && arr[y].age > x){
                arr[y+1]=arr[y];
                y=y-1;
        }
        SWAP(arr[y+1],arr[i]);
    }
}

int main(){

    struct Person p1 = {26, "devin"};
    struct Person p2 = {28, "bob"};
    struct Person p3 = {22, "derric"};
    struct Person p4 = {20, "amy"};
    struct Person p5 = {19, "melvin"};
    struct Person p6 = {17, "ashley"};
    struct Person p7 = {31, "haley"};
    struct Person p8 = {32, "larry"};
    struct Person p9 = {24, "ben"};
    struct Person p10 = {40, "bobby"};


    struct Person arr[] = {p1,p2,p3,p4,p5,p6,p7,p8,p9,p10};

    int n = sizeof(arr)/sizeof(arr[0]);

    printf("--Array Before Sort--\n");
    print(arr, n);

    printf("--Array After Sort--\n");
    sort(arr,n);

    //printf("\n--Sorted Array--\n");
    print(arr,n);
}

The code is missing the print function because I believe that is working properly and I'm trying to condense what I need help with. I believe the issue is in the for and while loops in the sort function. Here is the output...

--Array Before Sort--
26 devin, 28 bob, 22 derric, 20 amy, 19 melvin, 17 ashley, 31 haley, 32 larry, 24 ben, 40 bobby, 
--Array After Sort--
32 larry, 28 bob, 28 bob, 28 bob, 28 bob, 26 devin, 28 bob, 31 haley, 32 larry, 40 bobby, 

The names are supposed to be sorted from youngest to oldest. Any ideas?


Solution

  • You just need to make a few small changes to sort function:

    void sort(Person* arr, int n)
    {
        int i, y;
        for (i = 1; i < n; i++){
            Person x = arr[i];
            y = i - 1;
    
            while (y >= 0 && arr[y].age > x.age){
                    arr[y + 1] = arr[y];
                    y = y - 1;
            }
            SWAP(arr[y + 1], x);
        }
    }
    

    I would also replace SWAP(arr[y+1], x); with just arr[y+1] = x; because it makes code more readable and it probably is better for overall performance.