Thread: generic insertion sort

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    18

    generic insertion sort

    So I have an insertion sort here that is supposed to take in any type of input. I have the insertion algorithm correctly. The problem is with the swapping of the pointers. I don't really see what I'm doing wrong.

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include "inssort.h"
    
    void inssort (void *base, size_t nelem, size_t size,
                   int (*compar) (void *, void *))
    {
       //int i, j;
    
       
       for ( size_t i = 1 ; i <= nelem; i++ )
       {
          //size_t offset = size * i;
          void *element = (char *) base + i * size;
          //void *element2 = (char *) base + (i-1) * size;
       
          //(void) printf("element: %c  element2: %c\n", *(char*)element, *(char*)element2); 
          
          //double *value = (double *) element;
          //double *value2 = (double *) element2;
          //printf("e1: %s  e2: %s\n", element, element2);
           
          int slot = i;
          //void *key = malloc ( 200);
          //memcpy( key, element, ((i+1)*size) - (i*size) );
          
          void *key =  element;
          
          //Move all values smaller than key up one position
          for ( ; slot > 0; --slot )
          {
             void *ele1 = (char *) base + slot * size;
             void *ele2 = (char *) base + (slot-1) * size;
          
             int cmp = (*compar)(ele1, ele2);
             
             if ( cmp > 0)
                break;
                
             ele1 = ele2;
    
          }
          
          element = key;
       }
       //free ( key);
    }   
    
    int numcmp( void *s1, void *s2)
    {
       double *no1 = (double *) s1;
       double *no2 = (double *) s2;
       
       //(void) printf("v1: %lg   v2: %lg
    ", *no1, *no2);
       
       if ( *no1 < *no2 )
          return -1;
       else if ( *no1 > *no2 )
          return 1;
       else
          return 0;
    }
    Here is the code used to call the function from main:

    Code:
    inssort( array, nelem, sizeof *array, numcmp);
    The parameters are correct I'm assuming.

  2. #2
    Registered User
    Join Date
    Nov 2011
    Posts
    63
    Code:
    void *ele1 = (char *) base + slot * size;         
    void *ele2 = (char *) base + (slot-1) * size;
           
             int cmp = (*compar)(ele1, ele2);
              
             if ( cmp > 0)
                break;
                 
             ele1 = ele2;
    You're not changing the array at all. All you are doing is changing where ele1 and ele2 point towards. If ele1 and ele2 were part of an array of pointers to the elements, than that would make sense, but they're just arbitrary pointers that you've created.

    Try adding these to your code:

    Code:
             /*ele1 = ele2; */ /* In other words, get rid of this line. */
             char *temp = malloc(size);
             memcpy(temp, ele1, size);
             memcpy(ele1, ele2, size);
             memcpy(ele2, temp, size);
    Consider strengthening you compiler warning checking flags. If you use something like -ansi -pedantic -Wall -Werror, then it'll help you see what's wrong with your program.
    Last edited by failure67; 11-23-2011 at 10:21 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Insertion sort
    By UserName112 in forum C++ Programming
    Replies: 2
    Last Post: 10-11-2011, 03:47 AM
  2. Insertion sort
    By Fatima Rizwan in forum C++ Programming
    Replies: 5
    Last Post: 02-26-2010, 02:24 PM
  3. Replies: 1
    Last Post: 01-26-2010, 09:02 AM
  4. Insertion sort... Please help!
    By xMEGANx in forum C++ Programming
    Replies: 11
    Last Post: 11-30-2007, 03:30 AM
  5. Insertion sort
    By Hypercase in forum C Programming
    Replies: 9
    Last Post: 08-31-2004, 04:02 AM