【競プロ】Golangでの配列の部分ソート【Golang】

Golangでの配列の部分ソートを紹介します。
ABC289 B問題で使用する場面があるので、サンプルコードとともに説明します。

ABC B問題 サンプルコード

ABC289 B.go

package main

import (
	"fmt"
	"sort"
)

func main() {
	var N, M int
	fmt.Scan(&N, &M)

	a := make([]int, M)
	for i := 0; i < M; i++ {
		fmt.Scan(&a[i])
	}
	nums := make([]int, N+2)
	for i := 0; i <= N; i++ {
		nums[i] = i
	}

	for i := 0; i < M; i++ {
		for j := i + 1; j <= M; j++ {
			if j != M && a[i]+j == a[j]+i {
				// レ点が連続していたら、まだ部分的にソートするところではないので、処理を飛ばす
				continue
			}
			// 現在のレ点が直後のレ点と地続きになっていなければ、部分ソート(降順)する
			inplaceReverseSort(nums, a[i], a[j-1]+2)
			i = j - 1 // インクリメントされるので、マイナス1してる
			break
		}
	}

	for _, num := range nums[1 : len(nums)-1] {
		fmt.Print(num, " ")
	}

}

// 配列を部分ソート(リバースソート)する関数
func inplaceReverseSort(arr []int, n, m int) {
	sort.Slice(arr[n:m], func(i, j int) bool {
		return arr[n+i] > arr[n+j] // 降順にソート
	})
}

部分ソート部分をピックアップ

func inplaceReverseSort(arr []int, n, m int) {
	sort.Slice(arr[n:m], func(i, j int) bool {
		return arr[n+i] > arr[n+j] // 降順にソート
	})
}

• return arr[n+i] > arr[n+j] について：
  • iとjは、arr[n:m]の中でのローカルなインデックスを指す。
  • つまり、jはn:mのスライス内部の相対的なインデックスであり、元の配列arrのインデックスではない。
  • 元の配列arr全体を参照する場合、iとjは相対インデックスなので、nを加算して元の配列の絶対インデックスに変換する必要がある。
  • arr[n+i] > arr[n+j] の形にすることで、元の配列arrの正しい要素を比較できる。

最後に

Golangでソートするとなると、sort.Ints()やsort.Sort(sort.Reverse(sort.IntSlice()))、sort.Slice(arr, func(i, j) bool { return arr[i] < arr[j]})あたりをよく使いますよね。
ただ、どれも配列全体をソートする場面が多いので、意外とインデックスを使って部分ソートする場面は、灰色のレートだと少ないように思いました。
今回は、ADTでこの問題を知り、200点問題でも部分ソートで回答できる問題に会えてよかったと思いました。