Quicksort problems

HenriK (136)
Hi, it´s me here. I decided to take a look how quicksorting works. I found a piece of code concerning it and modified it for my own use and now when you look at the code below, you can see it is supposed quicksort with various data types with template functions:

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
 
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;

template<typename T> void Quicksort(T*,int);
template<typename T> void Quicksort(T*,int,int);
template<typename T> T Partition(T*,int,int);

template<typename T>
void Quicksort(T a[], int elements){
    Quicksort(a,0,elements);
}
template<typename T>
void Quicksort(T a[], int l, int r){
	if(l<r){
		T pivot = Partition<T>(a,l,r);
		Quicksort(a,l,pivot-1);
		Quicksort(a,pivot+1,r);
	}
}
template<typename T>
T Partition(T a[], int l, int r){
	int pivot = a[l];
	while(1){
		while(a[l]<pivot) ++l;
		while(a[r]>pivot) --r;
		if(l<r) swap(a[l],a[r]);
		else return r;
	}
}

int main(){
    double array1[]={5.3, 8, 1.5, 3.4};
    Quicksort<double>(array1,0,4);
    for(int i=0; i<4; i++) cout << array1[i] << endl;
    return 0;
}


Now I just don´t understand why I can´t change that value 8 in the main function to decimal number, otherwisely my program crashes. Doesn´t happen with any other element, though.
Must have something to do with the fact that it is the final element of my double array after quicksorting...
Last edited on
HenriK (136)
Never mind, fixed it - it seems to like I forgot to change this...

1
2
3
4
5
6
7
8
9
10
 
template<typename T>
T Partition(T a[], int l, int r){
	int pivot = a[l];
	while(1){
		while(a[l]<pivot) ++l;
		while(a[r]>pivot) --r;
		if(l<r) swap(a[l],a[r]);
		else return r;
	}
}


...to this:

1
2
3
4
5
6
7
8
9
10
 
template<typename T>
T Partition(T a[], int l, int r){
	T pivot = a[l];
	while(1){
		while(a[l]<pivot) ++l;
		while(a[r]>pivot) --r;
		if(l<r) swap(a[l],a[r]);
		else return r;
	}
}


Now I just wasted bit space of the world. Oh well...
Last edited on
ne555 (10692)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
    double array1[]={5.3, 8, 1.5, 3.4};
    Quicksort<double>(array1,0,4); //range [ )
//...

template<typename T>
T Partition(T a[], int l, int r){
	T pivot = a[l];
	while(1){
		while(a[l]<pivot) ++l;
		while(a[r]>pivot) --r;  //range [ ] 
		if(l<r) swap(a[l],a[r]);
		else return r;
	}
}


Test this int array1[]={1, 2, 3 ,2 ,1 ,5 ,2 ,1, 3}; (infinite loop)
1
2
3
 
		while(a[l]<pivot) ++l; //consider what happen with repeated elements 
		while(a[r]>pivot) --r;
//a[l] == pivot and a[r] == pivot
HenriK (136)
Sheesh, you´re right. It creates an infinite loop.

What would you suggest me to do?
ne555 (10692)
Move the pivot "outside the array". Then try to end with [lesser | pivot | greater or equal]
http://en.wikipedia.org/wiki/Quicksort#In-place_version
Topic archived. No new replies allowed.