We help IT Professionals succeed at work.

sorting a linked list

shilpi84
shilpi84 asked
on
5,455 Views
Last Modified: 2012-05-05
i want to sort a linked list which algorithm should be used and why such that sorting takes place with least complexity.
Comment
Watch Question

CERTIFIED EXPERT
Top Expert 2009

Commented:
Take a look at merge sort. It's generally perceived as the easiest way to sort a general linked list.

Of course, specific situations can require qpecific sorting algorithms ...
>>>> i want to sort a linked list

std::list has a sort member function. You'll find its implementation in <list> header. It uses a merge sort as jkr mentioned.

Regards, Alex
CERTIFIED EXPERT
Top Expert 2009

Commented:
I found this nice introductory page for you if you need to implement this for your own linked list datastructure :

http://en.wikipedia.org/wiki/Merge_sort

Author

Commented:
is insertion sort ok for sorting the linked list?
CERTIFIED EXPERT
Top Expert 2009

Commented:
I would only recommend it for small linked list, because it becomes very inefficient when the list grows larger.

It is easier to implement than merge sort, and I guess that's why you're asking ?

If it's just to play around a bit with sorting algorithms, or if you plan to only use it for small lists, then insertion sort is a good alternative.
In all other cases, I wouldn't pick it.
CERTIFIED EXPERT

Commented:
The insertion sort has complexity O(n**2). The merge sort has O(n log n) -- i.e. better. However, if the linked list was partially sorted, the insertion sort may be more efficient (depends on situation). As Infinity08 pointed out, have a look also at http://en.wikipedia.org/wiki/Insertion_sort.

However, if you have the choice to use std::list<>, then you probably want to use it and use its built-in sort method, as Alex mentioned.
Deepu AbrahamR & D Engineering Manager

Commented:
Insertion sort is less efficient than Quick sort or Merge sort. You can use STL methods that are much efficient and time tested functions.

Best Regards,
DeepuAbrahamK
Commented:
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION

Commented:
If you are looking singly linked list which is being sorted as it is created, check the following, may help you some.

void LinkedList::addToList(ItemType item)
{
      LList *newObject, *currentPoint, *listBegin;

      newObject = new LList(item,NULL);
      
      if (list == NULL) {
            /* if list is empty, add the newly created one and leave */
            list = newObject;
            return;
      }

      listBegin = list;
      currentPoint = list; /* keep the pointer where to add/insert */
      do {  
            /*if list is not empty */
            if (newObject->data <= currentPoint->data) { // if lower than the current one
                  newObject->next = currentPoint;
                  if (list == currentPoint)      // if inserted at first
                        listBegin = newObject;      // update the list beginning pointer to be the new one
                  break;
            }
            else
            if (currentPoint->next && newObject->data <= currentPoint->next->data) { /* if lower than the current's next, insert in between */
                newObject->next = currentPoint->next;
                  currentPoint->next = newObject;
                  break;
            }
            else if (currentPoint->next == NULL) { /* add at end */
                        newObject->next = NULL;
                        currentPoint->next = newObject;  
                        break;
            }
            currentPoint = currentPoint->next;
            
      } while (currentPoint);

      list = listBegin;      // before returning, just update the list beginning pointer, if any
      return;
}


Good luck :)

Author

Commented:
I want to implement a quick sort function on a singly linked list.. can you guide me how to goo about that

Commented:
Is your list already created or you want to write a damn fresh liniked list program?

Author

Commented:
i have already created the list.i just want 2 apply sorting on.quicksort appears 2 be so complex 4 linked list.
CERTIFIED EXPERT
Top Expert 2009

Commented:
Then how about merge sort as I suggested in the beginning. Check the page I posted for the algorithm which should make it easy for you to implement.

Also read my comments on insertion sort, which is easier to implement, but less effective on larger linked lists.
Hamed ZaghaghiMachine Learning Engineer
CERTIFIED EXPERT

Commented:
Hi Shilpi..,

I just want to tell you that if your data in the linke list is in a specific range, then you can use some other sorting algorithms like radix sort, with O(n), but remember that in this sort algorithms your data must be in an specific range.


have a good programming day;
CERTIFIED EXPERT

Commented:
zaqhaqhi: On a single processor, the best sorting algorithm has complexity O(n log n). I guess you know that because you emphasize the "specific range". But if I exagerate a bit, then the same way I can say "if the number of sorted elements is limited by a specific value, then any sort has complexity O(1) ;-) No offense, we were also taught that about radix sort. (Students on some level should not be flooded by details to get the core ideas.)

In my opinion, one have to choose the sort that fits with the representation of the sorted data and with the working environment. If it is not a critical part of the solved problem, then you are free to choose one of many possible solutions. Many of them are "quite good".

For radix sort, it was invented in time when punch cards were the main information media. The radix sort is perfect for the problem, because it is very suitable for that representation (punched cards) and can be performed in a specific environment (mechanical device). Citation from http://en.wikipedia.org/wiki/Radix_sort: "A radix sorting algorithm was originally used to sort punched cards in several passes. A computer algorithm was invented for radix sort in 1954 at MIT by Harold H. Seward. In many newer applications requiring super speeds and massive memory, the computer radix sort is an improvement on (slower) comparison sorts."

However, it is not a good idea to choose the sort blindly only because it has better theoretical complexity. For example, the radix sort needs to separate the digits of the sorted numbers. It may be still suitable if your numbers are stored in BCD (binary coded decimals). However, separating digits programmatically from say normal integers may be more time consuming than comparison of whole numbers on modern processors.

To summarize: Choose ready-to-use solution for std::list or the like structures. You can bet that clever people already thought about the problem and chose at least one of the best compromises. If you should make the choice, consider the features like stability, how much additional memory it needs, for what problems it is suitable... (see http://en.wikipedia.org/wiki/Sorting_algorithm).

P.S. Some of the sorts were clearly beaten by others. Sometimes the catchy name or easy implementation make some sorts more popular (like bubble sort, quick sort) and some of really good sorts are rather invisible for beginners (like the mentioned merge sort).

Gain unlimited access to on-demand training courses with an Experts Exchange subscription.

Get Access
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Empower Your Career
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE

Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Unlock the solution to this question.
Join our community and discover your potential

Experts Exchange is the only place where you can interact directly with leading experts in the technology field. Become a member today and access the collective knowledge of thousands of technology experts.

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.