Debian Codegraph @

SYMPHONY/Applications/VRP/src/Heuristics/qsort.c

raw
1 /*===========================================================================*/
2 /* */
3 /* This file is part of a demonstration application for use with the */
4 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
5 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */
6 /* */
7 /* This application was developed by Ted Ralphs ([email protected]) */
8 /* This file was modified by Ali Pilatin January, 2005 ([email protected]) */
9 /* */
10 /* (c) Copyright 2000-2005 Ted Ralphs. All Rights Reserved. */
11 /* */
12 /* This software is licensed under the Eclipse Public License. Please see */
13 /* accompanying file for terms. */
14 /* */
15 /*===========================================================================*/
16
17 #include "qsort.h"
18
19 void exchange(sweep_data *data, int i, int j)
20 {
21
22 sweep_data temp;
23
24 temp=data[i];
25 data[i]=data[j];
26 data[j]=temp;
27 }
28
29 /*===========================================================================*/
30
31 int partition(sweep_data *data, int len)
32 {
33
34 int i=0, j, pivot;
35 float middle;
36
37 j=len-1;
38 /*pivot=random() % len;*/
39 pivot=0;
40 middle=data[pivot].angle;
41
42 exchange(data, pivot, j);
43
44 while (i<j){
45 while ((i<j) && (data[i].angle<=middle))
46 i++;
47 while ((i<j) && (data[j].angle>=middle))
48 j--;
49 if (i<j)
50 exchange(data, i, j);
51 }
52 if (i!=len-1)
53 exchange(data, i, len-1);
54
55 return(i);
56 }
57
58 /*===========================================================================*/
59
60 void quicksort(sweep_data *data, int len)
61 {
62
63 int pivot;
64
65 pivot=partition(data, len);
66
67 if (pivot>=2)
68 quicksort(data, pivot);
69 if (pivot <= len - 3)
70 quicksort(data+pivot+1, len-pivot-1);
71 }
72