← Back

Partial Quicksort for Paging 分页场景下的部分快速排序 ページング向け部分クイックソート

Nov 1, 2023

Many APIs implement a paging mechanism, receiving pageNum and pageSize as parameters and returning only a slice of ordered results. If the data source is a relational database, this is usually handled by LIMIT and OFFSET in SQL. However, not all services store data locally — they may depend on one or more data sources that do not support sorting.

许多 API 实现了分页机制，即在参数中接收 pageNum 和 pageSize，只返回有序结果的一个切片。如果数据源是关系型数据库，通常可以通过 SQL 中的 LIMIT 和 OFFSET 来实现。然而，并非所有服务都将数据存储在本地——它们可能依赖一个或多个不支持排序的数据源。

多くの API はページングメカニズムを実装しており、パラメータとして pageNum と pageSize を受け取り、ソートされた結果の一部のみを返します。データソースがリレーショナルデータベースであれば、SQL の LIMIT と OFFSET で対応できます。しかし、すべてのサービスがデータをローカルに保存しているわけではなく、ソートをサポートしないデータソースに依存する場合もあります。

In such cases, we need to sort the results in memory and then cut the required slice. Notice that the actual requirement is only a correct range of sorted slice, not sorting the entire array. Hence a variation of quicksort can be applied — similar to the Top-K quicksort variant, but considering both boundary edges:

在这种情况下，我们需要自行在内存中对结果排序，然后截取所需的切片。注意，实际需求只是一个正确范围内的有序切片，而非对整个数组排序。因此可以应用一种快速排序的变体，与解决 Top-K 问题的快速排序变体类似，但需要同时考虑两侧边界：

このような場合、メモリ上で結果をソートしてから必要なスライスを切り出す必要があります。実際に必要なのは正しい範囲の有序スライスであり、配列全体をソートする必要はありません。そこで Top-K 問題に使われるクイックソートの変形を応用できます。ただし両側の境界を考慮する点が異なります：

package utils

import (
	"golang.org/x/exp/constraints"
)

func swap[T any](elements []T, i, j int) {
	elements[i], elements[j] = elements[j], elements[i]
}

func partition[T constraints.Ordered](elements []T, left, right int) int {
	pivot := elements[right-1]
	target := left
	for cur := left; cur < right; cur += 1 {
		if elements[cur] < pivot {
			swap(elements, target, cur)
			target += 1
		}
	}
	swap(elements, target, right-1)
	return target
}

func partialQuicksort[T constraints.Ordered](elements []T, start, end, left, right int) {
	if start >= end || left >= right || right < start || end < left {
		return
	}
	pivot := partition(elements, left, right)
	partialQuicksort(elements, start, end, left, pivot)
	partialQuicksort(elements, start, end, pivot+1, right)
}

func GetSortedSubSeq[T constraints.Ordered](elements []T, start, end int) []T {
	partialQuicksort(elements, start, end, 0, len(elements))
	return elements[start:end]
}

Since the partition step places the pivot in its correct position (all smaller elements to the left, all larger to the right), once all elements within the target range are determined by partition, they must be the expected elements in sorted order.

由于 partition 过程会将 pivot 放置到正确的位置（即所有较小的元素在左侧，所有较大的元素在右侧），一旦目标范围内的所有元素都被 partition 确定，它们必然是按有序序列排列的预期元素。

partition ステップはピボットを正しい位置（左側に小さい要素、右側に大きい要素）に配置するため、対象範囲内のすべての要素が partition によって決定されれば、それらは必ず正しい順序の期待される要素になります。

Some test code:

测试代码：

テストコード：

package utils

import (
	"testing"

	"github.com/stretchr/testify/require"
	"golang.org/x/exp/constraints"

	"code.byted.org/lang/gg/gslice"
)

func Range[T constraints.Integer](start, end T) []T {
	elements := make([]T, 0)
	for c := start; c < end; c += 1 {
		elements = append(elements, c)
	}
	return elements
}

func TestGetSortedSubSeq(t *testing.T) {
	as := require.New(t)
	elements, expected := Range(0, 100), Range(45, 55)

	gslice.Shuffle(elements)
	subseq := GetSortedSubSeq(elements, 45, 55)
	as.Equal(subseq, expected)

	gslice.Shuffle(elements)
	seq := GetSortedSubSeq(elements, 0, 100)
	gslice.Sort(elements)
	as.Equal(seq, elements)
}