By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,506 Members | 1,228 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,506 IT Pros & Developers. It's quick & easy.

Sorting struct array

P: 5
I'm trying to sort an array of structs. My code looks something like this:

Expand|Select|Wrap|Line Numbers
  1. struct Foo
  2. {
  3.     int number;
  4. };
  5.  
  6. int main()
  7. {
  8.     int i = 14;
  9.     Foo *floo = new Foo[i];
  10. }
  11.  
Are there any functions for this kind of sorting in the standard library? I've found a code for bubble sort, but I'm not sure how to pass a struct array to it.

Expand|Select|Wrap|Line Numbers
  1. void bubble_sort(apvector <int> &array)
  2. {
  3.       int i, j, flag = 1;
  4.       int temp;
  5.       int arrayLength = array.length( ); 
  6.       for(i = 1; (i <= arrayLength) && flag; i++)
  7.      {
  8.           flag = 0;
  9.           for (j=0; j < (arrayLength -1); j++)
  10.          {
  11.                if (array[j+1] > array[j])
  12.               { 
  13.                     temp = array[j];
  14.                     array[j] = array[j+1];
  15.                     array[j+1] = temp;
  16.                     flag = 1;
  17.                }
  18.           }
  19.      }
  20. }
  21.  
This is the code I found, but as I said, I don't know how to pass a struct array to it. If I try floo[j+1].number I get an error.
Also, I don't want to rearrange them sorted (like in the code above) but put them sorted into another array.
Feb 5 '07 #1
Share this Question
Share on Google+
2 Replies


100+
P: 1,646
Hi. You should copy to the array that you want to be sorted and pass that to your sort algorithm. This is a version of heap sort that I have adjusted to fit the struct you used as an example. This will work for any array of any struct. You just need to replace the type, Foo, with the struct type and the element, number, with the struct element that you wish to sort with.
Expand|Select|Wrap|Line Numbers
  1. void HeapSort(Foo* list)
  2. {
  3.    long size = sizeof(list) / sizeof(list[0]);
  4.    Foo tmp;
  5.  
  6.    for(long i = size/2; i > 0;) Heapify(list, --i, size);
  7.  
  8.    for(long i = size-1; i>0; --i)
  9.    {
  10.       tmp = list[0];
  11.       list[0] = list[i];
  12.       list[i] = tmp;
  13.       Heapify(list, 0, i);
  14.    }
  15. }
  16.  
  17. void Heapify(Foo* A, long i, long heapsize)
  18. {
  19.    while(true)
  20.    {
  21.       long l = 2*i+1;
  22.       long r = 2*i+2;
  23.  
  24.       long largest = (l < heapsize && A[i]->number < A[l]->number) ? l : i;
  25.  
  26.       if(r < heapsize && A[largest]->number < A[r]->number)
  27.          largest = r;
  28.  
  29.       if(largest != i)
  30.       {
  31.          foo tmp;
  32.          tmp = A[i];
  33.          A[i] = A[largest];
  34.          A[largest] = tmp;
  35.          i = largest;
  36.       }
  37.       else break;
  38.     }
  39. }
Feb 5 '07 #2

P: 5
Sorry for such a late reply. Just wanted to say thanks, it worked.
Feb 8 '07 #3

Post your reply

Sign in to post your reply or Sign up for a free account.