C++

Forum

 
Why is the time complexity of this quicksort so bad?

drawinfinity (8)
For a homework assignment I had to use a certain singly linked list implementation and create a quicksort for it. The main program imports a list from a file. The classes are templated but realistically we are only testing with integers.

The original interface for templated class list is:

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
 
  template <class List_entry>
class List {
public:
//  Specifications for the methods of the list ADT go here.
   List();
   int size() const;
   bool full() const;
   bool empty() const;
   void clear();
   void traverse(void (*visit)(List_entry &));
   Error_code retrieve(int position, List_entry &x) const;
   Error_code replace(int position, const List_entry &x);
   Error_code remove(int position, List_entry &x);
   Error_code insert(int position, const List_entry &x);

   void print() const; // Method to print out the list

//  The following methods replace compiler-generated defaults.
   ~List();
   List(const List<List_entry> &copy);
   List<List_entry> operator =(const List<List_entry> &copy);

protected:
//  Data members for the linked list implementation now follow.
   int count;
   Node<List_entry> *head;

//  The following auxiliary function is used to locate list positions
   Node<List_entry>*  set_position(int position) const;
};

The error_codes are an enumerated type.

The derived class Sortable_list, including my implementation of quicksort, is as follows:

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
 
template <class Record>
class Sortable_list:public List<Record> {
public:
   void quick_sort();
protected: 
   //  Add prototypes for auxiliary functions here
	void recursive_quick_sort(Sortable_list<Record> &sublist);
	void partition(Sortable_list<Record> &low, Sortable_list<Record> &high, Record &pivot, Sortable_list<Record> &sublist);
	void combine(Sortable_list<Record> &low, Sortable_list<Record> &high, Record &pivot, Sortable_list &sublist);
};


template <class Record>
void Sortable_list<Record>::quick_sort()
/*
Post: The entries of the Sortable_list have been rearranged so that
      the keys in all the entries are sorted into nondecreasing order.
*/
{
	Sortable_list<Record> sorting_list;
	for (int i = 0; i < this->count; i++) {
		Record p;
		retrieve(i, p);
		sorting_list.insert(i, p);
	}
	recursive_quick_sort(sorting_list);
	for (int i = 0; i < this->count; i++){
		Record r;
		sorting_list.retrieve(i, r);
		this->replace(i, r);
	}
}

template <class Record>
/*
	recursive_quick_sort partitions the list into a low list and a high list and then recursively calls itself to sort each of those lists. 
	After the recursive function returns it combines the low list with the pivot and high list.
*/
void Sortable_list<Record>::recursive_quick_sort(Sortable_list<Record> &sublist){
	Sortable_list<Record> lowList;
	Sortable_list<Record> highList;
	if (sublist.size() <= 1) return;
	Record pivot;
	partition(lowList, highList, pivot, sublist);
	recursive_quick_sort(lowList);
	recursive_quick_sort(highList);
	combine(lowList, highList, pivot, sublist);
	return;
}

template <class Record>
/*
	Partition creates two lists, one of which contains all keys smaller than the pivot and the other all keys that are greater than the pivot. 
	This partition implementation chooses the first element as the pivot.
*/
void Sortable_list<Record>::partition(Sortable_list<Record> &low, Sortable_list<Record> &high, Record &pivot, Sortable_list<Record> &sublist){
	int low_cursor = 0;
	int high_cursor = 0;
	int c = sublist.size();
	sublist.remove(0, pivot);
	Record current;
	for (int i = 1; i < c; i++) {
		sublist.remove(0, current);
		if (current < pivot) low.insert(low_cursor++, current);
		if (current >= pivot) high.insert(high_cursor++, current);
	}
}

template <class Record>
/*Combine takes two lists and a pivot and combines them into one list*/
void Sortable_list<Record>::combine(Sortable_list<Record> &low, Sortable_list<Record> &high, Record &pivot, Sortable_list<Record> &sublist){
	sublist.clear();
	int list_cursor = 0;
	for (int i = 0; i < low.size(); i++){
		Record r;
		low.retrieve(i, r);
		sublist.insert(list_cursor++, r);
	}
	sublist.insert(list_cursor++, pivot);
	for (int i = 0; i < high.size(); i++){
		Record r;
		high.retrieve(i, r);
		sublist.insert(list_cursor++, r);
	}
}


This code does work. What I don't understand is why it is so incredibly slow with large quantities of numbers. My only thought is that it is because in the partition function (as per instructions from the professor) we are creating two entirely new lists instead of just modifying our own.

Is that the reason or am I just doing something dumb?
Lachlan Easton (699)
There's a lot of places that could be slowing it down, the only way to know for sure it to use a profiler to see what functions are taking the most time. But to throw a guess:
1
2
3
4
 
Error_code retrieve(int position, List_entry &x) const;
Error_code replace(int position, const List_entry &x);
Error_code remove(int position, List_entry &x);
Error_code insert(int position, const List_entry &x);
All of these functions look like they'll have to traverse the whole list to find the position they're looking for, lists traversals are notoriously slow and these functions are called a lot. Usually in a linked list data structure you would also keep track of the tail (not just the head) so you can do push_back (insert at the end) in constant time.

Last edited on
Topic archived. No new replies allowed.