Sorting a linked list

[erik341]

Today I started reading about linked lists and I decided to make a program that asks the user how many random numbers wishes to create; then it shows all those random numbers in an unsorted way; right after that it shows the numbers sorted.

At first I did this with arrays and it was pretty easy; but with the linked list I've got no idea of how can I sort all this numbers... here is the code, hope you understand the question!

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

using namespace std;
struct number
{
    int random_number;
    number* p_next_number;
};
number* p_list_numbers = NULL;
number* get_new_number(int i)
{
    number* p_number = new number;
    p_number->random_number = i;
    p_number->p_next_number = p_list_numbers;
    p_list_numbers = p_number;
    return p_number;
}

void show_numbers(int i)
{
    int count_numbers = 0;
    while (p_list_numbers != NULL)
    {
       cout<< p_list_numbers->random_number;
       if (count_numbers < (i-1))
       {
           cout<< ", ";
       } else
       cout << ".";
       p_list_numbers = p_list_numbers->p_next_number;
       count_numbers++;
    }
}

void order_numbers(int i)
{
    int smaller_number = p_list_numbers->random_number;
    number* p_smaller_number = p_list_numbers->p_next_number;
    for(int j = 0; j < i; j++)
    {
        p_list_numbers = p_list_numbers->p_next_number;
        if (smaller_number > p_list_numbers->random_number)
        {
            smaller_number = p_list_numbers->random_number;
            p_smaller_number = p_list_numbers->p_next_number;
        }
    }
    /* in theory now smaller_number is the smallest number on 
       the list and p_smaller_number is a pointer pointing to where 
       the smallest number is, but what do I have to do now? */
}

int main()
{
    long int times;
    cout<<"How many numbers do you wish me to order? ";
    cin>>times;

    srand(time(NULL));

    for (int i = 0; i < times; i++)
    {
        int random = rand() % 100;
        get_new_number (random);
    }
    cout<< "These are the original numbers: ";
    show_numbers(times);

    order_numbers(times);

    cout<< "\nThese are the ordered numbers: ";
    show_numbers(times);
}

[MiiNiPaa]

1) create array holding pointers to each list element
2) sort pointers by values they are pointing to.
3) Rebuild list by new order.

Another variant is to implement insertion sort: basically your list is divided by 2 parts — sorted (in the beginning) and unsorted. Each pass you are taking one element from unsorted part and inserting it in their place in sorted part.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/insertion-sort/

[erik341]

so if I understood right, the second variant orders the list while it is creating it?

[MiiNiPaa]

First orders already existing list loo. It just do not takes in account exisiting links completely rewriting them in the end.

[erik341]

And is there a way of doing it without arrays? Because I would like to order MANY numbers, maybe a million (when I did this program with arrays it couldn't create 1 million numbers, but with linked list it could; I actually was able to create even 10 million random numbers and save them in a linked list wich took almost 18 minutes)

[MiiNiPaa]

It is not good to store trivial types in linked lists. On 64bit machine you use trice as much memory as you would with array. In your case you should consider deque to store your numbers.

Nevertheless, best approach to sort linked list is mergesort. It is more complex than insertion sort, but it has good asymptomatic and will be way faster in your case.

First google hit: http://www.geeksforgeeks.org/merge-sort-for-linked-list/

[erik341]

Perfect!!! Thank you very much!! One last question, as I'm using new memory all the time I'm creating a number, do I need to use the delete funciton? if so, when and how? And what happens if I don't delete? do I ran out of RAM memory or something like that?

[MiiNiPaa]

as I'm using new memory all the time I'm creating a number, do I need to use the delete funciton?

Yes

if so, when and how?

When you do not need that memory. Say if you are deleting number from list or destroying list itself.

And what happens if I don't delete? do I ran out of RAM memory or something like that?

Yes. That memory will be never reclaimed back and you will eventually run out of it.

Did you consider using standard library faculties which manage memory for you? And has a built-in sort()?

[erik341]

No idea what's that... as you can guess I just started with c++ and don't know much... so even after the program is closed, that memory is still being used?
If I shutdown my computer that memory will be freed... right?

[MiiNiPaa]

so even after the program is closed, that memory is still being used?

No, generally modern OS will forcebly release program memory, but in more complex programs this will lead to all kinds of problematic behavior.

Using C++ in C-like approach is detrimental to learning it as a high-level language. You will fare better with C in this case.

In C++ there is std::list which does exactly what you need:

1 2 3 4 5 6 7 8 9 10

#include <iostream> #include <list> int main() { std::list<int> f = {1, 4, 6, 8, 3}; f.sort(); for (auto i: f) std::cout << i << ' '; }

1 3 4 6 8

Or better, use deque:

1 2 3 4 5 6 7 8 9 10 11

#include <iostream> #include <deque> #include <algorithm> int main() { std::deque<int> f = {1, 4, 6, 8, 3}; std::sort(f.begin(), f.end()); for (auto i: f) std::cout << i << ' '; }

1 3 4 6 8

[erik341]

Damm! Looks much simpler than what I was trying to do xD and for the delete function I don't have to worry? I just don't put it (in this case)?

[MiiNiPaa]

Well, you still need to delete list when you done with it, so you have to write delete list function in your code.

If you want to learn more about how to work with C++ containers start from here: http://www.mochima.com/tutorials/vectors.html

It describes vector: a continuous dinamicaly sized safe array. Most operations it supports other containers support as well.

[erik341]

Okok, I'll look at it, if I restart my pc the memory will be liberated, right?

[MiiNiPaa]

It would be freed when your program finishes. But you still need to learn to never allow memory leaks. Or it would bite you in the back soon.