| [2aa6644] | 1 | /*BHEADER**********************************************************************
|
|---|
| 2 | * Copyright (c) 2008, Lawrence Livermore National Security, LLC.
|
|---|
| 3 | * Produced at the Lawrence Livermore National Laboratory.
|
|---|
| 4 | * This file is part of HYPRE. See file COPYRIGHT for details.
|
|---|
| 5 | *
|
|---|
| 6 | * HYPRE is free software; you can redistribute it and/or modify it under the
|
|---|
| 7 | * terms of the GNU Lesser General Public License (as published by the Free
|
|---|
| 8 | * Software Foundation) version 2.1 dated February 1999.
|
|---|
| 9 | *
|
|---|
| 10 | * $Revision: 2.4 $
|
|---|
| 11 | ***********************************************************************EHEADER*/
|
|---|
| 12 |
|
|---|
| 13 |
|
|---|
| 14 | #include "utilities.h"
|
|---|
| 15 | #include <math.h>
|
|---|
| 16 |
|
|---|
| 17 | /*--------------------------------------------------------------------------
|
|---|
| 18 | * hypre_DoubleQuickSplit
|
|---|
| 19 | * C version of the routine "qsplit" from SPARSKIT
|
|---|
| 20 | * Uses a quicksort-type algorithm to split data into
|
|---|
| 21 | * highest "NumberCut" values without completely sorting them.
|
|---|
| 22 | * Data is double precision data.
|
|---|
| 23 | *--------------------------------------------------------------------------*/
|
|---|
| 24 |
|
|---|
| 25 | int hypre_DoubleQuickSplit(double *values, int *indices,
|
|---|
| 26 | int list_length, int NumberKept )
|
|---|
| 27 | {
|
|---|
| 28 | int ierr = 0;
|
|---|
| 29 | double interchange_value;
|
|---|
| 30 | double abskey;
|
|---|
| 31 | int interchange_index;
|
|---|
| 32 | int first, last;
|
|---|
| 33 | int mid, j;
|
|---|
| 34 | int done;
|
|---|
| 35 |
|
|---|
| 36 | first = 0;
|
|---|
| 37 | last = list_length-1;
|
|---|
| 38 |
|
|---|
| 39 | if ( (NumberKept < first+1) || (NumberKept > last+1) )
|
|---|
| 40 | return( ierr );
|
|---|
| 41 |
|
|---|
| 42 | /* Loop until the "midpoint" is NumberKept */
|
|---|
| 43 | done = 0;
|
|---|
| 44 |
|
|---|
| 45 | for ( ; !done; )
|
|---|
| 46 | {
|
|---|
| 47 | mid = first;
|
|---|
| 48 | abskey = fabs( values[ mid ]);
|
|---|
| 49 |
|
|---|
| 50 | for( j = first+1; j <= last; j ++)
|
|---|
| 51 | {
|
|---|
| 52 | if( fabs( values[ j ]) > abskey )
|
|---|
| 53 | {
|
|---|
| 54 | mid ++;
|
|---|
| 55 | /* interchange values */
|
|---|
| 56 | interchange_value = values[ mid];
|
|---|
| 57 | interchange_index = indices[ mid];
|
|---|
| 58 | values[ mid] = values[ j];
|
|---|
| 59 | indices[ mid] = indices[ j];
|
|---|
| 60 | values[ j] = interchange_value;
|
|---|
| 61 | indices[ j] = interchange_index;
|
|---|
| 62 | }
|
|---|
| 63 | }
|
|---|
| 64 |
|
|---|
| 65 | /* interchange the first and mid value */
|
|---|
| 66 | interchange_value = values[ mid];
|
|---|
| 67 | interchange_index = indices[ mid];
|
|---|
| 68 | values[ mid] = values[ first];
|
|---|
| 69 | indices[ mid] = indices[ first];
|
|---|
| 70 | values[ first] = interchange_value;
|
|---|
| 71 | indices[ first] = interchange_index;
|
|---|
| 72 |
|
|---|
| 73 | if ( mid+1 == NumberKept )
|
|---|
| 74 | {
|
|---|
| 75 | done = 1;
|
|---|
| 76 | break;
|
|---|
| 77 | }
|
|---|
| 78 | if ( mid+1 > NumberKept )
|
|---|
| 79 | last = mid - 1;
|
|---|
| 80 | else
|
|---|
| 81 | first = mid + 1;
|
|---|
| 82 | }
|
|---|
| 83 |
|
|---|
| 84 | return ( ierr );
|
|---|
| 85 | }
|
|---|
| 86 |
|
|---|
