1 //------------------------------------------------------------------------------
2 // GB_qsort_template: quicksort of a K-by-n array
3 //------------------------------------------------------------------------------
4
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7
8 //------------------------------------------------------------------------------
9
10 // This file is #include'd in GB_qsort*.c to create specific versions for
11 // different kinds of sort keys and auxiliary arrays. Requires an inline or
12 // macro definition of the GB_lt function. The GB_lt function has the form
13 // GB_lt (A,i,B,j) and returns true if A[i] < B[j].
14
15 // All of these functions are static; there will be versions of them in each
16 // variant of GB_qsort*, and given unique names via #define's in the
17 // #include'ing file.
18
19 //------------------------------------------------------------------------------
20 // GB_partition: use a pivot to partition an array
21 //------------------------------------------------------------------------------
22
23 // C.A.R Hoare partition method, partitions an array in-place via a pivot.
24 // k = partition (A, n) partitions A [0:n-1] such that all entries in
25 // A [0:k] are <= all entries in A [k+1:n-1].
26
GB_partition(GB_args (A),const int64_t n,uint64_t * seed)27 static inline int64_t GB_partition
28 (
29 GB_args (A), // array(s) to partition
30 const int64_t n, // size of the array(s) to partition
31 uint64_t *seed // random number seed, modified on output
32 )
33 {
34
35 // select a pivot at random
36 int64_t pivot = ((n < GB_RAND_MAX) ? GB_rand15 (seed) : GB_rand (seed)) % n;
37
38 // get the Pivot
39 int64_t Pivot_0 [1] ; Pivot_0 [0] = A_0 [pivot] ;
40 #if GB_K > 1
41 int64_t Pivot_1 [1] ; Pivot_1 [0] = A_1 [pivot] ;
42 #endif
43 #if GB_K > 2
44 int64_t Pivot_2 [1] ; Pivot_2 [0] = A_2 [pivot] ;
45 #endif
46
47 // At the top of the while loop, A [left+1...right-1] is considered, and
48 // entries outside this range are in their proper place and not touched.
49 // Since the input specification of this function is to partition A
50 // [0..n-1], left must start at -1 and right must start at n.
51 int64_t left = -1 ;
52 int64_t right = n ;
53
54 // keep partitioning until the left and right sides meet
55 while (true)
56 {
57 // loop invariant: A [0..left] < pivot and A [right..n-1] > pivot,
58 // so the region to be considered is A [left+1 ... right-1].
59
60 // increment left until finding an entry A [left] >= pivot
61 do { left++ ; } while (GB_lt (A, left, Pivot, 0)) ;
62
63 // decrement right until finding an entry A [right] <= pivot
64 do { right-- ; } while (GB_lt (Pivot, 0, A, right)) ;
65
66 // now A [0..left-1] < pivot and A [right+1..n-1] > pivot, but
67 // A [left] > pivot and A [right] < pivot, so these two entries
68 // are out of place and must be swapped.
69
70 // However, if the two sides have met, the partition is finished.
71 if (left >= right)
72 {
73 // A has been partitioned into A [0:right] and A [right+1:n-1].
74 // k = right+1, so A is split into A [0:k-1] and A [k:n-1].
75 return (right + 1) ;
76 }
77
78 // since A [left] > pivot and A [right] < pivot, swap them
79 GB_swap (A, left, right) ;
80
81 // after the swap this condition holds:
82 // A [0..left] < pivot and A [right..n-1] > pivot
83 }
84 }
85
86 //------------------------------------------------------------------------------
87 // GB_quicksort: recursive single-threaded quicksort
88 //------------------------------------------------------------------------------
89
GB_quicksort(GB_args (A),const int64_t n,uint64_t * seed)90 static void GB_quicksort // sort A [0:n-1]
91 (
92 GB_args (A), // array(s) to sort
93 const int64_t n, // size of the array(s) to sort
94 uint64_t *seed // random number seed
95 )
96 {
97
98 if (n < 20)
99 {
100 // in-place insertion sort on A [0:n-1], where n is small
101 for (int64_t k = 1 ; k < n ; k++)
102 {
103 for (int64_t j = k ; j > 0 && GB_lt (A, j, A, j-1) ; j--)
104 {
105 // swap A [j-1] and A [j]
106 GB_swap (A, j-1, j) ;
107 }
108 }
109 }
110 else
111 {
112 // partition A [0:n-1] into A [0:k-1] and A [k:n-1]
113 int64_t k = GB_partition (GB_arg (A), n, seed) ;
114
115 // sort each partition
116 GB_quicksort (GB_arg (A), k, seed) ; // sort A [0:k-1]
117 GB_quicksort (GB_arg_offset (A, k), n-k, seed) ; // sort A [k+1:n-1]
118 }
119 }
120
121