Sorting a linked list in C++ using an array to sort its data

Question

I tried to sort a list, by copying each of the nodes' data into an array. Then after the code that sorted the array, I attempted to copy the value in the elements of the array into each of the nodes' list. Is that even possible, I tried researching the question couldn't find a straight up yes or no. I don't want to use qsort from cstdlib, this crashes, I would like to know if there is a way to make this work. Insight appreciated.

template <typename NODETYPE>  
void List<NODETYPE>::sort(){ 
ListNode<NODETYPE>* currentPtr = firstPtr;
    int N = sizeOfList();
    NODETYPE a[N];
    int l = 0;
    int r = 0;
    int i,j,min,imin,tmp;

    while(currentPtr != NULL){
        a[l] = currentPtr->data;
        currentPtr = currentPtr ->nextPtr;
        l++;
    }

for (i=0;i<N-1;i++)
{
    imin=i;
    min=a[i];
    for (j=i+1;j<N;j++)
        if (a[j]<min)
        {
            min=a[j];
            imin=j;
        }

    tmp=a[imin];
    a[imin]=a[i];
    a[i]=tmp;
}


    for ( int y = 0; y < N-1; y++ ){
        currentPtr->data = a[y];
        currentPtr = currentPtr->nextPtr;
    }
    lastPtr->data = a[N];

}

Is that even possible -- Sure it's possible -- it is a poor man's way of sorting a linked list, but it works. However this: int N = sizeOfList(); NODETYPE a[N]; is not valid C++, since arrays cannot be declared using a variable as the number of items. — PaulMcKenzie
– PaulMcKenzie, Commented Sep 17, 2016 at 0:48
NODETYPE a[N] is not standard C++, it's an extension in some compilers. Be aware that if the list is large, this will result in blowing your stack away. Consider using std::vector instead. You may also want to look into std::swap. — kfsone
– kfsone, Commented Sep 17, 2016 at 0:52
Also, does your List class have a public interface to allow the user from the outside to change the List's data? If not, you need to write one, as it is useless if there is no way to change the data. Is there a way for the outside world to iterate through the list, from beginning to end? Again, I ask this since it would be useless without it. Having those two functions allows you to "sort" the list easily by just utilizing what you've already written. — PaulMcKenzie
– PaulMcKenzie, Commented Sep 17, 2016 at 0:54
Implement your linked list using std::list, and use the sort method, or implement your linked list in terms of a vector. — EvilTeach
– EvilTeach, Commented Sep 17, 2016 at 0:54

Sam Varshavchik · Accepted Answer · 2016-09-17 00:50:15Z

First of all, use std::sort instead of your manual sorting code. The reason that qsort() crashed is because it's a C library function that knows nothing about C++ classes. std::sort() will be able to correctly sort your array.

Setting that aside, there are multiple bugs in the code that gets executed after the sort. The current code does the following:

for ( int y = 0; y < N-1; y++ ){
    currentPtr->data = a[y];
    currentPtr = currentPtr->nextPtr;
}
lastPtr->data = a[N];

The problem here is that currentPtr was already used, before the sort, to walk through the list, and at this point it is NULL. If you simply tried discussing your code with your rubber duck, your rubber duck would've told you that.

So the very first iteration here results in a null pointer dereference, and a crash.

You simply need to:

Reset currentPtr back to listPtr.
You can get rid of the special-casing for the last element of the list. It accomplishes absolutely nothing useful. Besides, it's wrong:
```
lastPtr->data = a[N];
```

Since a has N elements, the last element is a[N-1], and this will run off the end of the array, resulting in undefined behavior.

Like I said, you can remove this completely, and simply iterate over the entire range:

for ( int y = 0; y < N; y++ ){

Finally, you appear to be using gcc's variable length array extension, which is non-portable. Instead of declaring

NODETYPE a[N];

You should simply use a vector:

std::vector<NODETYPE> a;

a.reserve(n);

... and then push_back() each value, in the loop that follows.

If you don't want to use std::vector, you can temporarily new the array, and then delete it afterwards.

Collectives™ on Stack Overflow

Sorting a linked list in C++ using an array to sort its data

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related