| 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 |
|