1

If this has been answered before, please point me in in the right direction!

So, I've been strolling around SO for some while reading about sorting. I was wondering however, what is the main difference between choosing a good sorting algorithm for a singly linked list vs a double linked list (and also linked structures compared to array structures)?

I know that (assuming we're in an OO-language) the type matters on the elements to be sorted etc (primitive types are typically faster than complex objects). I was comparing Java Strings and integers.

As far as I understand, when dealing with a linked structure, we should probably rule out Quicksort and Insertion sort since they deal a lot with indexing.

This question probably is bad, but as I mentioned, please point me to another source where I can read about choosing the correct algorithm (not how to implement an algorithm).

Improve this question
4
  • In your shoes, I'd analyze the code for sorting (various sorting) approaches already written in JDK. Commented Feb 15, 2018 at 17:40
  • 1
    We're not a substitute for Google. We don't point people to sources. Commented Feb 15, 2018 at 17:41
  • 1
    Possible duplicate of What's the fastest algorithm for sorting a linked list? Commented Feb 15, 2018 at 17:41
  • As linked to in an update from one of the answers in What's the fastest algorithm for sorting a linked list a bottom up merge sort is fastest for sorting a list (unless you copy to array, sort the array, create a new list, which is faster still). Just sort the list as if it was a single linked list, then make a single pass to set the previous pointers. Commented Feb 15, 2018 at 17:48

2 Answers 2

Reset to default
0

Yea, the idea of trying to stay away from indexing in linked structures is quite a good guideline. Note however, it is not a strict rule.

I know that (assuming we're in an OO-language) the type matters on the elements to be sorted etc (primitive types are typically faster than complex objects). I was comparing Java Strings and integers.

This is a very good thought! Primitive types have fast comparing time, so to Quicksort these works well (assuming that they're not in a linked structure).

Comparing Strings can be very expensive if they're long. Merge sort for lots of strings is therefore a good idea. So the main idea here is if we have expensive comparing, Merge sort is preferred. If we have fast comparing, Quicksort would probably be preferred (assuming we have a good technique to pick a Pivot value).

One idea can also be, for linked structures, to copy all of the list into a heap and from there perform a Heap Sort. But if we have limited memory, this is not a good way to encounter the problem.

If you can't decide a good sorting algorithm to apply to your code, follow the language standard. See for example this topic: Why Collections.sort uses merge sort instead of quicksort? [closed] .

A little list:

  • If you can't afford to use more memory: Quicksort.
  • If you can't afford slow comparisons: Merge sort.
  • If you have a really (really) large structure: Quicksort or Merge sort.
  • If you have linked structures: Merge sort.

Of course there are loads of combinations of scenarios where one has to choose carefully. There are also plenty of more sorting algorithms out there to use. I only referred to Merge and Quick since you seemed to know them quite well.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

I'd say there is no difference. For general comparison-based sorting algorithms, you're limited by O(n) reads and O(log(n)) comparisons.

Take merge sort for example, chopping up the list until the base case (a list with one item is already sorted) is reached. Then, you're merging and swapping items that fall out of order. Swapping in a singly or doubly linked list is both an O(1) operation.

Perhaps with a doubly linked list, if you know your data will follow some order of "partially sorted" structure eg. being "more sorted" forwards versus backwards, then you can write your list walk to walk in the specific direction that will yield less swaps, but in the end you still have an O(n log n) algorithm with a very, very marginally faster runtime due to only making O(log n) comparisons, less swaps.

Improve this answer

6 Comments

Yeah, the swapping itself might be O(1). But having to loop the list many times when we need to find new indexes is slow (for example when swapping smaller and larger elements after selecting a Pivot value in Quicksort).
@Oskarzito Not true. In a divide and conquer algorithm like merge/quick sort, the algorithm would already know which items to swap based on the fact that the merge/partition part would already have gotten to the items that need to be swapped. Only a poorly written or out of place sort would walk the list many times to "find" the items to swap (when the comparison already has the pointer to both items...)
yes, you have a great, but it is still a big problem for any linked structure to index in it. As for Quicksort, we have to find a good Pivot value as close to the middle value as possible. Then we need to swap elements to make them appear in the correct partition. Then do it again (divide and conquer). Imaging this process for Quicksort in a singly linked list. It's not optimal, so to say.
@Oskarzito true. Quicksort does a lot of swaps that require additional walks of both the sorted partitions and unsorted rest of the list. But, that's not a difference between sorting a singly and doubly linked list. That's just the difference between algorithms like Quicksort and algorithms like Mergesort. And even then, with a little caching of pointers to elements in the partition in an array, this difference goes away and accessing a specific index becomes O(1). So it stands to reason that there is no difference between sorting a single or doubly linked list.
aah, now I get your point! I did not reflect on that matter. So you're saying that when choosing an advanced sorting algorithm, it only matters to consider if it is an array structure or a linked structure, and not consider whether it is singly or doubly linked (since it will be the same)?
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.