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).

Jonas
  • 21
  • 2
  • In your shoes, I'd analyze the code for sorting (various sorting) approaches already written in JDK. – zlakad Feb 15 '18 at 17:40
  • 1
    We're not a substitute for Google. We don't point people to sources. – Kayaman Feb 15 '18 at 17:41
  • 1
    Possible duplicate of [What's the fastest algorithm for sorting a linked list?](https://stackoverflow.com/questions/1525117/whats-the-fastest-algorithm-for-sorting-a-linked-list) – Falla Coulibaly Feb 15 '18 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](https://stackoverflow.com/questions/1525117/whats-the-fastest-algorithm-for-sorting-a-linked-list) a [bottom up merge sort](https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists) 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. – rcgldr Feb 15 '18 at 17:48

2 Answers2

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.

TTT
  • 1,952
  • 18
  • 33
  • 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 Feb 15 '18 at 17:56
  • @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...) – TTT Feb 15 '18 at 17:59
  • 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 Feb 15 '18 at 18:08
  • @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. – TTT Feb 15 '18 at 18:14
  • 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)? – Oskarzito Feb 15 '18 at 18:53
  • @Oskarzito Yes, that's my thought. How the data is represented (array, linked) is a top-down optimization, which will yield reasonable gains in performance for good design. How you then access and manipulate this data (quick select, merge, etc) is a bottom-up optimization, it will make a difference depending on the specific use-case of the algorithm. Combine the two, and you see that there is actually no difference between representations, only the memory overhead and how the specific sort must be implemented for the desired performance outcome. – TTT Feb 15 '18 at 18:59
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.

Oskarzito
  • 458
  • 2
  • 13