Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_qsort_template: quicksort of a K-by-n array
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : //
8 : // For additional details (including references to third party source code and
9 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
10 : // Contributors.txt for a full list of contributors. Created, in part, with
11 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
12 : // DM22-0790
13 :
14 : // Contributed by Timothy A. Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : // This file is #include'd in LG_qsort*.c to create specific versions for
19 : // different kinds of sort keys and auxiliary arrays. Requires an inline or
20 : // macro definition of the LG_lt function. The LG_lt function has the form
21 : // LG_lt (A,i,B,j) and returns true if A[i] < B[j].
22 :
23 : // All of these functions are static; there will be versions of them in each
24 : // variant of LG_qsort*, and given unique names via #define's in the
25 : // #include'ing file.
26 :
27 : //------------------------------------------------------------------------------
28 : // LG_partition: use a pivot to partition an array
29 : //------------------------------------------------------------------------------
30 :
31 : // C.A.R Hoare partition method, partitions an array in-place via a pivot.
32 : // k = partition (A, n) partitions A [0:n-1] such that all entries in
33 : // A [0:k] are <= all entries in A [k+1:n-1].
34 :
35 1334739 : static inline int64_t LG_partition
36 : (
37 : LG_args (A), // array(s) to partition
38 : const int64_t n, // size of the array(s) to partition
39 : uint64_t *seed, // random number seed, modified on output
40 : LG_void *tx
41 : )
42 : {
43 :
44 : // select a pivot at random
45 1334739 : int64_t pivot = LG_Random64 (seed) % n ;
46 :
47 : // get the Pivot
48 1334739 : int64_t Pivot_0 [1] ; Pivot_0 [0] = A_0 [pivot] ;
49 : #if LG_K > 1
50 1166192 : int64_t Pivot_1 [1] ; Pivot_1 [0] = A_1 [pivot] ;
51 : #endif
52 : #if LG_K > 2
53 113051 : int64_t Pivot_2 [1] ; Pivot_2 [0] = A_2 [pivot] ;
54 : #endif
55 :
56 : // At the top of the while loop, A [left+1...right-1] is considered, and
57 : // entries outside this range are in their proper place and not touched.
58 : // Since the input specification of this function is to partition A
59 : // [0..n-1], left must start at -1 and right must start at n.
60 1334739 : int64_t left = -1 ;
61 1334739 : int64_t right = n ;
62 :
63 : // keep partitioning until the left and right sides meet
64 23869150 : while (true)
65 : {
66 : // loop invariant: A [0..left] < pivot and A [right..n-1] > pivot,
67 : // so the region to be considered is A [left+1 ... right-1].
68 :
69 : // increment left until finding an entry A [left] >= pivot
70 106596878 : do { left++ ; } while (LG_lt (A, left, Pivot, 0)) ;
71 :
72 : // decrement right until finding an entry A [right] <= pivot
73 104777739 : do { right-- ; } while (LG_lt (Pivot, 0, A, right)) ;
74 :
75 : // now A [0..left-1] < pivot and A [right+1..n-1] > pivot, but
76 : // A [left] > pivot and A [right] < pivot, so these two entries
77 : // are out of place and must be swapped.
78 :
79 : // However, if the two sides have met, the partition is finished.
80 25203889 : if (left >= right)
81 : {
82 : // A has been partitioned into A [0:right] and A [right+1:n-1].
83 : // k = right+1, so A is split into A [0:k-1] and A [k:n-1].
84 1334739 : return (right + 1) ;
85 : }
86 :
87 : // since A [left] > pivot and A [right] < pivot, swap them
88 23869150 : LG_swap (A, left, right) ;
89 :
90 : // after the swap this condition holds:
91 : // A [0..left] < pivot and A [right..n-1] > pivot
92 : }
93 : }
94 :
95 : //------------------------------------------------------------------------------
96 : // LG_quicksort: recursive single-threaded quicksort
97 : //------------------------------------------------------------------------------
98 :
99 2672629 : static void LG_quicksort // sort A [0:n-1]
100 : (
101 : LG_args (A), // array(s) to sort
102 : const int64_t n, // size of the array(s) to sort
103 : uint64_t *seed, // random number seed
104 : LG_void *tx
105 : )
106 : {
107 :
108 2672629 : if (n < 20)
109 : {
110 : // in-place insertion sort on A [0:n-1], where n is small
111 14605831 : for (int64_t k = 1 ; k < n ; k++)
112 : {
113 22075964 : for (int64_t j = k ; j > 0 && LG_lt (A, j, A, j-1) ; j--)
114 : {
115 : // swap A [j-1] and A [j]
116 8808023 : LG_swap (A, j-1, j) ;
117 : }
118 : }
119 : }
120 : else
121 : {
122 : // partition A [0:n-1] into A [0:k-1] and A [k:n-1]
123 1334739 : int64_t k = LG_partition (LG_arg (A), n, seed, tx) ;
124 :
125 : // sort each partition
126 1334739 : LG_quicksort (LG_arg (A), k, seed, tx) ; // sort A [0:k-1]
127 1334739 : LG_quicksort (LG_arg_offset (A, k), n-k, seed, tx) ; // sort A [k+1:n-1]
128 : }
129 2672629 : }
|
