Sorting Lists Faster

airerdem (27)
Hi,

I have following code but it is very slow during sorting. 


1
2
3
4
5
6
7
8
 
list<double> fitness;

for(i=0;i<250;i++)
{
fitness.push_back(Random Number);
}

fitness.sort();


Is there any other method about list sorting ?

Thanks in advance
m4ster r0shi (2201)
airerdem wrote:
Is there any other method about list sorting ?

No.

I'm pretty sure it's not the sorting that slows you down.
On my machine the above takes less than a millisecond.
airerdem (27)
Actually I launched the performance wizard in visual studio 2010 it showed bigger inclusive sample ratio in sorting lines. Is that mean this line slows down the program ?
closed account (zwA4jE8b)
here are some sorts....

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
 
//Michael Ervin - Sorting functions

#ifndef H_SORTFUNCS
#define H_SORTFUNCS

template <class dType>
void swapitem(dType& one, dType& two)
{
	dType d;
	d = one;
	one = two;
	two = d;
}

//Works with Arrays and Vectors
template <class dType>
void bubblesort(dType &temp, int n)
{
	bool sorted = false;
	int i = 0, j = 1;
	
	while (!sorted)
	{
		sorted = true;
		for (i = 0; i < n - j; i++)
		{
			if (temp[i] > temp[i + 1])
			{
				swapitem(temp[i], temp[i + 1]);
				sorted = false;
			}
		}
		j++;
	}
}

//Works with Arrays and Vectors
template <class dType>
void selectsort(dType &temp, int n)
{
	int j = 0, k = 0, small;

	if (n > 1)
		for (k = 0; k < n - 1; k++)
		{
			small = k;
			for (j = k + 1; j < n; j++)
				if (temp[j] < temp[small]) small = j;
			if (k != small)	swapitem(temp[k], temp[small]);
		}
}

//Works with Arrays - Change datatype of save to work with vectors
template <class dType>
void insertionsort(dType &temp, int n)
{
	int j = 0, k = 0;
	dType save;

	for (k = n - 1; k >= 0; k--)
	{
		j = k + 1;
		save = temp[k];
		temp[n] = save;
		while (save > temp[j])
		{
			temp[j - 1] = temp[j];
			j++;
		}
		temp[j - 1] = save;
	}
}

//Works with Arrays and Vectors
template <class dType>
void quicksort(dType &temp, int left, int right) {

	int i = left, j = right;
	int pivot = temp[(left + right) / 2];
	while (i <= j) 
	{
		while (temp[i] < pivot)i++;
		while (temp[j] > pivot)j--;
        if (i <= j) 
		{
			swapitem(temp[i], temp[j]);
			i++;
			j--;
		}
	}
	if (left < j)quicksort(temp, left, j);
	if (i < right)quicksort(temp, i, right);
}

//Works with Arrays and Vectors
template <class dType>
void shellsort(dType &temp, int n)
{
	bool swap = false;
	int i, gap;

	gap = n;

	while (gap >= 1)
	{
		if (swap == false)
			gap = gap / 2;
		swap = false;
		for (i = 0; i < (n - gap); i++)
		{
			if (temp[i] > temp[i + gap])
			{
				swapitem(temp[i], temp[i + gap]);
				swap = true;
			}
		}
	}
}
#endif


quicksort is often one of the fastest sorts, but depends on what your sorting. large data objects can be sorted faster with selectsort because of less moves.
Last edited on
closed account (S6k9GNh0)
Look, it doesn't matter. You can use a bubble sort (or other poor algorithms) and it shouldn't make a difference, there simply isn't enough elements in that list to matter.

What your std::list provides is probably better than what you can hand make. Even if it isn't, I would still suggest you use the interface given by list in order to implement new algorithms.

EDIT: At worst, that list with bubblesort will iterate through the entire array about 250*249 (=62 250) times. That's still not enough to actually matter.
Last edited on
closed account (zwA4jE8b)
Just posting some other methods, didn't mean to offend you.
jsmith (5804)
None of them will work anyway since they all want arrays passed to them.

Some sorts will perform worse than others on a std::list<> due to the fact that std::list<> does not provide random access iterators. Bubble sort is probably one of the better sorts for a std::list<>.
closed account (zwA4jE8b)
I have used them with vectors
jsmith (5804)
Sorry, true, anything that supports operator[] would work.
m4ster r0shi (2201)
FYI, this is also being discussed here -> http://www.daniweb.com/software-development/cpp/threads/370607
ashishkumar (46)
(i) Sorting algorithms for numbers suits best if the numbers are allocated contiguous memory space. First that should be ensured. I am not sure if list data structure supports that. In case you use a std::vector, it would be better. Even a normal array storage is also better.
(ii) There are different data structures ( such as a binary tree ), where you can ensure that the numbers are inserted in such a way so that a particular traversal gives you sorted output. No need to sort it at all.
Topic archived. No new replies allowed.