Sort Slice di Golang: slices.Sort, SortFunc, dan Banyak Field

Mengurutkan tipe bawaan

slices.Sort mengurutkan slice apa pun yang tipe elemennya bisa diurutkan: integer, float, dan string. Fungsi ini mengurutkan langsung di tempat dan tidak mengembalikan apa-apa.

package main

import (
	"fmt"
	"slices"
)

func main() {
	nums := []int{42, 7, 19, 3, 88}
	slices.Sort(nums)
	fmt.Println(nums)

	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.Sort(names)
	fmt.Println(names) // byte order: uppercase before lowercase

	fmt.Println(slices.IsSorted(nums))

	i, found := slices.BinarySearch(nums, 19)
	fmt.Println(i, found)
}

Output:

[3 7 19 42 88]
[Bob Carl alice lisa]
true
2 true

String diurutkan berdasarkan byte, jadi setiap huruf besar ASCII muncul sebelum setiap huruf kecil. Untuk nama, hasil itu jarang sesuai harapan pengguna. Bagian berikutnya memperbaikinya.

Package slices hadir di Go 1.21. Sort miliknya adalah pattern-defeating quicksort: O(n log n), di tempat, dan tidak stabil.

Urutan sendiri dengan SortFunc

slices.SortFunc menerima fungsi pembanding func(a, b T) int. Kembalikan angka negatif jika a harus di depan, angka positif jika b yang harus di depan, dan nol jika keduanya sama. Helper cmp.Compare mengembalikan tepat itu untuk tipe yang bisa diurutkan.

package main

import (
	"cmp"
	"fmt"
	"slices"
	"strings"
)

func main() {
	names := []string{"lisa", "Bob", "alice", "Carl"}
	slices.SortFunc(names, func(a, b string) int {
		return cmp.Compare(strings.ToLower(a), strings.ToLower(b))
	})
	fmt.Println(names)

	// Descending: swap a and b.
	nums := []int{42, 7, 19, 3, 88}
	slices.SortFunc(nums, func(a, b int) int {
		return cmp.Compare(b, a)
	})
	fmt.Println(nums)

	// By length, shortest first.
	words := []string{"banana", "fig", "apple", "kiwi"}
	slices.SortFunc(words, func(a, b string) int {
		return cmp.Compare(len(a), len(b))
	})
	fmt.Println(words)
}

strings.ToLower di dalam perbandingan mengalokasikan string baru setiap kali input-nya berisi huruf besar, dan perbandingan dijalankan sekitar n log n kali. Untuk slice besar, hitung key huruf kecilnya sekali saja. Untuk nama dalam bahasa lain (aksen, aturan locale), pakai golang.org/x/text/collate, yang berada di luar pustaka standar.

Fungsi pembanding harus konsisten: kalau ia bilang a di depan b, ia juga harus bilang b di belakang a. Fungsi yang melanggar aturan ini (misalnya mengembalikan -1 setiap kali dua nilai berbeda) menghasilkan slice dengan urutan salah tanpa error. Mengurangkan integer (return a - b) terlihat rapi, tetapi bisa overflow untuk nilai besar; pakai cmp.Compare.

Mengurutkan struct

Fungsi pembanding menerima elemen, jadi mengurutkan struct berdasarkan sebuah field memakai panggilan yang sama:

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Compare(a.Salary, b.Salary)
	})
	for _, e := range staff {
		fmt.Println(e.Salary, e.Name)
	}
}

Karyawan dengan gaji yang sama bisa keluar dalam urutan apa pun di sini, karena SortFunc tidak stabil. Kalau kamu butuh urutan yang pasti, pecahkan seri dengan field lain atau pakai stable sort.

Mengurutkan berdasarkan beberapa field

Bandingkan field yang paling penting lebih dulu, dan lanjut ke field berikutnya hanya kalau hasilnya seri. cmp.Or (Go 1.22) mengembalikan argumen pertamanya yang bukan nol, sehingga semuanya jadi satu baris:

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Employee struct {
	Name   string
	Dept   string
	Salary int
}

func main() {
	staff := []Employee{
		{"Ana", "eng", 120},
		{"Bob", "sales", 90},
		{"Cy", "eng", 150},
		{"Dee", "sales", 90},
		{"Eve", "eng", 120},
	}

	// Department A to Z, then salary high to low, then name A to Z.
	slices.SortFunc(staff, func(a, b Employee) int {
		return cmp.Or(
			cmp.Compare(a.Dept, b.Dept),
			cmp.Compare(b.Salary, a.Salary),
			cmp.Compare(a.Name, b.Name),
		)
	})
	for _, e := range staff {
		fmt.Printf("%-6s %4d %s\n", e.Dept, e.Salary, e.Name)
	}
}

Output:

eng     150 Cy
eng     120 Ana
eng     120 Eve
sales    90 Bob
sales    90 Dee

Setiap perbandingan tetap dievaluasi walaupun perbandingan pertama sudah menentukan hasilnya, karena semuanya hanyalah argumen biasa. Untuk perbandingan field, biayanya kecil. Kalau sebuah pemecah seri mahal, tulis rangkaian if c := ...; c != 0 { return c } secara manual.

Stable sort

Stable sort menjaga elemen yang dianggap sama tetap dalam urutan aslinya. Hal ini penting ketika input sudah punya urutan yang bermakna, misalnya catatan yang diurutkan berdasarkan waktu lalu sekarang kamu kelompokkan per pengguna.

package main

import (
	"cmp"
	"fmt"
	"slices"
)

type Event struct {
	User string
	Seq  int
}

func main() {
	events := []Event{
		{"bob", 1}, {"ana", 2}, {"bob", 3}, {"ana", 4}, {"bob", 5},
	}
	slices.SortStableFunc(events, func(a, b Event) int {
		return cmp.Compare(a.User, b.User)
	})
	fmt.Println(events)
}

Program ini mencetak [{ana 2} {ana 4} {bob 1} {bob 3} {bob 5}]: di dalam setiap pengguna, urutan aslinya tetap terjaga. Stable sort bekerja lebih banyak, jadi pakai hanya kalau urutan elemen yang sama itu penting.

Mengurutkan map

Map tidak punya urutan. Untuk menampilkan map yang terurut berdasarkan key, urutkan key-nya: slices.Sorted(maps.Keys(m)) (Go 1.23). Untuk mengurutkan berdasarkan value, urutkan key-nya dengan perbandingan yang mencari value-nya:

package main

import (
	"cmp"
	"fmt"
	"maps"
	"slices"
)

func main() {
	wordCount := map[string]int{"go": 12, "map": 3, "slice": 7, "chan": 7}

	keys := slices.Collect(maps.Keys(wordCount))
	slices.SortFunc(keys, func(a, b string) int {
		return cmp.Or(
			cmp.Compare(wordCount[b], wordCount[a]), // count, high first
			cmp.Compare(a, b),                       // then word, for a stable result
		)
	})
	for _, k := range keys {
		fmt.Println(k, wordCount[k])
	}
}

Pemecah seri berdasarkan kata itu penting: tanpanya, chan dan slice (keduanya 7) akan tercetak dalam urutan yang berbeda di setiap run, karena key keluar dari map dalam urutan acak. Lihat map untuk penjelasan lebih lanjut.

Package sort: sort.Slice dan kawan-kawannya

Sebelum Go 1.21, pengurutan dilakukan lewat package sort. Kamu akan menemukannya di banyak kode yang sudah ada:

sort.Ints(nums)
sort.Strings(names)
sort.Slice(staff, func(i, j int) bool {
	return staff[i].Salary < staff[j].Salary
})
sort.SliceStable(staff, func(i, j int) bool { ... })

Perbedaan yang perlu kamu tahu:

Bug yang umum pada sort.Slice adalah closure yang menangkap slice yang berbeda dari slice yang sedang diurutkan, karena fungsi less mengakses elemen berdasarkan posisi. SortFunc tidak mungkin punya bug itu karena ia langsung memberimu elemennya.

Tipe sort.Interface (Len, Less, Swap) adalah bentuk yang paling tua. Bentuk ini masih menjadi cara untuk mengurutkan data yang bukan satu slice tunggal, seperti dua slice paralel yang harus bergerak bersama. Sejak Go 1.22, sort.Ints, sort.Strings, dan sort.Float64s hanya memanggil slices.Sort.

Kesalahan umum

• Mengira Sort mengembalikan slice yang sudah terurut. Fungsi ini mengurutkan di tempat dan tidak mengembalikan apa-apa. Pakai slices.Sorted(slices.Values(s)) kalau kamu ingin slice baru yang terurut, atau slices.Clone lebih dulu.
• Mengira elemen yang sama tetap pada urutannya. Hanya varian Stable yang menjanjikan itu.
• Membandingkan dengan pengurangan. a - b bisa overflow. Pakai cmp.Compare.
• Mengurutkan float yang berisi NaN. cmp.Compare menempatkan NaN sebelum semua nilai lain, sehingga pengurutan tetap konsisten. Perbandingan a < b yang ditulis manual tidak begitu.