sorting vector problem

closed account (zwA4jE8b)
Hey guys,
I am new to using vectors and am having trouble using my quicksort to sort a vector.

The quicksort I have works perfect on arrays.

My problem is that I do not know how to pass a vector as the parameter.

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
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

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

template <class dType>
void quicksort(dType temp[], int l, int r)
{
	int j, k;
	if (l < r)
	{
		j = l;
		k = r + 1;
		do
		{
			do{j++;} while (!(temp[j] > temp[l]));
			do{k--;} while (!(temp[k] < temp[l]));
			if (j < k) 
			{
				swapitem(temp[j], temp[k]);
			}
		}
		while (k > j);
		swapitem(temp[l], temp[k]);
		quicksort(temp, l, k - 1);
		quicksort(temp, k + 1, r);
	}
}

int main()
{
	ifstream inf("input.dat");
	ofstream outf("output.dat");
	vector<int> V;
	vector<int>::iterator iter;
	int i;

	while (!inf.eof())
	{
		inf >> i;
		V.push_back(i);
	}

	for (iter = V.begin(); iter != V.end(); ++iter)	{outf << *iter << " ";}
	outf << endl;

	quicksort(V, 0, V.size()-1);

	for (iter = V.begin(); iter != V.end(); ++iter)	{outf << *iter << " ";}

	return 0;
}


line 58 is where I am trying to pass it.

And yes, I know the stl contains a sort function.

Thank you,
Mike
Last edited on
closed account (zwA4jE8b)
I took off the [] in the parameter list and it now accepts the vector, but it does not sort properly.

void quicksort(dType temp, int l, int r)


35 25 55 65 15 105 28 75 95 5  //original values
15 5 25 35 55 65 28 75 95 105 //values after sort is called


I tried with bubble sort also, I get the same results.

also tried

void quicksort(dType &temp, int l, int r)

perhaps the swap function is incorrect to handle vectors?
Last edited on
jsmith (5804)
If you want your quicksort to work on arrays and vectors, you have two choices:

1
2
3
4
5
6
7
8
9
 
template< typename T >
void quicksort( T* first, T* last ) // last = 1 past last element to sort, just as in all stl algorithms
{
}

// and with vectors, you call it like this:
std::vector< int > v; 
if( !v.empty() )
    quicksort( &v[ 0 ], &v[ v.size() - 1 ] + 1 )


or:

1
2
3
4
5
6
7
8
9
10
11
 
template< typename RandomAccessIter >
void quicksort( RandomAccessIter first, RandomAccessIter last )
{
}

// and call it like this:
int array[ 10 ];
std::vector< int > v;

quicksort( array, array + 10 );
quicksort( v.begin(), v.end() );


This will solve your problems.
closed account (zwA4jE8b)
I see what you are saying but my version of quicksort takes 3 parameters. the object, the left value and the right value.

I have seen versions online that take just the two parameters.

Is it possible to make it work with the version of the sort I have written?

Perhaps bubble sort would be easier for me to start with.

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
 
template <class dType>
void swapitem(dType& one, dType& two)
{
	dType d;
	d = one;
	one = two;
	two = d;
}

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++;
	}
}


 
 
bubblesort(V, V.size());


I did what you said and instead of using size - 1 i just used size and the bubble sort now works!

Edit: Sorry, it is early here, I don't know why i was passing size - 1 to bubble sort in the first place.


Last edited on
closed account (zwA4jE8b)
In my version the left and right values are indexes.

 
 
quicksort(V, 0, V.size());


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
template <class dType>
void quicksort(dType &temp, int l, int r)
{
	int j, k;
	if (l < r)
	{
		j = l;
		k = r + 1;
		do
		{
			do{j++;} while (!(temp[j] > temp[l]));
			do{k--;} while (!(temp[k] < temp[l]));
			if (j < k) 
			{
				swapitem(temp[j], temp[k]);
			}
		}
		while (k > j);
		swapitem(temp[l], temp[k]);
		quicksort(temp, l, (k - 1));
		quicksort(temp, (k + 1), r);
	}
}



when I run this, I get an error, vector subscript out of range. also happens when I run it with size() -1

but I cannot find where.
Last edited on
ne555 (10692)
1
2
3
4
 
j = l;
do{
  j++;
} while (!(temp[j] > temp[l])); //j starts at l+1
So if temp[l] is the minimum element of the array, that will be out of bounds.
Veltas (450)
Just want to shout out;
does anyone else like the name 'Bubble Sort' here?

Always cheers me up...
closed account (zwA4jE8b)
do you know why then this works with arrays and not vectors?

like I said, i am new to vectors but they seem similar to arrays in that you can use the subscripts.

the quicksort works with 'arrayname[10]' but not a vector of length 10.

I guess my main area of confusion comes from the fact that my bubblesort, selectsort, and shell sort work with both arrays and vectors. but I just cannot get quicksort to work.

maybe i will just have to do what jsmith said and use the version of quicksort that takes 2 parameters.

No problem, just practicing.
Last edited on
ne555 (10692)
Undefined behaviour is undefined.
You just were unlucky with the array.

Fix those do while and it should work.

Edit:
You've got the out of bounds with the array too, it just didn't crash.
When it reached 
1
2
3
4
 
if (j < k) 
			{
				swapitem(temp[j], temp[k]);
			}
the condition was false, so you didn't see the error.
If you are worried about out of bounds, replace the subscripts with vector::at. That will raise an exception in case of a bad index.
Last edited on
closed account (zwA4jE8b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
template <class dType>
void quicksort(dType &temp, int l, int r)
{
	int j, k;
	if (l < r)
	{
		j = l;
		k = r + 1;
		do
		{
			do{j++;} while ((temp[j] < temp[l]));
			do{k--;} while ((temp[k] > temp[l]));
			if (j < k) 
			{
				swapitem(temp[j], temp[k]);
			}
		}
		while (k > j);
		swapitem(temp[l], temp[k]);
		quicksort(temp, l, k - 1);
		quicksort(temp, k + 1, r);
	}
}


I changed it back to this and it works on both static and dynamic arrays. still not working with vectors.

I have noticed that the version i am trying to use might be an old version because it uses the temp[l] as the pivot point where as most I am seeing online use temp[(left + right) /2] as the pivot point. I am having trouble making my version like the newer version.

this is a slightly modified version of what i found online. and this works for vectors and arrays.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
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);
}
Last edited on
Topic archived. No new replies allowed.