myqsort.c


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

#include "myqsort.h"
#include <stdlib.h>
int my_partition(display *A, int p, int r){
	int ri = p + rand() % (r - p);
	display tmp = A[ri];
	A[ri] = A[r];
	A[r] = tmp;

	display pivot = A[r];
	int pos_pivot = p;
	
	for(int i=p; i < r; ++i){
		if(A[i].p.z < pivot.p.z){
			display aux = A[i];
			A[i] = A[pos_pivot];
			A[pos_pivot] = aux;
			pos_pivot++;
		}
	}

	display aux = A[pos_pivot];
	A[pos_pivot] = pivot;
	A[r] = aux;

	return pos_pivot;
}

void my_qsort(display *A, int p, int r){
	if(p < r){
		int q = my_partition(A, p, r);
		my_qsort(A, p, q-1);
		my_qsort(A, q+1, r);
	}
}