Linked List Sorting Algorithm

[h4ckb0x7]

This is the algorithm I have so far and it works great. I was wondering what other people think?? Comments/Critiques??

void LinkedList::sort()
{
    if (head != 0)
    {
        Node* current = head;
        Node* prev = 0;
        Node* tempNode = 0;
        int changeFlag = 0;
        for (int i = 0; i < length; i++)
        {
            while (current->next != 0)
            {
                tempNode = current->next;
                
                if (current->value > tempNode->value)
                {
                    changeFlag = 1;
                    current->next = tempNode->next;
                    tempNode->next = current;
                    if (prev != 0)
                        prev->next = tempNode;
                    prev = tempNode;
                    if (head == current)
                        head = tempNode;
                    if (current->next == 0)
                        end = current;
                }
                else
                {
                    prev = current;
                    current = current->next;
                }
            }
            if (changeFlag == 0)
                break;
            else
            {
                prev = 0;
                current = head;
                changeFlag = 0;
            }
        }
    }
}

Cheers,
Scott

[vlad from moscow]

Why is data member length as I have understood defined as int? Is it possible that the length of the list can be negative value?

[h4ckb0x7]

What else would you define it as?? unsigned int??

Cheers,
Scott

[vlad from moscow]

Yes, it would be better if you would define in your class the type

typedef unsigned int size_type;

[h4ckb0x7]

What is the benefit? I don't see a downside to length being defined as an int. I doubt a list will end up with over 2 Billion nodes in it.

[vlad from moscow]

It is not a good idea when you select a type that has a domain that does not correspond to the values you are going to use.

[h4ckb0x7]

I don't get your reasoning behind this. Consider the following:

int main(int argc, char **argv);

When is argc ever going to be negative???? That's a standard piece of code and it is just using an int, not an unsigned int.

Cheers,
Scott

[vlad from moscow]

When main was invented in C there was not such keyword as unsigned.

[h4ckb0x7]

I know unsigned ints go as far back as at least C89.

[z05DSL3A]

h4ckb0x7,

C was started in 1969, unsigned int was introduced in K&R C around 1978.

[DeXecipher]

I can tell vlad is at least a pro by his style.

[h4ckb0x7]

If I add:

typedef unsigned int size_type;

to my class, should it be a public or private member?? Also, once I have done that and changed length's type to size_type as well as the return type of the size() member function, how would you rectify the following line:

for (int i = 0; i < length; i++)

With this:

for (int i = 0; size_type(i) < length; i++)

This:

for (size_type i = 0; i < length; i++)

Or this:

for (int i = 0; i < int(length); i++)

I'm still not really sure of the point of making the variable an unsigned int. I understand that unsigned holds only positive values, however, length is a private member variable and is initialized to zero and is only acted upon from within the class definition.

[doug4]

I would go with

for (size_type i = 0; i < length; i++)

The question of why is a good one. It's a question of semantics. In this situation, you could probably get away with working with an int because your code is fairly simple and you're the only one working with it. However, work on a large production system with 100 programmers and you might not be intimate with all the details. The more care you put into picking and designing data types, the more robust your systems will be and the easier it will be to debug problems in the future. It's best to get into that habit now with your simple programs.

On that note, I would also change the type of changeFlag to a bool. Making it a bool immediately shows the reader / maintainer that you are looking for a true/false value. Leaving it an int makes the reader / maintainer read the entire code block to interpret how it is used. Again, not a problem on a small project like this one, but it can come back to "byte" you on bigger projects.

[JLBorges]

> I'm still not really sure of the point of making the variable an unsigned int.

There is no point.

Though making it a std::size_t would be pedantically correct (the theoretical maximum number of nodes that the list can hold may be larger than the maximum value of an unsigned int).


> I understand that unsigned holds only positive values

The value that an unsigned int holds is interpreted as a non-negative value.

#include <iostream>

int main ()
{
    unsigned int u = -1U ;
    std::cout << u << '\n' ;
    int i = u ;
    std::cout << i << '\n' ;
}

http://ideone.com/7UY3uD

So, for( int i = 0 ; i < 25 ; ++i ) { /* .... */ }

And not for( unsigned int i = 0 ; i < 25U ; ++i ) { /* .... */ }

That the range of the loop involves only non-negative values of i is irrelevant.

unsigned int just_cant_be_negative ;
std::cout << "please enter a non-negative integer: " ;
std::cin >> just_cant_be_negative ;
// did the user type in a number with a minus sign (like -23)? 
// we just have no way of knowing. 

Unless it is a library defined type like std::size_t, std::time_t, std::string::size_type, std::uint32_t (or you want to perform bit-wise operations), just use a plain int as the default integer type.

[mik2718]

You could just

1. allocate an array of Node pointers of size length
2. set each pointer in the array to the corresponding list node
3. sort the pointers (using qsort - whatever) - you can access the node values through these pointers
4. reseat all the list node pointers by running along the array
5. delete the helper array

This will be much faster than a bubble sort

RE unsigned int for indexing into arrays - there is an awkward case where you want to scan an array from end to beginning with a simple for loop

for(unsigned int i = length; i>=0 ; --i)  // oh-oh condition is always true 

in this case the domain of the index is OK for the array but not for the loop condition