current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite

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;
}
share|improve this question
1  
your sorting is messed up –  No Idea For Name Aug 5 '13 at 7:02
    
Nested loops with the same counter j ? How can it work at all? –  Alex Farber Aug 5 '13 at 7:03
    
no its not. It works just fine, I added only a little more to my current code before I got small bugs, and they still can be bypassed. I was just curious to why I was getting them in the first place. –  user2651901 Aug 5 '13 at 7:04
1  
Do you need to write the code to sort the array of pointers, or do you need to sort an array of pointers? Please specify which. If you don't need to write your own code, the solution is trivial. –  juanchopanza Aug 5 '13 at 7:11
3  
"I wasn't really taught to use them (STL containers) in class." - Of course you weren't, because eveybody knows C++ is best taught by teaching "C with cout" first. ;) –  Christian Rau Aug 5 '13 at 9:41
show 17 more comments

4 Answers

up vote 2 down vote accepted

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.
share|improve this answer
    
I think I said this somewhere, but I haven't learned to use stl in my class yet and I AM a newbie who is just starting to understand more about how to use pointers. Thanks for the better code but I was just trying to understand what mine did. –  user2651901 Aug 5 '13 at 20:19
    
@user2651901 you should learn Standard Library before pointers. –  Bartek Banachewicz Aug 5 '13 at 20:28
add comment
up vote 2 down vote

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

share|improve this answer
    
While this does work, it sorts the opposite way which I'm sure can be easily fixed. But my main problem that I'm dealing with is understanding whether or not I can do a comparison of the address of my original int array and the pointers. I'm pretty sure now that is what was messing up my code. –  user2651901 Aug 5 '13 at 8:45
    
Actually I believe I was overwriting my pointers. –  user2651901 Aug 5 '13 at 8:52
    
@user2651901: You mean you want the script to sort from 8 to 1 instead of 8 to 1? –  Kyle_the_hacker Aug 5 '13 at 10:03
    
yeah 8 to 1 not 1 to 8. –  user2651901 Aug 5 '13 at 20:22
    
@user2651901: Look the answer I updated 9 hours ago. –  Kyle_the_hacker Aug 5 '13 at 20:29
add comment
up vote 1 down vote

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.

share|improve this answer
add comment
up vote 0 down vote

Change this first:

for(; j > -1 && *newptr[j] < *newptr[j+1]; j--)

into

for(int i=j; i > -1 && *newptr[i] < *newptr[i+1]; i--)

It seems alot more efficient..

share|improve this answer
1  
but very confusing. simplicity is more important to me at this point. –  user2651901 Aug 5 '13 at 7:20
    
it's not, reusing the same j is confusing, it actually might lower the j in your outer loop which is probably not the purpose? –  irW Aug 5 '13 at 7:27
    
Hmm. Now that I think about it, it does reduce the amount of processing of numbers. It isn't necessary but it is a good idea. Thanks! –  user2651901 Aug 5 '13 at 7:36
    
@irW "alot" more efficient? link –  user529758 Aug 5 '13 at 13:15
    
yes you are right, it won't have a big impact, still it is silly to decrease the j in the outer loop since there is no reason for that. (when I wrote 'alot' I was incorreclty assuming j -> 0 every time) –  irW Aug 5 '13 at 13:29
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.