zsortfunc.go

     1  // Code generated by gen_sort_variants.go; DO NOT EDIT.
     2  
     3  // Copyright 2022 The Go Authors. All rights reserved.
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  package sort
     8  
     9  // insertionSort_func sorts data[a:b] using insertion sort.
    10  func insertionSort_func(data lessSwap, a, b int) {
    11  	for i := a + 1; i < b; i++ {
    12  		for j := i; j > a && data.Less(j, j-1); j-- {
    13  			data.Swap(j, j-1)
    14  		}
    15  	}
    16  }
    17  
    18  // siftDown_func implements the heap property on data[lo:hi].
    19  // first is an offset into the array where the root of the heap lies.
    20  func siftDown_func(data lessSwap, lo, hi, first int) {
    21  	root := lo
    22  	for {
    23  		child := 2*root + 1
    24  		if child >= hi {
    25  			break
    26  		}
    27  		if child+1 < hi && data.Less(first+child, first+child+1) {
    28  			child++
    29  		}
    30  		if !data.Less(first+root, first+child) {
    31  			return
    32  		}
    33  		data.Swap(first+root, first+child)
    34  		root = child
    35  	}
    36  }
    37  
    38  func heapSort_func(data lessSwap, a, b int) {
    39  	first := a
    40  	lo := 0
    41  	hi := b - a
    42  
    43  	// Build heap with greatest element at top.
    44  	for i := (hi - 1) / 2; i >= 0; i-- {
    45  		siftDown_func(data, i, hi, first)
    46  	}
    47  
    48  	// Pop elements, largest first, into end of data.
    49  	for i := hi - 1; i >= 0; i-- {
    50  		data.Swap(first, first+i)
    51  		siftDown_func(data, lo, i, first)
    52  	}
    53  }
    54  
    55  // pdqsort_func sorts data[a:b].
    56  // The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort.
    57  // pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf
    58  // C++ implementation: https://github.com/orlp/pdqsort
    59  // Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/
    60  // limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.
    61  func pdqsort_func(data lessSwap, a, b, limit int) {
    62  	const maxInsertion = 12
    63  
    64  	var (
    65  		wasBalanced    = true // whether the last partitioning was reasonably balanced
    66  		wasPartitioned = true // whether the slice was already partitioned
    67  	)
    68  
    69  	for {
    70  		length := b - a
    71  
    72  		if length <= maxInsertion {
    73  			insertionSort_func(data, a, b)
    74  			return
    75  		}
    76  
    77  		// Fall back to heapsort if too many bad choices were made.
    78  		if limit == 0 {
    79  			heapSort_func(data, a, b)
    80  			return
    81  		}
    82  
    83  		// If the last partitioning was imbalanced, we need to breaking patterns.
    84  		if !wasBalanced {
    85  			breakPatterns_func(data, a, b)
    86  			limit--
    87  		}
    88  
    89  		pivot, hint := choosePivot_func(data, a, b)
    90  		if hint == decreasingHint {
    91  			reverseRange_func(data, a, b)
    92  			// The chosen pivot was pivot-a elements after the start of the array.
    93  			// After reversing it is pivot-a elements before the end of the array.
    94  			// The idea came from Rust's implementation.
    95  			pivot = (b - 1) - (pivot - a)
    96  			hint = increasingHint
    97  		}
    98  
    99  		// The slice is likely already sorted.
   100  		if wasBalanced && wasPartitioned && hint == increasingHint {
   101  			if partialInsertionSort_func(data, a, b) {
   102  				return
   103  			}
   104  		}
   105  
   106  		// Probably the slice contains many duplicate elements, partition the slice into
   107  		// elements equal to and elements greater than the pivot.
   108  		if a > 0 && !data.Less(a-1, pivot) {
   109  			mid := partitionEqual_func(data, a, b, pivot)
   110  			a = mid
   111  			continue
   112  		}
   113  
   114  		mid, alreadyPartitioned := partition_func(data, a, b, pivot)
   115  		wasPartitioned = alreadyPartitioned
   116  
   117  		leftLen, rightLen := mid-a, b-mid
   118  		balanceThreshold := length / 8
   119  		if leftLen < rightLen {
   120  			wasBalanced = leftLen >= balanceThreshold
   121  			pdqsort_func(data, a, mid, limit)
   122  			a = mid + 1
   123  		} else {
   124  			wasBalanced = rightLen >= balanceThreshold
   125  			pdqsort_func(data, mid+1, b, limit)
   126  			b = mid
   127  		}
   128  	}
   129  }
   130  
   131  // partition_func does one quicksort partition.
   132  // Let p = data[pivot]
   133  // Moves elements in data[a:b] around, so that data[i]<p and data[j]>=p for i<newpivot and j>newpivot.
   134  // On return, data[newpivot] = p
   135  func partition_func(data lessSwap, a, b, pivot int) (newpivot int, alreadyPartitioned bool) {
   136  	data.Swap(a, pivot)
   137  	i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned
   138  
   139  	for i <= j && data.Less(i, a) {
   140  		i++
   141  	}
   142  	for i <= j && !data.Less(j, a) {
   143  		j--
   144  	}
   145  	if i > j {
   146  		data.Swap(j, a)
   147  		return j, true
   148  	}
   149  	data.Swap(i, j)
   150  	i++
   151  	j--
   152  
   153  	for {
   154  		for i <= j && data.Less(i, a) {
   155  			i++
   156  		}
   157  		for i <= j && !data.Less(j, a) {
   158  			j--
   159  		}
   160  		if i > j {
   161  			break
   162  		}
   163  		data.Swap(i, j)
   164  		i++
   165  		j--
   166  	}
   167  	data.Swap(j, a)
   168  	return j, false
   169  }
   170  
   171  // partitionEqual_func partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot].
   172  // It assumed that data[a:b] does not contain elements smaller than the data[pivot].
   173  func partitionEqual_func(data lessSwap, a, b, pivot int) (newpivot int) {
   174  	data.Swap(a, pivot)
   175  	i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned
   176  
   177  	for {
   178  		for i <= j && !data.Less(a, i) {
   179  			i++
   180  		}
   181  		for i <= j && data.Less(a, j) {
   182  			j--
   183  		}
   184  		if i > j {
   185  			break
   186  		}
   187  		data.Swap(i, j)
   188  		i++
   189  		j--
   190  	}
   191  	return i
   192  }
   193  
   194  // partialInsertionSort_func partially sorts a slice, returns true if the slice is sorted at the end.
   195  func partialInsertionSort_func(data lessSwap, a, b int) bool {
   196  	const (
   197  		maxSteps         = 5  // maximum number of adjacent out-of-order pairs that will get shifted
   198  		shortestShifting = 50 // don't shift any elements on short arrays
   199  	)
   200  	i := a + 1
   201  	for j := 0; j < maxSteps; j++ {
   202  		for i < b && !data.Less(i, i-1) {
   203  			i++
   204  		}
   205  
   206  		if i == b {
   207  			return true
   208  		}
   209  
   210  		if b-a < shortestShifting {
   211  			return false
   212  		}
   213  
   214  		data.Swap(i, i-1)
   215  
   216  		// Shift the smaller one to the left.
   217  		if i-a >= 2 {
   218  			for j := i - 1; j >= 1; j-- {
   219  				if !data.Less(j, j-1) {
   220  					break
   221  				}
   222  				data.Swap(j, j-1)
   223  			}
   224  		}
   225  		// Shift the greater one to the right.
   226  		if b-i >= 2 {
   227  			for j := i + 1; j < b; j++ {
   228  				if !data.Less(j, j-1) {
   229  					break
   230  				}
   231  				data.Swap(j, j-1)
   232  			}
   233  		}
   234  	}
   235  	return false
   236  }
   237  
   238  // breakPatterns_func scatters some elements around in an attempt to break some patterns
   239  // that might cause imbalanced partitions in quicksort.
   240  func breakPatterns_func(data lessSwap, a, b int) {
   241  	length := b - a
   242  	if length >= 8 {
   243  		random := xorshift(length)
   244  		modulus := nextPowerOfTwo(length)
   245  
   246  		for idx := a + (length/4)*2 - 1; idx <= a+(length/4)*2+1; idx++ {
   247  			other := int(uint(random.Next()) & (modulus - 1))
   248  			if other >= length {
   249  				other -= length
   250  			}
   251  			data.Swap(idx, a+other)
   252  		}
   253  	}
   254  }
   255  
   256  // choosePivot_func chooses a pivot in data[a:b].
   257  //
   258  // [0,8): chooses a static pivot.
   259  // [8,shortestNinther): uses the simple median-of-three method.
   260  // [shortestNinther,∞): uses the Tukey ninther method.
   261  func choosePivot_func(data lessSwap, a, b int) (pivot int, hint sortedHint) {
   262  	const (
   263  		shortestNinther = 50
   264  		maxSwaps        = 4 * 3
   265  	)
   266  
   267  	l := b - a
   268  
   269  	var (
   270  		swaps int
   271  		i     = a + l/4*1
   272  		j     = a + l/4*2
   273  		k     = a + l/4*3
   274  	)
   275  
   276  	if l >= 8 {
   277  		if l >= shortestNinther {
   278  			// Tukey ninther method, the idea came from Rust's implementation.
   279  			i = medianAdjacent_func(data, i, &swaps)
   280  			j = medianAdjacent_func(data, j, &swaps)
   281  			k = medianAdjacent_func(data, k, &swaps)
   282  		}
   283  		// Find the median among i, j, k and stores it into j.
   284  		j = median_func(data, i, j, k, &swaps)
   285  	}
   286  
   287  	switch swaps {
   288  	case 0:
   289  		return j, increasingHint
   290  	case maxSwaps:
   291  		return j, decreasingHint
   292  	default:
   293  		return j, unknownHint
   294  	}
   295  }
   296  
   297  // order2_func returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.
   298  func order2_func(data lessSwap, a, b int, swaps *int) (int, int) {
   299  	if data.Less(b, a) {
   300  		*swaps++
   301  		return b, a
   302  	}
   303  	return a, b
   304  }
   305  
   306  // median_func returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.
   307  func median_func(data lessSwap, a, b, c int, swaps *int) int {
   308  	a, b = order2_func(data, a, b, swaps)
   309  	b, c = order2_func(data, b, c, swaps)
   310  	a, b = order2_func(data, a, b, swaps)
   311  	return b
   312  }
   313  
   314  // medianAdjacent_func finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.
   315  func medianAdjacent_func(data lessSwap, a int, swaps *int) int {
   316  	return median_func(data, a-1, a, a+1, swaps)
   317  }
   318  
   319  func reverseRange_func(data lessSwap, a, b int) {
   320  	i := a
   321  	j := b - 1
   322  	for i < j {
   323  		data.Swap(i, j)
   324  		i++
   325  		j--
   326  	}
   327  }
   328  
   329  func swapRange_func(data lessSwap, a, b, n int) {
   330  	for i := 0; i < n; i++ {
   331  		data.Swap(a+i, b+i)
   332  	}
   333  }
   334  
   335  func stable_func(data lessSwap, n int) {
   336  	blockSize := 20 // must be > 0
   337  	a, b := 0, blockSize
   338  	for b <= n {
   339  		insertionSort_func(data, a, b)
   340  		a = b
   341  		b += blockSize
   342  	}
   343  	insertionSort_func(data, a, n)
   344  
   345  	for blockSize < n {
   346  		a, b = 0, 2*blockSize
   347  		for b <= n {
   348  			symMerge_func(data, a, a+blockSize, b)
   349  			a = b
   350  			b += 2 * blockSize
   351  		}
   352  		if m := a + blockSize; m < n {
   353  			symMerge_func(data, a, m, n)
   354  		}
   355  		blockSize *= 2
   356  	}
   357  }
   358  
   359  // symMerge_func merges the two sorted subsequences data[a:m] and data[m:b] using
   360  // the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
   361  // Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
   362  // Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
   363  // Computer Science, pages 714-723. Springer, 2004.
   364  //
   365  // Let M = m-a and N = b-n. Wolog M < N.
   366  // The recursion depth is bound by ceil(log(N+M)).
   367  // The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
   368  // The algorithm needs O((M+N)*log(M)) calls to data.Swap.
   369  //
   370  // The paper gives O((M+N)*log(M)) as the number of assignments assuming a
   371  // rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
   372  // in the paper carries through for Swap operations, especially as the block
   373  // swapping rotate uses only O(M+N) Swaps.
   374  //
   375  // symMerge assumes non-degenerate arguments: a < m && m < b.
   376  // Having the caller check this condition eliminates many leaf recursion calls,
   377  // which improves performance.
   378  func symMerge_func(data lessSwap, a, m, b int) {
   379  	// Avoid unnecessary recursions of symMerge
   380  	// by direct insertion of data[a] into data[m:b]
   381  	// if data[a:m] only contains one element.
   382  	if m-a == 1 {
   383  		// Use binary search to find the lowest index i
   384  		// such that data[i] >= data[a] for m <= i < b.
   385  		// Exit the search loop with i == b in case no such index exists.
   386  		i := m
   387  		j := b
   388  		for i < j {
   389  			h := int(uint(i+j) >> 1)
   390  			if data.Less(h, a) {
   391  				i = h + 1
   392  			} else {
   393  				j = h
   394  			}
   395  		}
   396  		// Swap values until data[a] reaches the position before i.
   397  		for k := a; k < i-1; k++ {
   398  			data.Swap(k, k+1)
   399  		}
   400  		return
   401  	}
   402  
   403  	// Avoid unnecessary recursions of symMerge
   404  	// by direct insertion of data[m] into data[a:m]
   405  	// if data[m:b] only contains one element.
   406  	if b-m == 1 {
   407  		// Use binary search to find the lowest index i
   408  		// such that data[i] > data[m] for a <= i < m.
   409  		// Exit the search loop with i == m in case no such index exists.
   410  		i := a
   411  		j := m
   412  		for i < j {
   413  			h := int(uint(i+j) >> 1)
   414  			if !data.Less(m, h) {
   415  				i = h + 1
   416  			} else {
   417  				j = h
   418  			}
   419  		}
   420  		// Swap values until data[m] reaches the position i.
   421  		for k := m; k > i; k-- {
   422  			data.Swap(k, k-1)
   423  		}
   424  		return
   425  	}
   426  
   427  	mid := int(uint(a+b) >> 1)
   428  	n := mid + m
   429  	var start, r int
   430  	if m > mid {
   431  		start = n - b
   432  		r = mid
   433  	} else {
   434  		start = a
   435  		r = m
   436  	}
   437  	p := n - 1
   438  
   439  	for start < r {
   440  		c := int(uint(start+r) >> 1)
   441  		if !data.Less(p-c, c) {
   442  			start = c + 1
   443  		} else {
   444  			r = c
   445  		}
   446  	}
   447  
   448  	end := n - start
   449  	if start < m && m < end {
   450  		rotate_func(data, start, m, end)
   451  	}
   452  	if a < start && start < mid {
   453  		symMerge_func(data, a, start, mid)
   454  	}
   455  	if mid < end && end < b {
   456  		symMerge_func(data, mid, end, b)
   457  	}
   458  }
   459  
   460  // rotate_func rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data:
   461  // Data of the form 'x u v y' is changed to 'x v u y'.
   462  // rotate performs at most b-a many calls to data.Swap,
   463  // and it assumes non-degenerate arguments: a < m && m < b.
   464  func rotate_func(data lessSwap, a, m, b int) {
   465  	i := m - a
   466  	j := b - m
   467  
   468  	for i != j {
   469  		if i > j {
   470  			swapRange_func(data, m-i, m, j)
   471  			i -= j
   472  		} else {
   473  			swapRange_func(data, m-i, m+j-i, i)
   474  			j -= i
   475  		}
   476  	}
   477  	// i == j
   478  	swapRange_func(data, m-i, m, i)
   479  }
   480
View as plain text