Thread: Sort algorithm and an ugly error

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    417

    Sort algorithm and an ugly error

    Code:
    // POINT_BUBSORT.CPP
    // Bubble sort function. Sorts an array of ints in descending order.
    template<class element>
    void pointerBubbleSort(apvector <element> &array, int n)
    {
      apvector <element*> pointer(n);
      int i, j, flag = 1;
      int *temp;
    
      for (i = 0; i < n; i++)
    	  pointer[i] = &array[i];
    
      for(i = 1; (i <= n) && flag; i++)
       {
         flag = 0;
         for(j = 0; j < (n - i); j++)
    	{
    	  if (pointer[j + 1] > pointer[j])
    	   {
    	     temp = pointer[j + 1];
    	     pointer[j + 1] = pointer[j];
    	     pointer[j] = temp;
    	     flag = 1;
    	   }
    	}
        }
    }
    There's my sort algorithm. Please don't tell me whether its a good one or not, I'm trying out some ideas and need to find out for myself.

    I'm trying to sort using pointers to characters in a vector. For some reason it is always going out of bounds with a negative number, even if I initialize them to death. Apvector has bounds checking, and it keeps closing the program.

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    It looks as though you are comparing the addresses instead of the values. I'm not sure if this is what is causing your problem, but you'll need to dereference the pointers before you compare them to get an accurate sort.

  3. #3
    Registered User
    Join Date
    Sep 2002
    Posts
    417
    I was trying to find a way to make it so that instead of physically moving the data or moving integers representing the data that you could compare them and then change the memory address associated with an entry.

    I don't know if this is possible, but if it is... then couldn't you "move" an entry a lot faster?

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Its definately possible, but you still need to make sure that you are comparing the actual data instead of the address.

    Change
    Code:
    if (pointer[j + 1] > pointer[j])
    to
    Code:
    if (*pointer[j + 1] > *pointer[j])
    and it should work as far as I can tell.

  5. #5
    Registered User
    Join Date
    Sep 2002
    Posts
    417
    I got it working.

    Here's my excellent results:

    Using the regular bubble sort I didn't right, sorting 10000 randomly chosen integers between 0 and 10000, it took 36 seconds.

    Using my pointer bubble sort, and the exact same integers, it took 2 seconds.

    I'll post the sorts up in a minute.

    [Edit #2] I'm running it with 100,000 elements now. I set it to output i (the number of times it went through the outer for loop) every 100 (if (i%100==0) ) times, and with my pointer one to output i every 1000 times.

    It outputs i the first sort about every 8 seconds (so every 8 seconds 100 outer loops have gone by)

    With the second loop, about every 5 (every 1000 elements, 10 times the other!) seconds it outputs i.

    Thats almost like comparing the speed of an ant to the speed of an airplane![/Edit #2]
    Last edited by Trauts; 02-24-2003 at 11:51 AM.

  6. #6
    Registered User
    Join Date
    Sep 2002
    Posts
    417
    My sort!
    Code:
    // POINT_BUBSORT.CPP
    // Bubble sort function. Sorts an array of ints in descending order.
    // Copyright Dylan Horkin 2002
    //template<class element>
    void pointerBubbleSort(int *array, int n)
    {
      int *pointer = array;
      int i, j, flag = 1;
      int temp;
    
      for(i = 1; (i <= n) && flag; i++)
       {
         flag = 0;
         for(j = 0; j < (n - i); j++)
    	{
    	  if (pointer[j + 1] < pointer[j])
    	   {
    	     temp = pointer[j + 1];
    	     pointer[j + 1] = pointer[j];
    	     pointer[j] = temp;
    	     flag = 1;
    	   }
    	}
    	 if (i%1000 == 0)
    		 cout << i << endl;
        }
    }
    And theirs:

    Code:
    // BUBSORT.CPP
    // Bubble sort function. Sorts an array of ints in descending order.
    template<class element>
    void bubbleSort(apvector <element> &array, int n)
    {
      int i, j, flag = 1;
      int temp;
    
      for(i = 1; (i <= n) && flag; i++)
       {
         flag = 0;
         for(j = 0; j < (n - i); j++)
    	{
    	  if (array[j + 1] > array[j])
    	   {
    	     temp = array[j + 1];
    	     array[j + 1] = array[j];
    	     array[j] = temp;
    	     flag = 1;
    	   }
    	}
    	 if (i%100 == 0)
    		 cout << i << endl;
        }
    }

  7. #7
    Registered User
    Join Date
    Sep 2002
    Posts
    417

    Timing

    I calculated approximately how long it would take for the AP book's sort algorithm to sort, which is about 222.22 minutes to sort 100,000 random numbers

    My sort would take about 293.392 seconds exactly (4.88986 minutes).

  8. #8
    Registered User
    Join Date
    Sep 2002
    Posts
    417
    New sort algorithm, this time an insertion sort:

    Code:
    // POINT_INSSORT.CPP
    // Insertion sort function. Sorts an array of ints in descending order.
    //template<class element>
    void pointerInsertionSort(int *array, int n)
    {
      int *pointer = array;
      int i, j, key;
      int temp;
    
      for(j = 1; (j < n); j++)
       {
         key = array[j];
    
    	 // Move all values smaller than key up one position
         for(i = j - 1; (i >= 0) && (array[i] > key); i--)
    	 {
    		pointer[i + 1] = pointer[i];
    	 }
    	  pointer[i + 1] = key;
    	}
    //	 if (i%1000 == 0)
    //		 cout << i << endl;
    }
    This one completed the same 100000 element test with these results:

    Bubble Sort: 222.22 minutes
    Pointer Bubble Sort: 4.88986 minutes
    Pointer Insertion Sort: 1.40601667 minutes (84.361 seconds)

Popular pages Recent additions subscribe to a feed