sorting linkedlist

[jdeboer]

Greetings all,

I'm sure this is a topic that's been well traversed allready but i just can't figure out the solution for my specific case and i'm hoping somebody can give me some help.

I'm new to C++ (or C for that matter) and i'm trying to create a linked list and then outputting said linked list and sorting the contents (either asc or desc.) But i've gotten to the point where i've got the linked lists and output working. But i can't for the life of me figure out how to properly sort the output.

Here's the code:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

struct numberslist {
        int number1;
        int number2;
        int number3;
        numberslist* next;
        };

int main() {
        srand(time(NULL)); //Create random nummer, seed is time voor randomize.


numberslist* newrcd;               //maak pointer aan voor n. Maken hiermee newrcde structs aan.
numberslist* temp;               //maak pointer aan voor t. Linken hiermee de boel aan elkaar.
numberslist* head;               //maak hiermee een start punt.

newrcd = new numberslist;          //maak newrcde struct aan.
newrcd->number1 = rand();             //vul met data.
newrcd->number2 = rand();
newrcd->number3 = rand();

temp = newrcd;          //definieer t voor linken van lists.
head = newrcd;          //definieer h zodat we altijd terug naar start kunnen.

newrcd = new numberslist;
newrcd->number1 = rand();
newrcd->number2 = rand();
newrcd->number3 = rand();

temp->next = newrcd; // verplaats t naar voren van oude struct.
temp = newrcd; //verplaats t weer naar de next in struct.

newrcd = new numberslist;
newrcd->number1 = rand();
newrcd->number2 = rand();
newrcd->number3 = rand();

temp->next = newrcd; // verplaats t naar voren van oude struct.
temp = newrcd; //verplaats t weer naar de next in struct.

newrcd = new numberslist;
newrcd->number1 = rand();
newrcd->number2 = rand();
newrcd->number3 = rand();

temp->next = newrcd; // verplaats t naar voren van oude struct.

temp = newrcd; //verplaats t weer naar de next in struct.
newrcd = new numberslist;
newrcd->number1 = rand();
newrcd->number2 = rand();
newrcd->number3 = rand();

temp->next = newrcd;            //verplaats t weer.
newrcd->next = NULL;         //Eindig lijst.


//Loop om getallen uit te printen.
numberslist *current = head;
while( current != NULL ) {
cout << (*current).number1 << endl;
cout << (*current).number2 << endl;
cout << (*current).number3 << endl;
current = current->next;
}

//Loop om alle nodes te verwijderen om memory leak te voorkomen.
while( current != NULL ) {
delete newrcd;
current = current->next;
}

                return 0;
}

Now i know it's possible to use recursion and then sort the whole bunch but i have no idea how to use recursion.
So i've resorted to stuffing the whole bunch into an array and then trying to sort the array. I've gotten as far as to get everything into the array but then my code fails to compile due to a logical error where i'm stuffing a PTR value in a integer value.

As such:

while( current != NULL) {

int currentarray[15] = {(*current).number1,(*current).number2,(*current).number3};
        for(int i=0;i< sizeof(int[15])-1;i++){
        for(int j=i+1;j< sizeof(int[15]);j++){
                if(currentarray[i] > currentarray[j]){
                 temp = currentarray[i];
                currentarray[i] = currentarray[j];
                currentarray[j] = temp;
                }
        }
        cout << "\n Sorted list, ascending.";
        for(int i=0; i< sizeof(int[15]);i++)
        cout << " " << currentarray[i];
        cout << endl;
        return 0;
        }

current = current->next;
}

I'm sure that's very nonsensical and noobish but i'm at a loss on how else to achieve this short from rebuilding everything and then just inserting everything into the linkedlist sorted already..

Any help would be greatly appreciated.

Regards,
Jdeboer

[Moschops]

Start simple.

Look at first two items in the list. If they're in the wrong order, swap them. Look at the second and third item. If they're in the wrong order, swap them. Look at the third and forth items in the list....

When you've gone through it, if you did ANY swapping, start again

Eventually, you'll get through the list without having swapped anything. The list is sorted when this happens.

For this, you need to write a function to swap two adjacent elements in your list, and a function to know if two items are in the right order, and that's it. Something like:

bool did_a_swap = true;
while (did_a_swap)
{
  did_a_swap = false;
  for (int i = 0; i < list.size()-1; i++)
  {
    if ( listItem[i] > listItem [i+1])
      {  
          swap(listItem[i], listItem [i+1]);
          did_a_swap = true; 
      }
  }
}

[jdeboer]

Moschops, thank you very much for the reply.
That does make a lot more sense !

One question i have though, if you'll bare with me, by "listItem[value]" and list.size do you mean the array or the actual linkedlist. I get a bit confused by terminology that a lot of people use and it seems a lot like people can adress the list itself directly whilst that doesn't work for me.

This is how i somehow interpret your code into mine:

bool did_a_swap = true;
while (did_a_swap)
{
  did_a_swap = false;
  for (int i = 0; i < currentarray.size()-1; i++)
  {
    if ( currentarray[i] > currentarray [i+1])
      {  
          swap(currentarray[i], currentarray [i+1]);
          did_a_swap = true; 
      }
  }
}

But if i try it like that i just get a compile error. Now i know i shouldn't copy it over litteraly but i just can't help by shake the feeling that i'm misinterperating the whole lists - arrays and how to adress a list.

[Moschops]

When sorting a linked list, you're not meant to dump them all into an array. You're meant to go through the list, comparing each object with the next one.

Do not put them all into an array.


Imagine the start of the list was an object named head.

You look at head, and you look at the next one (which you can get easily; head->next). If they need to be swapped around, swap them around. Then you look at next, and the one after that.

It's a simple cycle and if you don't understand it, stop programming and think. Draw it out on paper. Seriously. There's no point typing if you don't understand what you're doing.