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.

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.

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?

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.

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]

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;
    }
}

---

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).

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)