Thread: Heap Sort Problem

  1. #1
    Registered User
    Join Date
    Oct 2006
    Location
    istanbul
    Posts
    3

    Heap Sort Problem

    Hey, I am trying to generate random strings and sort'em using heap sort. It sorts well but there is a problem. The sorted array doesn't include the first generated string. Instead of it, it gives me a random string. I tested the random functions, I think they are ok.

    So, here is the full code, I hope somebody can help me.

    PHP Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
     
    charrandom_fill(int n, const char *src)
    {
        
    char *s;
        
    = (char*) malloc (n*sizeof(char));
        
    int src_len strlen(src);
        
    int i;
     
        for (
    0ni++)
        {
            
    s[i] = src[rand() % src_len];
        }
        return 
    s;
    }

    int randomNum(int max){
      
    int n;
      
    rand()%max+1;
      return 
    n;
    }

    void percDown(char** array,int root,int bottom);

    void heapSort(char** array,int size){
      
    int i;
      
    int j;
      
    chartemp;
      for(
    i=size/2;i>=0;i--)
        
    percDown(array,i,size);
      for(
    j=size-1;j>=1;j--){
        
    temp = array[0];
        array[
    0]=array[j];
        array[
    j]=temp;
        
    percDown(array,0,j);
      }
    }

    void percDown(char** array,int i,int n){
      
    int child;
      
    chartemp;
      for(
    temp=array[i];(2*i)+1<n;i=child){
        
    child 2*i+1;
        if(
    child!=n-1&&strcmp(array[child],array[child+1])<0)
          
    child++;
        if(
    strcmp(temp,array[child])<0)
          array[
    i] = array[child];
        else
          break;
      }
      array[
    i]=temp;
    }
     
    int main(void)
    {
        
    srand((unsigned)time(NULL));
        
    int maxLength;
        
    int numberOfStrings;
        
    scanf("%d",&numberOfStrings);
        
    scanf("%d",&maxLength);
        const 
    char *src "abcdefghijklmnopqrstuvwxyz";
        
    char** array;
        array = (
    char**) malloc(numberOfStrings*sizeof(char));
        
    int counter;
        for(
    counter=0;counter<numberOfStrings;counter++){
          array[
    counter] = random_fill(randomNum(maxLength), src);
          
    puts(array[counter]);
        }
        
    heapSort(array,numberOfStrings);
        for(
    counter=0;counter<numberOfStrings;counter++){
          
    printf("%s \n",array[counter]);
        }
        
    char a;
        
    scanf("%c",&a);
        return 
    0;


  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    It doesn't look like you've set up an array of strings properly.
    Code:
    int i;
    char **array = malloc( numberofstrings * sizeof(array[0]) );
    if ( array != NULL ) {
       for ( i = 0; i < numberofstrings; i++ ) {
          array[i] = malloc( maxlength + 1 );
          if ( array[i] != NULL )
            randomfill( maxlength + 1, src, array[i] );
       }
    }
    
    /* use it then release it */
    while ( numberofstrings-- > 0 ) {
       free( array[numberofstrings] );
    }
    free( array );
    The randomfill function will have to work in such a way that it does not allocate memory, in order for this to work as is.

    See here.

    Your randomfill function is also broken because the character arrays are not terminated with zero, which would make them strings. By definition, a C string is an ASCII sequence of arbitrary length with a zero as the last character. printf("%s \n", array[counter]); and a lot of other function calls will assume that you are working with the standard idea of a string.
    Last edited by whiteflags; 01-18-2011 at 06:49 PM.

  3. #3
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    your array should be an array of pointers... not an array of characters... you aren't allocating enough space...
    Code:
        char** array; 
        array = malloc(numberOfStrings*sizeof(char*));
    A char is sized 1 ... a char* is 4 bytes on a 32 bit system

    Also in random fill you aren't allocating enough space for the trailing null...

    Code:
        s = calloc ((n+1,sizeof(char));   // allocate and 0 fill
    Likely your sort is swapping garbage into that first string from the unreserved memory...

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    I don't have time to analyze the whole bit of code, but here are a couple of things that I noticed:

    1) in 'random_fill', you forgot to null-terminate the string. You should probably allocate n+1 bytes, as well.
    2) in 'main', 'array' was sized using sizeof(char) - that should be sizeof(char*)...

    [edit]
    nvm, beat me to it...
    [/edit]
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    Registered User
    Join Date
    Oct 2006
    Location
    istanbul
    Posts
    3
    Thanks for all your help guys. It works fine now .

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. problem with gets and bubble sort
    By wwwildbill in forum C Programming
    Replies: 4
    Last Post: 04-04-2009, 01:31 AM
  3. array sort output problem
    By radiantarchon28 in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2007, 01:49 AM
  4. Problem with Bubble Sort code
    By lisa1234 in forum C++ Programming
    Replies: 7
    Last Post: 01-13-2004, 03:40 PM
  5. Heap Sort - O(logn)
    By MethodMan in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 11-14-2002, 08:19 PM