C++

Forum

 
Doubly Linked List Quick Sort

Jakubaz (24)
Hello. I have problem with my quick sort algorithm in dubly linked list.
Exhatly is 4 condition i dont know how to implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
  ListItem* pivot, * i, * j;
	i = l; 
	j = r;
	pivot = Pivot(L, l, r); // middle of list 
	
	do 
	{
		while (i->Value < pivot->Value) i = i->Next;
		while (j->Value > pivot->Value) j = j->Prev;
		if (i != j) // 1)
		{
			Exchange(i, j);
			i = i->Next;
			j = j->Prev;
		}
		
	} while (i != j); //2)
	if (l < j) // 3)
	     QuickSort(L, l, j);
	if (i < r) // 4)
	     QuickSort(L, i, r);


// how it should look. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
void QuickSort(int a[], const int l, const int r)
{
	int i = l;
	int j = r;
	int pivot = a[(l + r) / 2];
	do
	{
		while (a[i] < pivot) i += 1;
		while (pivot < a[j]) j -= 1;
		if (i <= j)
		{
			Exchange(a[i], a[j]);
			i += 1;
			j -= 1;
		}
	} while (i <= j);
	if (l < j)
		QuickSort(a, l, j);
	if (i < r)
		QuickSort(a, i, r);
}

Last edited on
keskiverto (10365)
I think you have trouble already on condition 2.

Lets test with {42,1,7}:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
i-> 42
j-> 7
pivot-> 1
42<1 is false
7>1 is true => j->1
1>1 is false
Exchange( i->42, j->1 ) =>
{1,42,7}, i->1, j->42
update pointers:
i-> 42
j-> 1
=>
still i != j, but j->Next == i

Unstoppable.

A problem with cond 3 and cond 4 is that you cannot use < with those pointers. Each node is probably allocated separately and there is no way to know where. Nothing predictable.

!= and == are the only possible relations.

The question is, can the j slip into l->Prev and beyond. (Same with i and r.)
icy1 (596)
Hi Jakubaz,
Do you have a small working demo (mostly for initializing and printing your doubly Linked List)?

I did a bit of reading on the wikipedia article for QuickSort; not sure which implementation you used, though it seems to be working. Perhaps you'd have an easier time using the Hoare implementation, which doesn't involve finding the middle. Your doubly-linked list manager has easy access to front and back, right?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include <iostream>
#include <vector>
using namespace std;

// Hoare implementation 
// https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
int Partition(vector<int>& v, int lo, int hi)
{
    int pivot = v[lo];
    int i = lo-1;
    int j = hi+1;
    while (true)
    {
        do { ++i; } while (v[i] < pivot);
        do { --j; } while (v[j] > pivot);
        
        if (i >= j)
            return j;
        swap(v[i], v[j]);
    }
}

void QuickSort(vector<int>& v, int lo, int hi)
{
    if (lo < hi)
    {
        int p = Partition(v, lo, hi);
        QuickSort(v, lo, p);
        QuickSort(v, p+1, hi);
    }
}

void Show(const vector<int>& v)
{
    for (auto& n : v)
        cout << n << " ";
    cout << endl;
}
 

int main()
{
    vector<int> v = {10, 7, 8, 9, 1, 5};
    cout << "\nVector:" << endl;
    Show(v);
    cout << "Sorted Vector:" << endl;
    QuickSort(v, 0, v.size()-1);
    Show(v);
    return 0;
}


Jimmy Vaporizer Pen (1)
great share!
icy1 (596)
Ok, I think I have an implementation for LinkedList now ;D. The components you need are 

Size()
At(index i) or [i]
Swap(Node* a, Node* b)

Then it's basically just like the vector implementation. Of course, indexing on a linked list is horribly slow, since it has to start from the beginning (I suppose it could be smart and start from the end sometimes if it knows its own size?!). Can run it at https://repl.it/repls/DentalGainsboroHexagon

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
 
#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

struct Node
{
    Node(int i) : value(i)
    {
    }
    
    string Verbose()
    {
        ostringstream oss;
        oss << "[" << value << " ";
        if (prev)
            oss << "prev"<<prev->value << " ";
        if (next)
            oss << "next"<<next->value;
        oss << "] ";
        return oss.str();
    }
    
    int value;
    Node* prev;
    Node* next;
};

class NodeManager
{
public:
    NodeManager() : size_(0)
    {
    }

    // Deallocate memory
    ~NodeManager()
    {
        CleanUp();
    }

    void Append(int i)
    {
        Node* n = new Node(i);
        if (!head_)
        {
            head_ = n;
            tail_ = n;
        }
        else
        {
            tail_->next = n;
            n->prev = tail_;
            tail_ = n;
        }
        size_ += 1;
    }
    
    size_t Size()
    {
        return size_;
    }
    
    // Swaps the values of two nodes
    void Swap(Node* a, Node* b)
    {
        if (!a || !b)
        {
            cout <<"Node Swap Error -- a or b not valid!\n";
            return;
        }
        
        int tmp = a->value;
        a->value = b->value;
        b->value = tmp;
    }
    void Swap(int i, int j)
    {
        Node* a = At(i);
        Node* b = At(j);
        Swap(a,b);
    }
    
    // Indexing takes up to O(n) time, sadly
    Node* At(int index)
    {
        Node* n = head_;
        int i=0;
        while(n)
        {
            if (i==index)
                return n;
            n = n->next;
            ++i;
        }
        throw out_of_range("Index "+to_string(index)+" not found in this NodeManager");
    }
    
    Node* operator[](int index)
    {
        return At(index);
    }
    
    void Show(bool verbose=false)
    {
        if (!head_)
        {
            cout << "List is empty.\n";
        }
        else
        {
            Node* n = head_;
            while(n)
            {
                if (verbose)
                    cout << n->Verbose();
                else
                    cout << n->value << " ";
                n = n->next;
            }
            cout << endl;
        }
    }
    
    // Delete all nodes
    void CleanUp()
    {
        Node* n = head_;
        Node* tmp;
        while(n)
        {
            tmp = n->next;
            delete n; 
            n = tmp;
        }
        head_ = nullptr;
        tail_ = nullptr;
        size_ = 0;
    }
    
private:
    Node* head_;
    Node* tail_;
    size_t size_;
};

int Partition(NodeManager* n, int lo, int hi)
{
    int pivot = n->At(lo)->value;
    int i = lo-1;
    int j = hi+1;
    while (true)
    {
        do { ++i; } while (n->At(i)->value < pivot);
        do { --j; } while (n->At(j)->value > pivot);
        
        if (i >= j)
            return j;
        n->Swap(i,j);
    }
}

void QuickSort(NodeManager* n, int lo, int hi)
{
    if (lo < hi)
    {
        int p = Partition(n, lo, hi);
        QuickSort(n, lo, p);
        QuickSort(n, p+1, hi);
    }
}
 

int main()
{
    NodeManager* nm = new NodeManager;
    nm->Append(10);
    nm->Append(7);
    nm->Append(8);
    nm->Append(9);
    nm->Append(1);
    nm->Append(5);
    
    cout << "\nLinked List:" << endl;
    nm->Show();
    nm->Show(true);
    cout << "\nSorted Linked List:" << endl;
    QuickSort(nm, 0, nm->Size()-1);
    nm->Show();
    nm->Show(true);
    
    delete nm;
    
    return 0;
}


Output, includes a verbose show to see prev and next values:
Linked List:
10 7 8 9 1 5 
[10 next7] [7 prev10 next8] [8 prev7 next9] [9 prev8 next1] [1 prev9 next5] [5 prev1 ] 

Sorted Linked List:
1 5 7 8 9 10 
[1 next5] [5 prev1 next7] [7 prev5 next8] [8 prev7 next9] [9 prev8 next10] [10 prev9 ]
icy1 (596)
Changes:
- changed Swap method to use std::swap
- hopefully improved upon indexing to start from the back if requested index is large
- bigger example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
 
#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

struct Node
{
    Node(int i) : value(i)
    {
    }
    
    string Verbose()
    {
        ostringstream oss;
        oss << "[" << value << " ";
        if (prev)
            oss << "prev"<<prev->value << " ";
        if (next)
            oss << "next"<<next->value;
        oss << "] ";
        return oss.str();
    }
    
    int value;
    Node* prev;
    Node* next;
};

class NodeManager
{
public:
    NodeManager() : size_(0)
    {
    }

    // Deallocate memory
    ~NodeManager()
    {
        CleanUp();
    }

    void Append(int i)
    {
        Node* n = new Node(i);
        if (!head_)
        {
            head_ = n;
            tail_ = n;
        }
        else
        {
            tail_->next = n;
            n->prev = tail_;
            tail_ = n;
        }
        size_ += 1;
    }
    
    size_t Size()
    {
        return size_;
    }
    
    // Swaps the values of two nodes
    void Swap(Node* a, Node* b)
    {
        if (!a || !b)
        {
            cout <<"Swap Error -- node(s) invalid!\n";
            return;
        }
        swap(a->value, b->value);
    }
    void Swap(int i, int j)
    {
        Swap(At(i), At(j));
    }
    
    // Hopefully now indexing will take approx O(n/2) time
    Node* At(int index)
    {
        if (!size_)
            throw out_of_range("List is empty.");
            
        if (index<0 || index>=size_)
            throw out_of_range("Index "+to_string(index)+" not in range.");
        
        if (index == size_-1)
            return tail_;

        if (index == 0)
            return head_;

        if (index < size_/2)
        {
            Node* n = head_;
            int i=0;
            while(n)
            {
                if (i==index)
                    return n;
                n = n->next;
                ++i;
            }
        }
        else
        {
            Node* n = tail_;
            int i = size_-1;
            while(n)
            {
                if (i==index)
                    return n;
                n = n->prev;
                --i;
            }
        }
        
        throw out_of_range("Index "+to_string(index)+" not found.");
    }
    
    Node* operator[](int index)
    {
        return At(index);
    }
    
    void Show(bool verbose=false)
    {
        if (!head_)
        {
            cout << "List is empty.\n";
        }
        else
        {
            Node* n = head_;
            while(n)
            {
                if (verbose)
                    cout << n->Verbose();
                else
                    cout << n->value << " ";
                n = n->next;
            }
            cout << endl;
        }
    }
    
    // Delete all nodes
    void CleanUp()
    {
        Node* n = head_;
        Node* tmp;
        while(n)
        {
            tmp = n->next;
            delete n; 
            n = tmp;
        }
        head_ = nullptr;
        tail_ = nullptr;
        size_ = 0;
    }
    
private:
    Node* head_;
    Node* tail_;
    size_t size_;
};

int Partition(NodeManager* n, int lo, int hi)
{
    int pivot = n->At(lo)->value;
    int i = lo-1;
    int j = hi+1;
    while (true)
    {
        do { ++i; } while (n->At(i)->value < pivot);
        do { --j; } while (n->At(j)->value > pivot);
        
        if (i >= j)
            return j;
        n->Swap(i,j);
    }
}

void QuickSort(NodeManager* n, int lo, int hi)
{
    if (lo < hi)
    {
        int p = Partition(n, lo, hi);
        QuickSort(n, lo, p);
        QuickSort(n, p+1, hi);
    }
}

int main()
{
    NodeManager* nm = new NodeManager;
    
    vector<int> vals = {13306,  23084,  23327, 21418,  13354,  6829,
    17939,  19656,  13584,  10141,  2377,  22761,  3669,  618,  1935,
    8967,  9718,  7294,  4718,  16237,  3661,  17529, 4106,  21536,
    2286,  5217,  19754,  16726,  16413,  19210,  12115, 10344, 5410,
    9972,  23314,  9380,  3831,  22282,  15688,  20690,  23364,  10278,
    14923,  23509,  13544, 15967, 13656, 2187, 8226, 22703, 4776, 4164,
    5304, 14891, 730, 2051, 21096, 329, 13786, 13907, 12569, 19401, 20654,
    12955, 19029, 18727, 2024, 18728, 1041, 20753, 4230, 9591, 13731, 13693,
    1744, 2039, 15359, 9206, 21659, 18256, 5006, 9624, 14009, 19526, 10867,
    3523, 4866, 21726, 4891, 20173, 6039, 13450, 19208, 9866, 5126, 5131,
    4997, 10382, 16820, 11068};
    
    for (auto& v : vals)
        nm->Append(v);
    
    cout << "\nLinked List:" << endl;
    nm->Show();

    cout << "\nSorted Linked List:" << endl;
    QuickSort(nm, 0, nm->Size()-1);
    nm->Show();

    delete nm;
    return 0;
}


Output (added newlines cause this site doesn't word-wrap):
Linked List:
13306 23084 23327 21418 13354 6829 17939 19656 13584 10141 2377 22761 3669
 618 1935 8967 9718 7294 4718 16237 3661 17529 4106 21536 2286 5217 19754
 16726 16413 19210 12115 10344 5410 9972 23314 9380 3831 22282 15688 20690 
23364 10278 14923 23509 13544 15967 13656 2187 8226 22703 4776 4164 5304
 14891 730 2051 21096 329 13786 13907 12569 19401 20654 12955 19029 18727
 2024 18728 1041 20753 4230 9591 13731 13693 1744 2039 15359 9206 21659
 18256 5006 9624 14009 19526 10867 3523 4866 21726 4891 20173 6039 13450
 19208 9866 5126 5131 4997 10382 16820 11068 

Sorted Linked List:
329 618 730 1041 1744 1935 2024 2039 2051 2187 2286 2377 3523 3661 3669
 3831 4106 4164 4230 4718 4776 4866 4891 4997 5006 5126 5131 5217 5304
 5410 6039 6829 7294 8226 8967 9206 9380 9591 9624 9718 9866 9972 10141
 10278 10344 10382 10867 11068 12115 12569 12955 13306 13354 13450 13544
 13584 13656 13693 13731 13786 13907 14009 14891 14923 15359 15688 15967
 16237 16413 16726 16820 17529 17939 18256 18727 18728 19029 19208 19210
 19401 19526 19656 19754 20173 20654 20690 20753 21096 21418 21536 21659
 21726 22282 22703 22761 23084 23314 23327 23364 23509
Topic archived. No new replies allowed.