C++

Forum

 
Help in sorts

rhaegal21 (1)
Write your question here.
I have to write a bucket sort and a merge sort using vector and lists, i think i did it but when i test me it gives me a segmentation fault and i dont know why.
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
 
  /*--------------------------------------------------------------------

 * Actividad de programación: Algoritmos de ordenamiento

 * Fecha: 30-Sep-2015

 * Autor: 

 *           A01154927 Luis Santillan

 *--------------------------------------------------------------------*/
 
#ifndef SORTS_H_
#define SORTS_H_

#include "exception.h"
#include <vector>
#include <list>

template <class T>
class Sorts {
public:
	std::vector<T> bubbleSort(const std::vector<T>&);

	std::vector<T> bucketSort(const std::vector<T>&);
	std::list<T>   mergeList(const std::list<T>&, const std::list<T>&);
};

template <class T>
std::vector<T> Sorts<T>::bubbleSort(const std::vector<T> &source) {
	std::vector<T> v = source;
	int i, j; 
	for (i = 0; i < v.size()-1; i++){       
        for (j = 0; j < v.size()-i-1; j++){  
           if (v[j] > v[j+1]){
        	T aux = v[j];
			v[j] = v[j+1];
			v[j+1] = aux;	
           }
        }
	}   
	return v;
}

template <class T>
std::vector<T> Sorts<T>::bucketSort(const std::vector<T> &source) {
	std::vector<T> v;
	std::vector<T> b0, b1, b2, b3, b4, b5, b6, b7, b8, b9;
	
	for(int i = 0; i < v.size(); i++){
		if(v[i] >= 0 && v[i] <= 9){
			b0.push_back(v[i]);
		} else if(v[i] >= 10 && v[i] <= 19){
			b1.push_back(v[i]);
		} else if(v[i] >= 20 && v[i] <= 29){
			b2.push_back(v[i]);
		} else if(v[i] >= 30 && v[i] <= 39){
			b3.push_back(v[i]);
		} else if(v[i] >= 40 && v[i] <= 49){
			b4.push_back(v[i]);
		} else if(v[i] >= 50 && v[i] <= 59){
			b5.push_back(v[i]);
		} else if(v[i] >= 60 && v[i] <= 69){
			b6.push_back(v[i]);
		} else if(v[i] >= 70 && v[i] <= 79){
			b7.push_back(v[i]);
		} else if(v[i] >= 80 && v[i] <= 89){
			b8.push_back(v[i]);
		} else if(v[i] >= 90 && v[i] <= 99){
			b9.push_back(v[i]);
		}
	}
	
	b0 = bubbleSort(b0);
	b1 = bubbleSort(b1);
	b2 = bubbleSort(b2);
	b3 = bubbleSort(b3);
	b4 = bubbleSort(b4);
	b5 = bubbleSort(b5);
	b6 = bubbleSort(b6);
	b7 = bubbleSort(b7);
	b8 = bubbleSort(b8);
	b9 = bubbleSort(b9);
	
	v.clear();
	
	for(int i = 0; i < b0.size(); i++){
		v.push_back(b0[i]);
	}
	for(int i = 0; i < b1.size(); i++){
		v.push_back(b1[i]);
	}
	for(int i = 0; i < b2.size(); i++){
		v.push_back(b2[i]);
	}
	for(int i = 0; i < b3.size(); i++){
		v.push_back(b3[i]);
	}
	for(int i = 0; i < b4.size(); i++){
		v.push_back(b4[i]);
	}
	for(int i = 0; i < b5.size(); i++){
		v.push_back(b5[i]);
	}
	for(int i = 0; i < b6.size(); i++){
		v.push_back(b6[i]);
	}
	for(int i = 0; i < b7.size(); i++){
		v.push_back(b7[i]);
	}
	for(int i = 0; i < b8.size(); i++){
		v.push_back(b8[i]);
	}
	for(int i = 0; i < b9.size(); i++){
		v.push_back(b9[i]);
	}
	

	return v;
}

template <class T>
std::list<T> Sorts<T>::mergeList(const std::list<T> &lst1, const std::list<T> &lst2) {
	std::list<T> result;
	typename std::list<T>::const_iterator itr1 = lst1.begin(), itr2 = lst2.begin(); 
	typename std::list<T>::iterator itr3 = result.begin();
	
	while(!lst1.empty() && !lst2.empty()){
		if(*itr1 < *itr2){
			*itr3 = *itr1;
			itr1++;
			itr3++;
		}else{
			*itr3 = *itr2;
			itr2++;
			itr3++;
		}
	}
	if(!lst1.empty()){
		while(!lst2.empty()){
			*itr3 = *itr2;
			itr2++;
			itr3++;
		}
	}else{
		while(!lst1.empty()){
			*itr3 = *itr1;
			itr1++;
			itr3++;
		}	
	}
	return result;
}

#endif /* SORTS_H_ */
Peter87 (11234)
Note that v.size() returns an unsigned integer type so if you subtract so that the result goes below zero the value will wrap around and become a very large value because unsigned integers can't store negative values.
jonnin (11436)
bucket sort for values of 0 to 100:
unsigned int bucket[101];
for(all the data)
bucket[value]++

then when you recover the data,
for(all the buckets)
for(0 to bucket value) //say bucket value is 10 and you had 23 copies of the value 10
process(bucket ID) //eg, print 10, 23 times. the bucket array index is 10, and its value is 23

see?


there may be another version of it; I have seen several algorithms called 'bucket sort' but this is the one I recommend as is it is O(N) which is as fast as it gets to sort data. Note that you must know the value range of the data and it must be integer or integer like data to use this.

your version, with multiple values per bucket, is much more complex -- its slower and really has no niche where it is the best choice. you can magic the index to support negative values, eg
int buckets[202]; //adjust index into this to be value+100, so -100 becomes [0], -99 is 1, and so on. but the range still has to be known and continuous. a cute way to do this is to say int* bp = &buckets[101]; c++ will let you use bp[-100] so the basic logic is simplified with the pointer. You would use vectors here of course, I am just showing you the algorithm with arrays for simplicity
Last edited on
saeidsj (23)
Dear friend,
Your Bucket sort is not bucket sort because you used your Bubbelsort function in it and we do not have that in Bucket sort.
Also your merg sort is false because will not sort the lists it just copy two lists after each other for example the forst list is [5,4,3,2,1] and second one is [6,7,9,8] the result would be [5,4,3,2,1,6,7,9,8]!!!!!
Topic archived. No new replies allowed.