0
$\begingroup$

Given doubly linked list $L$ that contains $n$ elements of numbers. Between QuickSort, and MergeSort and InsertionSort, which algorithm preferred to sorting $L$ by just swapping links of $L$?

I think the InsertionSort is better option but I have no any idea to show that that minimize number of changing pointers. Any help will appreciated?

Suppose in below black edge is previous link and green edge is next link, after swapping liknks: enter image description here

Improve this question
$\endgroup$
8
  • $\begingroup$ Are you allowed to use nonconstant external working memory? Are you allowed to temporarily make a copy of a number outside of L? $\endgroup$ Commented Dec 18, 2022 at 13:30
  • $\begingroup$ Yes we are allowed to use auxiliary memory. $\endgroup$ Commented Dec 19, 2022 at 3:23
  • $\begingroup$ @Mohammad.Rostami Suppose a node is a pair of pointers $(n, p)$ where $n$ points to the next node and $p$ points to the previous node (and the data part is omitted). Suppose there are nodes $e_1:=(n_1\to e_2, p_1\to e_0)$, $e_2:=(n_2\to e_3, p_2\to e_1)$, $e_7:=(n_7\to e_8, p_7\to e_6)$, $e_8:=(n_8\to e_9, p_8\to e_7)$, where the arrows are understood naturally. What is a swap of links/a change of pointers? Can you give an example with the setup here, showing the result of one change of pointers? $\endgroup$ Commented Dec 24, 2022 at 19:33
  • $\begingroup$ @JohnL. I add an example. $\endgroup$ Commented Dec 26, 2022 at 15:09
  • 1
    $\begingroup$ 1) Exactly which swaps do you make to achieve what you show in the picture? You can't achieve this by only swapping the pointers (i.e. if the operation is to swap the values in 2 pointers), since in the original picture pointer to $4$ occurs twice, but in the sorted version it occurs once. 2) Do you need to find the exact minimum number of swaps (i.e. current answers which only show $O(n)$ sequence when $O(1)$ sequence exists don't answer your question)? $\endgroup$ Commented Dec 26, 2022 at 19:54

3 Answers 3

Reset to default
0
$\begingroup$

Minimizing the number of changing pointers is equivalent to minimizing number of swaps, which is obtained by Selection Sort.

Improve this answer
$\endgroup$
0
0
$\begingroup$

Selection sort will sort in O(n^2) with O(n) pointer changes. So if for some reason you need to minimise the number of pointer changes, that’s it.

On the other hand, you can just put all the pointers into an array, sort the array, and reconstruct the double linked list.

(I actually had this in a job interview. I recommended either this, or bubble sort if it is absolutely not time critical because bubble sort of a double linked list is fun).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you argue that how Selection sort needs $O(n)$ pointer changes? $\endgroup$ Commented Dec 27, 2022 at 0:29
  • $\begingroup$ Selection sort will need O(n) pointer changes in most cases, and not more. It is very unusual that you measure the number of pointer changes and nothing else. $\endgroup$ Commented Dec 27, 2022 at 7:08
  • $\begingroup$ Can we claim that, Merge sort needs $O(n\log n)$ pointer changes? $\endgroup$ Commented Dec 27, 2022 at 16:05
0
$\begingroup$

Only MergeSort has a guaranteed $O(n\log n)$ behavior. You may well consider Natural MergeSort, that has the extra property of adaptiveness.

If you only care about swapping links (?), I guess that both StraightSelection and StraightInsertion achieve an optimal (certainly in the worst case, $O(n)$).

Improve this answer
$\endgroup$
7
  • $\begingroup$ Why you think insertion sort is optimal? $\endgroup$ Commented Nov 18, 2022 at 12:35
  • $\begingroup$ It moves every element once, doesn't it ? $\endgroup$ Commented Nov 18, 2022 at 12:36
  • $\begingroup$ But eac pointer could be changed multiple times over each insertion. How it change each pointer one time? $\endgroup$ Commented Nov 18, 2022 at 13:33
  • $\begingroup$ @Jut: how could it change multiple times ?? $\endgroup$ Commented Nov 18, 2022 at 16:02
  • $\begingroup$ Suppose $L=\langle 1,3,-1,2\rangle$, then we do nothing about $1$ and $2$, but we insert $-1$ before $1$ and $3$ after next iteration we insert $2$ between $1$ and $3$, so we change multiple times the pointer of $1$ and $3$. $\endgroup$ Commented Nov 18, 2022 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.