Sorting an array of structs by string

Question

I'm trying to sort an array of structs using selection sort and pointers, but I'm having some trouble.

When I try to print the array out to see if the names are sorted, all the names are sorted except for the one in the first position which remains where it is (unsorted).

/*
   all is the unordered array of struct; pLast is pointer to the last struct in array.
*/
void sortArray(CASE* all, CASE* pLast)
{
  CASE* current;
  CASE* walker;
  CASE* smallest;
  CASE temp;


  for(current = all; current < pLast; current++)
  {
    smallest = current;

    for (walker = current + 1; walker <= pLast; walker++)
    {
      if(strcmp(walker->name, smallest->name) < 0 )
        smallest = walker;
    }
    temp = *current;
    *current = *smallest;
    *smallest = temp;
  }

  for(walker = all; walker <= pLast; walker++)
  {
    printf("%s\n", walker->name);
  }  

  return;
}

Any tips?

Thanks

Edit: major revision that allows the names to be printed, but not fully sorted

My first thought is that you need to initialize smallest before you use it. The first time your loop runs, it will have some random pointer value which you are dereferencing with smallest->name. As soon as you do that, who knows what'll happen? — Isaac Sutherland
– Isaac Sutherland, Commented Apr 24, 2012 at 5:29
I initialized it to all so that the first run would make the strcmp return 0; however, the same problem still occurs. — Huy
– Huy, Commented Apr 24, 2012 at 5:30
Secondly, the selection sort algorithm has a loop within a loop -- you have the inner loop which is responsible for finding the smallest item, but no outer loop. — Isaac Sutherland
– Isaac Sutherland, Commented Apr 24, 2012 at 5:31
look carefully: the swap should not be inside the inner loop. In other words, first you find the smallest element, and then you make a swap. — Isaac Sutherland
– Isaac Sutherland, Commented Apr 24, 2012 at 6:03
You are probably getting segmentation faults because you are trying to swap smallest with walker. However, after the inner loop has finished, walker is a pointer to the next CASE after the end of the array -- i.e. walker == pLast + 1 is true -- and that's a bad pointer to memory you probably don't own. Hence the segmentation fault. (FYI en.wikipedia.org/wiki/Segmentation_fault) — Isaac Sutherland
– Isaac Sutherland, Commented Apr 24, 2012 at 6:19

Isaac Sutherland · Accepted Answer · 2012-04-24 06:26:56Z

2

Being a simple algorithm, selection sorts always look something like this:

function selection_sort(arr):
  for i in 0..len(arr)-1:
    smallest = i
    for j in i+1..len(arr)-1:
      if arr[j] < arr[smallest]:
        smallest = j
    swap i and smallest.

An implementation will still use this format (or very close) if using pointers.

FYI: http://en.wikipedia.org/wiki/Selection_sort

edited Apr 24, 2012 at 6:26

answered Apr 24, 2012 at 5:50

Isaac Sutherland

3,1784 gold badges31 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jonathan Leffler · Accepted Answer · 2012-04-24 06:14:37Z

0

Is there any reason not to use qsort?

Unfortunately you to not write what struct CASE* is; we just know it contains a field name

So you can write a comparison function like:

int case_struct_comparison_function (const void * v1, const void * v2) {
  const struct CASE * case_1 = v1;
  const struct CASE * case_2 = v2;
  return  strcmp(case_1->name, case_2->name);
}

qsort(arr, size_of_arr, sizeof(struct CASE), case_struct_comparison_function);

It's untested but should give you an idea.

edited Apr 24, 2012 at 6:14

Jonathan Leffler

759k145 gold badges961 silver badges1.3k bronze badges

answered Apr 24, 2012 at 5:40

Friedrich

6,0081 gold badge30 silver badges46 bronze badges

4 Comments

Huy Over a year ago

I'm trying to learn how to code right now using pointers/structs so I want to stick to the problem.

Friedrich Over a year ago

As you can see I'm using all kind of pointers in this cuntion. I use the pointer to a CASE struct, dereference a ponter in strcmp and am using a function pointer as parameter ;-) Anywa I do get what you want to do. But I asked is there any reaon not to use qsort...

unwind Over a year ago

@Friedrich To an experienced C programmer, those usages don't really stand out as being something to notice, "dereferencing a pointer in strcmp()" really is nothing special. I'm not saying this to "keep you down", but just trying to point out that while to you, your code is obviously needlessly convoluted because you want to practice, to someone else it might be needlessly convoluted and should be changed to something simpler. :)

Friedrich Over a year ago

It is not convulted, it used the means C gives us. And not it's hardly simple to get a good search function implemented. It took even years to get quicksort right and even binary search was "once" problematic. So no I disagree with your comment.

Collectives™ on Stack Overflow

Sorting an array of structs by string

2 Answers 2

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related