Sorting Array of Pointers in C++

Question

Hoping I can get a little advice on a sorting method I made.

The purpose of this code is to create a int pointer array and sort the pointers in that array by the contents of regular int array. Then assign values for a different variable based on the location of the original int array.

The strangeness I am experiencing with this code is that the test code which shouldn't effect anything as far as I know... IS actually effecting the contents of my pointers. Perhaps the values aren't changing but the way I'm writing the test code is causing errors.

 //create array
 int c[8] = {3,1,5,7,8,2,6,4};
 //create pointer array
 int *newptr[8];
 for(int k = 0; k<8; k++)
 {
     newptr[k] = &c[k];
 }
//sort pointer array
for(int j = 0; j<8; j++)
{
    for(; j > -1 && *newptr[j] < *newptr[j+1]; j--)
    {
        int *temp = newptr[j+1];
        newptr[j+1] = newptr[j];
        newptr[j] = temp;
    }
}
//set lookuplocation
int lookuplocation;
for(int i = 0; i<8; i++)
{
    cout << *newptr[i];

    if(newptr[i] == &c[0])
    {
        cout << *newptr[i] << endl;

        //If I use endl or \n to test the pointers values I end up with only
        //a part of the correct data. 

        cout << "\nSuccess!\n";
        lookuplocation = 0;
    }
}
//Also for my last test sometimes the first element gets messed up as well
//test arrays
for(int k = 0; k<8; k++)
{
    cout << "Element " << k << ": " << *newptr[k] << endl;
    cout << "Element " << k << ": " << newptr[k] << endl;
}

Solution 1

I figured someone might actually need to sort an array of pointers in a sane way:

#include <iostream>
#include <array>
#include <algorithm>

int main() {
    std::array<int, 8> arr { 3, 5, 4, 1, 2, 7, 6, 8 };
    std::array<int*, 8> p_arr;

    for (unsigned i = 0; i < 8; ++i) {
        p_arr[i] = &arr[i];
    }

    std::sort(p_arr.begin(), p_arr.end(), [](int* a, int* b) { return *a < *b; });

    for (auto i : p_arr) 
        std::cout << *i;
}

The ugly middle loop is totally replace'able by range for over zippped range, but I don't have my own implementation with reference semantics right now, and I am too lazy to check the Boost one.¹

Here's a live sample on Coliru.

Also, because I think we should repeat this over and over until newbies understand it:

• Don't reinvent the sorting wheel (unless it's a toy implementation)
• Try to avoid using pointers in C++ if reasonably possible.

---

¹This is actually important in order to make sure both ranges (in this case two arrays) have the same length. Different zipping conventions either require the ranges to be of the same length (crashing or throwing otherwise) or fill in the empty data should one of the ranges be too short. While seemingly obvious in such a simple program, be careful in real-world code.

Solution 2

If your array c[n] has for range [1 .. n], you can use the following algorithm which work in O(n) time complexity:

for(int j = 0; j < n; j++)
    while(*newptr[*newptr[j] - 1] != *newptr[j])
        std::swap(newptr[*newptr[j] - 1], newptr[j]);

The idea behind it is to assign the value 1 to the pointer newptr[0], 2 to the pointer newptr[1], ..., and n to the pointer newptr[n-1]. There is no algorithm that is more efficient (especially in C++11, since std::swap will use std::move).

So for int c[8] = {3,1,5,7,8,2,6,4}, you get (disregarding the reference to value table):

1233

Success!
45678

---

Update: If you want the reverse order:

for(int j = 0; j < n; j++)
    while(*newptr[n - *newptr[j]] != *newptr[j])
        std::swap(newptr[n - *newptr[j]], newptr[j]);

For int c[8] = {3,1,5,7,8,2,6,4}, you get:

8765433

Success!
21

Solution 3

Popular approach is to implement generic sort function that sorts elements with given comparator, so you can abstract over array elements. There are some ways:

template<typename ElementType, typename CompType>
void sort(ElementType array[], size_t size, CompType cmp);
template<typename ElementType, typename CompType>
void sort(std::vector<ElementType> & array, CompType cmp);
template<typename IteratorType, typename CompType>
void sort(IteratorType first, IteratorType last, CompType cmp);

Last way is preferable because you can abstract over container type too.