Thread: Insertion Sort on Array of Structs

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    2

    Insertion Sort on Array of Structs

    I'm trying to take my working selection sort (values largest to smallest ) and switch it a with an Insertion sort (values smallest to biggest). I have the year comparison working the problem is I'm exactly sure how I would compare the day and month using the insertion sort
    Code:
    Here is my Selection Sort
    int selectionSort(struct date *array, int size)
    {
       int i, j,temp;
       int moves =0;
    
       for(i=0; i<(size-1); i++)
           for(j=i+1; j<size; j++){
              if (array[i].year < array[j].year){
                  swap(array, i, j);
                  moves++;
              }
              else if(array[i].year == array[j].year)
                  if(array[i].month<array[j].month){
                      swap(array, i, j);
                      moves++;
                  }
              else if(array[i].year == array[j].year)
                  if(array[i].month == array[j].month)
                      if(array[i].day < array[j].day){
                          swap(array, i, j);
                          moves++;
                      }
    
    
           }
    
       return moves;
    }
    
    
    
    Here is what I have for my Insertion Sort
    
    void insertSort(struct date *array, int size)
    {
       int i, j, current;
    
       for(i=1; i<size; i++)
       {
          current = array[i].year;
          j = i;
          while((j > 0) && (array[j-1].year > current))
          {
             array[j].year = array[j-1].year;
             j = j - 1;
          }
          array[j].year = current;
       }
    }

  2. #2
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    If it was me, I would probably write a separate function to compare dates. You might need it in other situations as well.

  3. #3
    Registered User
    Join Date
    Mar 2008
    Posts
    2
    coulld there be any other way

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    There is ALWAYS another way, but writing a function that compares a date to another date and returns (for example) -1, 0 or 1 depending on whether first date is less, equal or greater than the second date.

    That would make your selection sort much simpler too:
    Code:
    int selectionSort(struct date *array, int size)
    {
       int i, j,temp;
       int moves =0;
    
       for(i=0; i<(size-1); i++) {
           for(j=i+1; j<size; j++){
              if (cmpDate(array[i], array[j]) > 0){
                  swap(array, i, j);
                  moves++;
              }
           }
       }
       return moves;
    }
    I also added the outer (red) braces to make it more readable and maintainable.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. for loop with sort issues
    By redmondtab in forum C Programming
    Replies: 10
    Last Post: 10-09-2006, 10:36 AM
  2. Sorting an Array of Structs not working
    By ashcan1979 in forum C++ Programming
    Replies: 9
    Last Post: 09-28-2006, 03:07 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM
  5. Recursive Array Sort
    By Nakeerb in forum C++ Programming
    Replies: 3
    Last Post: 12-13-2002, 08:27 PM