Selection sort using strings inside structs

Question

I'm stuck. I am trying to use a selection sort to alphabetically arrange structs by strcmp the strings with each other. The problem is that I do not know how to do a selection sort with strings that are inside structs using only pointers, no indexes.

My struct looks like:

struct customer
{
char  customer_name[MAX_NAME_LENGTH];  /* Last name of customer    */
float amount_owed;                     /* Amount customer owes     */
int   priority;                        /* Priority of customer     */
};

and my function call:

sort_customers(quantity, p_customer_records);

and the definition:

/**********************************************************************/
/*                     Sort the customer database                     */
/**********************************************************************/
void sort_customers(int quantity, struct customer *p_customer_start)
{
struct customer *p_customer,
                     *p_outer,
                     *p_inner,
                     temp_customer;

for(p_customer = p_customer_start;
    (p_customer-p_customer_start) < quantity; p_customer++)
{
    p_inner = p_customer;

    for(p_outer = p_inner + 1;
        (p_outer-p_inner) <= quantity; p_outer++)
        if(strcmp(p_inner->customer_name, p_outer->customer_name) < 0)
            p_inner = p_outer;

    temp_customer = *p_customer;
    *p_customer   = *p_inner;
    *p_inner      = temp_customer;

    p_inner++;
}
return;
}

I honestly have no clue how to do this. I haven't been able to find anything on the internet or in my books to help me with this. Right now, this function sorts the names backwards. I'm pretty sure its something easy. I'm just missing something. I think another set of eyes will help. Hopefully everything is descriptive to help anyone understand what is going on.

If it is working but sorting backwards, change the comparison from < 0 to > 0. Or reverse the order of the arguments to strcmp(). You should think carefully about the inner loop and its upper bound. You have elements 0..quantity-1 in the array, so I think you want a < quantity there too; and you can marginally optimize the outer loop by looping to < quantity-1. As it stands, you're in danger of accessing the array out of bounds. — Jonathan Leffler
– Jonathan Leffler, Commented Oct 25, 2013 at 23:15
@JonathanLeffler Ok, so I think it might be something else. I just tried everything that you commented and nothing changed. Any other suggestions? — Jesse Upchurch
– Jesse Upchurch, Commented Oct 25, 2013 at 23:22
@JonathanLeffler Ok, if you could do that for me, I would be really appreciative. Thanks for the help! If you need any more info, I can give it to you. — Jesse Upchurch
– Jesse Upchurch, Commented Oct 25, 2013 at 23:29
Is there a specific reason you need selection sort? Or do you just want your customer list sorted? — Travis Griggs
– Travis Griggs, Commented Oct 26, 2013 at 0:10

Jonathan Leffler · Accepted Answer · 2013-10-26 00:02:44Z

Your problem is the loop control on the inner loop:

for (p_outer = p_inner + 1;
     (p_outer-p_inner) < quantity; p_outer++)

You need to check against the start of the array:

for (p_outer = p_inner + 1;
     (p_outer-p_customer_start) < quantity; p_outer++)

It would probably be easier to work with two array indexes, using subscripting.

Working code (with bug in 'swap' printing fixed):

#include <stdio.h>
#include <string.h>

enum { MAX_NAME_LENGTH = 16 };
struct customer
{
    char  customer_name[MAX_NAME_LENGTH];  /* Last name of customer    */
    float amount_owed;                     /* Amount customer owes     */
    int   priority;                        /* Priority of customer     */
};

static void sort_customers(int quantity, struct customer *p_customer_start)
{
    struct customer *p_customer,
                    *p_outer,
                    *p_inner,
                    temp_customer;

    for (p_customer = p_customer_start;
            (p_customer-p_customer_start) < quantity; p_customer++)
    {
        p_inner = p_customer;
        printf("Inner: %s\n", p_inner->customer_name);

        for (p_outer = p_inner + 1;
                (p_outer-p_customer_start) < quantity; p_outer++)
        {
            printf("Compare: %s vs %s\n", p_inner->customer_name, p_outer->customer_name);
            if (strcmp(p_inner->customer_name, p_outer->customer_name) > 0)
                printf("Change!\n"),
                p_inner = p_outer;
        }
        printf("Swap B: %s vs %s\n", p_customer->customer_name, p_inner->customer_name);
        temp_customer = *p_customer;
        *p_customer   = *p_inner;
        *p_inner      = temp_customer;
        printf("Swap A: %s vs %s\n", p_customer->customer_name, p_inner->customer_name);
        //p_inner++;
    }
}

static void dump_customers(int n, struct customer *c)
{
    printf("Customers (%d):\n", n);
    for (int i = 0; i < n; i++)
        printf("%-10s %6.2f %4d\n", c[i].customer_name, c[i].amount_owed, c[i].priority);
}

int main(void)
{
    struct customer data[] =
    {
        { "Max", 23.45, 2 },
        { "Carla", 34.75, 1 },
        { "Zach", 39.21, 22 },
    };
    int quantity = 3;

    dump_customers(quantity, data);
    sort_customers(quantity, data);
    dump_customers(quantity, data);

    return 0;
}

Output from failing version:

Customers (3):
Max         23.45    2
Carla       34.75    1
Zach        39.21   22
Inner: Max
Compare: Max vs Carla
Change!
Compare: Carla vs Zach
Compare: Carla vs 
Change!
Compare:  vs @?Q?
Compare:  vs 
Swap B: Max vs 
Swap A:  vs Max
Inner: Carla
Compare: Carla vs Zach
Compare: Carla vs Max
Swap B: Carla vs Carla
Swap A: Carla vs Carla
Inner: Zach
Compare: Zach vs Max
Change!
Compare: Max vs @?Q?
Change!
Compare: @?Q? vs 
Change!
Compare:  vs 
Compare:  vs 
Swap B: Zach vs 
Swap A:  vs Zach
Customers (3):
             0.00    0
Carla       34.75    1
            -0.00 32767
Segmentation fault: 11

It was obvious when it kept on going that there was a problem with the boundary of the inner loop.

Output from working version:

Customers (3):
Max         23.45    2
Carla       34.75    1
Zach        39.21   22
Inner: Max
Compare: Max vs Carla
Change!
Compare: Carla vs Zach
Swap B: Max vs Carla
Swap A: Carla vs Max
Inner: Max
Compare: Max vs Zach
Swap B: Max vs Max
Swap A: Max vs Max
Inner: Zach
Swap B: Zach vs Zach
Swap A: Zach vs Zach
Customers (3):
Carla       34.75    1
Max         23.45    2
Zach        39.21   22

Note how I print useful information at every turn. The printf("Change!\n"), notation is not graceful — but it works for debugging purposes. The dump_customers() function is something you should more or less automatically write for yourself (and use often while debugging). It makes it a lot easier to see when things are going wrong. It isn't my best ever dump function; it should take a tag string as an argument, and possibly a FILE *fp to write to. For bigger arrays, it should print the row number in front of each line. Nevertheless, the basic idea of a function to print each of your data structures is very helpful.

Collectives™ on Stack Overflow

Selection sort using strings inside structs

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related