0

I have to implement quicksort for single linked list, quicksort for doubly linked list can be implemented using algorithm specified in cormen, as node has pointer to both next and previous element, but i have no idea for implementing quicksort for linkedlist. I have searched the internet, but can't get anything useful. Any psudocode or suggestion will be very helpful.

Nitish Jain
  • 704
  • 2
  • 10
  • 24
  • 2
    What have you searched for? I tried "doubly linked list quicksort c" and it came up with oodles. Substitute your language of choice. – AMADANON Inc. Jun 10 '14 at 04:28

1 Answers1

0

First implement quicksort on an array using only forward iterators. Here is the partition step. The invariant you maintain is as follows: a[0] is the pivot element We have two iterators (indices) i and j. For 0 <= k < j we have a[k] <= pivot. For j <= k < i we have a[k] >= pivot. Elements for k >= i are unknown. Now if a[i] >= pivot, increment i. If a[i] < pivot, swap a[i] and a[j] and increment both i and j.

When you have that working for an array, "translate" the algorithm to the singly linked list.

user515430
  • 3,341
  • 2
  • 17
  • 13
  • Is this the algorithm you are propsing for parition in c int partition(int a[], int l, int r) {pivot = a[l]; int i, j; i = l; j = l; while (i <= r) { if (a[i] >= pivot) i++; else swap(a[i++], a[j++])} return j;} then i think this will not give correct partition for this example of 6 elements 4 2 3 1 5 0 as finally after partition becomes 2 3 1 0 5 4 .... correct me if i am wrong – Nitish Jain Jun 10 '14 at 08:51
  • The for-loop (while in your case) ends with i = 6 and j = 5. The array is 4 2 3 1 0 5. Now you swap a[0] and a[j-1] and get 0 2 3 1 4 5. After this you do recursion on the sub-arrays 0 2 3 1 and 5. – user515430 Jun 10 '14 at 14:19
  • why have you used this array is 4 2 3 1 0 5, my array was 4 2 3 1 5 0 and how did you swapped a[0] & a[j-1], according to algorithm please explain – Nitish Jain Jun 11 '14 at 05:47
  • The original array is 4 2 3 1 5 0. 4 is the pivot. Until we get to i = 5 no elements are swapped. When i = 5, j = 4. Now as a[5] < pivot we swap a[i] and a[j] and increment i and j, terminating the for-loop. So, when the for-loop terminates we have the array 4 2 3 1 0 5. We then put the pivot element in its right place by swapping 4 and 0 (a[0] and a[j-1]) giving us the array 0 2 3 1 4 5. We are then ready for the recursion. – user515430 Jun 11 '14 at 06:13
  • but a[1], a[2], a[3] all were smaller than pivot, why not they were swapped and j and i will then increase? – Nitish Jain Jun 11 '14 at 09:35
  • Yes, a[1], a[2], a[3] were swapped with themselves and i and j were incremented. – user515430 Jun 11 '14 at 12:02
  • Means, condition you mentioned in the answer should be Now if a[i] > pivot, increment i. If a[i] <= pivot, swap a[i] and a[j] and increment both i and j (i have changed equality sign from first condition to second) or i = l+1, I have tried but algo is not clear to me till now please check my algo i mentioned according to you description in first comment or provide an step by step example – Nitish Jain Jun 11 '14 at 16:48
  • What you do with elements identical to the pivot element, whether you include them in the first group or the second group, is irrelevant. The important thing is the invariant. That the invariant holds after the for-loop ends makes it possible to 1) put the pivot element in its right position and 2) do the recursive calls. – user515430 Jun 11 '14 at 18:04