Сортировка коллекций в Go

Упорядочивание коллекции

Сортировка — это расстановка элементов коллекции в определённом порядке.

У некоторых типов есть естественный порядок. Числа упорядочиваются по значению: 1 идёт перед 2. Строки упорядочиваются по алфавиту: "four" идёт перед "one". Для всего остального, а также когда нужен другой порядок, вы задаёте свой порядок: функцию сравнения, которая смотрит на два элемента и говорит, какой из них идёт первым.

Go сортирует срезы с помощью пакета slices:

slices.Sort() сортирует срез в естественном порядке. Он изменяет срез на месте: исходный порядок теряется.
slices.Sorted() (Go 1.23) возвращает новый отсортированный срез и оставляет исходный таким, каким он был. Вы передаёте ей slices.Values(s), которая проходит по элементам s.
slices.SortFunc() сортирует на месте с помощью вашей собственной функции сравнения.

Более старая функция sort.Slice() из пакета sort делает ту же работу с функцией «less», которая возвращает true или false. В новом коде обычно используют slices.

В примерах ниже используются слова one, two, three, four.

Синтаксис функции сравнения для SortFunc

T обозначает тип элемента. Функция сравнения получает два элемента и возвращает число: отрицательное, когда первым идёт a, положительное, когда первым идёт b, и 0, когда они равны. cmp.Compare(a, b) из пакета cmp даёт как раз такое число для чисел и строк.

slices.SortFunc(items, func(a, b T) int {
  // return a negative number if a comes first,
  // a positive number if b comes first, 0 if equal
})

Естественный порядок

Естественный порядок — это порядок, который есть у типа сам по себе: числа по значению, строки буква за буквой.

slices.Sorted(slices.Values(s)) даёт новый срез в естественном порядке. Для порядка по убыванию отдельной функции нет: сначала отсортируйте, а затем разверните срез с помощью slices.Reverse().

У ваших собственных типов естественного порядка нет. В Go его добавляют, написав у структуры метод Compare, который возвращает отрицательное число, ноль или положительное число — то же правило, что и у функции сравнения. Затем этот метод можно передать в slices.SortFunc() или использовать напрямую, чтобы сравнить два значения.

Отсортированная копия

slices.Sorted() создаёт новый срез, отсортированный по алфавиту. Исходный срез words печатается после, чтобы показать, что он не изменился.

Возьмите слова one, two, three, four. Создайте новый срез, отсортированный в естественном (алфавитном) порядке, с помощью slices.Sorted, чтобы исходный срез не изменился. Выведите отсортированный срез, затем выведите исходный срез.

> Вывод: программа на Go и захваченный вывод

Prompt

Возьмите слова one, two, three, four. Создайте новый срез, отсортированный в естественном (алфавитном) порядке, с помощью slices.Sorted, чтобы исходный срез не изменился. Выведите отсортированный срез, затем выведите исходный срез.

package main

import (
  "fmt"
  "slices"
)

func main() {
  words := []string{"one", "two", "three", "four"}

  // slices.Sorted возвращает новый отсортированный срез; words остаётся прежним.
  sorted := slices.Sorted(slices.Values(words))

  fmt.Println(sorted)
  fmt.Println(words)
}

Сортировка по убыванию

Копия сортируется, затем slices.Reverse() переворачивает её, поэтому слова идут от "two" вниз до "four".

Возьмите слова one, two, three, four. Сделайте отсортированную копию с помощью slices.Sorted, затем переверните её с помощью slices.Reverse, чтобы слова шли в обратном алфавитном порядке. Выведите результат.

> Вывод: программа на Go и захваченный вывод

Prompt

Возьмите слова one, two, three, four. Сделайте отсортированную копию с помощью slices.Sorted, затем переверните её с помощью slices.Reverse, чтобы слова шли в обратном алфавитном порядке. Выведите результат.

package main

import (
  "fmt"
  "slices"
)

func main() {
  words := []string{"one", "two", "three", "four"}

  // Сортируем копию, затем разворачиваем её.
  desc := slices.Sorted(slices.Values(words))
  slices.Reverse(desc)

  fmt.Println(desc)
}

Тип со своим порядком

У Version есть числа Major и Minor. Его метод Compare сначала сравнивает Major; только когда они равны, решает Minor. cmp.Or() выбирает первый результат, который не равен 0. Проверка Compare(...) > 0 отвечает на вопрос «первая версия больше?».

Определите структуру Version с полями Major и Minor и добавьте ей метод Compare, который возвращает отрицательное число, ноль или положительное число, сравнивая сначала Major, а затем Minor. Выведите, больше ли версия 1.2, чем 1.3, а затем — больше ли 2.0, чем 1.5, используя Compare(...) > 0.

> Вывод: программа на Go и захваченный вывод

Prompt

Определите структуру Version с полями Major и Minor и добавьте ей метод Compare, который возвращает отрицательное число, ноль или положительное число, сравнивая сначала Major, а затем Minor. Выведите, больше ли версия 1.2, чем 1.3, а затем — больше ли 2.0, чем 1.5, используя Compare(...) > 0.

package main

import (
  "cmp"
  "fmt"
)

type Version struct {
  Major int
  Minor int
}

// Compare возвращает отрицательное число, ноль или положительное число,
// как функции сравнения, которые использует slices.SortFunc.
func (v Version) Compare(other Version) int {
  return cmp.Or(
    cmp.Compare(v.Major, other.Major),
    cmp.Compare(v.Minor, other.Minor),
  )
}

func main() {
  // Больше ли 1.2, чем 1.3?
  fmt.Println(Version{1, 2}.Compare(Version{1, 3}) > 0)

  // Больше ли 2.0, чем 1.5?
  fmt.Println(Version{2, 0}.Compare(Version{1, 5}) > 0)
}

Свои порядки сортировки

Свой порядок — это любой порядок, который вы описываете функцией сравнения.

slices.SortFunc() сортирует срез на месте с помощью такой функции. Если два элемента сравниваются как равные, их порядок не гарантируется. slices.SortStableFunc() сохраняет равные элементы в их исходном порядке. Используйте её, когда это важно, например при сортировке слов по длине.

Частое желание — отсортировать по одному свойству каждого элемента. Специальной функции для этого в Go нет: вы пишете функцию сравнения, которая сравнивает это свойство, обычно с помощью cmp.Compare().

Для порядка по убыванию поменяйте местами a и b в сравнении: cmp.Compare(b, a) вместо cmp.Compare(a, b).

Чтобы отсортировать сначала по одному признаку, а затем по другому, объедините два сравнения с помощью cmp.Or(). Она возвращает первый результат, который не равен 0. Если первое сравнение говорит, что элементы равны, спор решает второе.

Сортировка с функцией сравнения

Функция сравнения возвращает len(a) - len(b). Отрицательный результат означает, что a короче и идёт первым, поэтому слова оказываются от самого короткого к самому длинному.

Возьмите слова aaa, bb, c. Отсортируйте их с помощью slices.SortFunc, используя функцию сравнения, которая возвращает len(a) - len(b), чтобы более короткие слова шли первыми. Выведите результат.

> Вывод: программа на Go и захваченный вывод

Prompt

Возьмите слова aaa, bb, c. Отсортируйте их с помощью slices.SortFunc, используя функцию сравнения, которая возвращает len(a) - len(b), чтобы более короткие слова шли первыми. Выведите результат.

package main

import (
  "fmt"
  "slices"
)

func main() {
  words := []string{"aaa", "bb", "c"}

  // Более короткие строки идут первыми.
  slices.SortFunc(words, func(a, b string) int {
    return len(a) - len(b)
  })

  fmt.Println(words)
}

Сортировка по длине

Слова сравниваются по длине с помощью cmp.Compare(len(a), len(b)). "one" и "two" — оба длиной 3 буквы; стабильная сортировка сохраняет "one" перед "two".

Возьмите слова one, two, three, four. Отсортируйте их по длине с помощью slices.SortStableFunc и cmp.Compare по длинам, чтобы слова одинаковой длины сохранили свой исходный порядок. Выведите результат.

> Вывод: программа на Go и захваченный вывод

Prompt

Возьмите слова one, two, three, four. Отсортируйте их по длине с помощью slices.SortStableFunc и cmp.Compare по длинам, чтобы слова одинаковой длины сохранили свой исходный порядок. Выведите результат.

package main

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

func main() {
  words := []string{"one", "two", "three", "four"}

  // Стабильная сортировка: слова одинаковой длины сохраняют исходный порядок.
  slices.SortStableFunc(words, func(a, b string) int {
    return cmp.Compare(len(a), len(b))
  })

  fmt.Println(words)
}

Сортировка по последней букве, по убыванию

a[len(a)-1] — это последняя буква слова. Буквы b и a передаются в cmp.Compare() в обратном порядке, поэтому первым идёт слово с самой большой последней буквой: "four" (r), затем "two" (o), затем два слова, оканчивающихся на «e», в их исходном порядке.

Возьмите слова one, two, three, four. Отсортируйте их по последней букве по убыванию: используйте slices.SortStableFunc с cmp.Compare, передавая последнюю букву b перед последней буквой a. Выведите результат.

> Вывод: программа на Go и захваченный вывод

Prompt

Возьмите слова one, two, three, four. Отсортируйте их по последней букве по убыванию: используйте slices.SortStableFunc с cmp.Compare, передавая последнюю букву b перед последней буквой a. Выведите результат.

package main

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

func main() {
  words := []string{"one", "two", "three", "four"}

  // Сравниваем последние буквы, b и a поменяны местами для порядка по убыванию.
  slices.SortStableFunc(words, func(a, b string) int {
    return cmp.Compare(b[len(b)-1], a[len(a)-1])
  })

  fmt.Println(words)
}

Сортировка по длине, затем по алфавиту

cmp.Or() сначала сравнивает длины. Когда два слова одинаковой длины, она переходит к strings.Compare(), которая упорядочивает их по алфавиту.

Возьмите слова aaa, bb, c, b, a, aa, ccc. Отсортируйте их сначала по длине, а затем по алфавиту, используя slices.SortFunc с cmp.Or, чтобы объединить cmp.Compare по длинам и strings.Compare по словам. Выведите результат.

> Вывод: программа на Go и захваченный вывод

Prompt

Возьмите слова aaa, bb, c, b, a, aa, ccc. Отсортируйте их сначала по длине, а затем по алфавиту, используя slices.SortFunc с cmp.Or, чтобы объединить cmp.Compare по длинам и strings.Compare по словам. Выведите результат.

package main

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

func main() {
  words := []string{"aaa", "bb", "c", "b", "a", "aa", "ccc"}

  // cmp.Or использует первое сравнение, которое не равно 0: сначала длина, затем алфавит.
  slices.SortFunc(words, func(a, b string) int {
    return cmp.Or(
      cmp.Compare(len(a), len(b)),
      strings.Compare(a, b),
    )
  })

  fmt.Println(words)
}

Проверка порядка сортировки

Иногда нужно только узнать, отсортирован ли срез уже, не сортируя его.

slices.IsSorted() возвращает true, когда срез идёт по возрастанию в естественном порядке. slices.IsSortedFunc() делает то же самое с вашей собственной функцией сравнения. В Go нет IsSortedDescending: передайте функцию сравнения, в которой a и b поменяны местами.

Чтобы проверить порядок по одному свойству, например по возрасту пользователя, сравнивайте это свойство внутри функции.

Проверка по возрастанию и по убыванию

slices.IsSorted() подтверждает, что 1, 2, 3, 4 идут по возрастанию. slices.IsSortedFunc() с cmp.Compare(b, a) подтверждает, что 4, 3, 2, 1 идут по убыванию.

Проверьте с помощью slices.IsSorted, идут ли числа 1, 2, 3, 4 по возрастанию, и выведите ответ. Затем проверьте с помощью slices.IsSortedFunc и функции сравнения, которая меняет местами a и b, идут ли 4, 3, 2, 1 по убыванию, и выведите этот ответ.

> Вывод: программа на Go и захваченный вывод

Prompt

Проверьте с помощью slices.IsSorted, идут ли числа 1, 2, 3, 4 по возрастанию, и выведите ответ. Затем проверьте с помощью slices.IsSortedFunc и функции сравнения, которая меняет местами a и b, идут ли 4, 3, 2, 1 по убыванию, и выведите этот ответ.

package main

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

func main() {
  ascending := []int{1, 2, 3, 4}
  descending := []int{4, 3, 2, 1}

  fmt.Println(slices.IsSorted(ascending))

  // Поменянные местами аргументы проверяют порядок по убыванию.
  fmt.Println(slices.IsSortedFunc(descending, func(a, b int) int {
    return cmp.Compare(b, a)
  }))
}

Проверка порядка по полю

Пользователи — Alice (24), Bob (31) и Charlie (29). Функция сравнения смотрит только на Age. Bob старше Charlie, поэтому срез не отсортирован по возрасту.

Определите структуру User с полями Name и Age. Составьте срез с Alice 24, Bob 31 и Charlie 29. С помощью slices.IsSortedFunc и cmp.Compare по возрастам проверьте, отсортированы ли пользователи по возрасту, и выведите ответ.

> Вывод: программа на Go и захваченный вывод

Prompt

Определите структуру User с полями Name и Age. Составьте срез с Alice 24, Bob 31 и Charlie 29. С помощью slices.IsSortedFunc и cmp.Compare по возрастам проверьте, отсортированы ли пользователи по возрасту, и выведите ответ.

package main

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

type User struct {
  Name string
  Age  int
}

func main() {
  users := []User{{"Alice", 24}, {"Bob", 31}, {"Charlie", 29}}

  // Идут ли пользователи в порядке возраста?
  fmt.Println(slices.IsSortedFunc(users, func(a, b User) int {
    return cmp.Compare(a.Age, b.Age)
  }))
}

Обратный порядок

Разворот ставит последний элемент первым, а первый — последним.

slices.Reverse() разворачивает срез на месте. Чтобы вместо этого получить развёрнутую копию, сначала скопируйте срез с помощью slices.Clone() и разверните копию. Оригинал сохраняет свой порядок.

Развёрнутая копия

Копия разворачивается и печатается, затем печатается оригинал, чтобы показать, что он не изменился.

Возьмите слова one, two, three, four. Скопируйте срез с помощью slices.Clone и разверните копию с помощью slices.Reverse, чтобы оригинал остался прежним. Выведите развёрнутую копию, затем выведите оригинал.

> Вывод: программа на Go и захваченный вывод

Prompt

Возьмите слова one, two, three, four. Скопируйте срез с помощью slices.Clone и разверните копию с помощью slices.Reverse, чтобы оригинал остался прежним. Выведите развёрнутую копию, затем выведите оригинал.

package main

import (
  "fmt"
  "slices"
)

func main() {
  words := []string{"one", "two", "three", "four"}

  // Разворачиваем копию, чтобы оригинал сохранил свой порядок.
  reversed := slices.Clone(words)
  slices.Reverse(reversed)

  fmt.Println(reversed)
  fmt.Println(words)
}

Случайный порядок

Перемешивание расставляет элементы в случайном порядке.

В пакете Go math/rand есть функция Shuffle(). Вы передаёте ей количество элементов и функцию обмена; она вызывает функцию обмена для случайных пар позиций. Как и slices.Reverse(), она работает на месте, поэтому перемешивайте копию, сделанную с помощью slices.Clone(), если оригинал ещё нужен.

Источник случайных чисел, созданный через rand.New(rand.NewSource(seed)), даёт один и тот же «случайный» порядок при каждом запуске программы с этим seed. Это удобно для тестов и для примеров вроде этого. Без фиксированного seed порядок меняется при каждом запуске.

Перемешанная копия

Источник случайных чисел с seed 7 перемешивает копию слов. Функция обмена меняет местами элементы на позициях i и j.

Возьмите слова one, two, three, four. Создайте источник случайных чисел с seed 7 через rand.New(rand.NewSource(7)). Перемешайте копию среза, сделанную с помощью slices.Clone, используя метод Shuffle с функцией обмена. Выведите перемешанную копию.

> Вывод: программа на Go и захваченный вывод

Prompt

Возьмите слова one, two, three, four. Создайте источник случайных чисел с seed 7 через rand.New(rand.NewSource(7)). Перемешайте копию среза, сделанную с помощью slices.Clone, используя метод Shuffle с функцией обмена. Выведите перемешанную копию.

package main

import (
  "fmt"
  "math/rand"
  "slices"
)

func main() {
  words := []string{"one", "two", "three", "four"}

  // Фиксированный seed даёт один и тот же «случайный» порядок при каждом запуске.
  r := rand.New(rand.NewSource(7))

  shuffled := slices.Clone(words)
  r.Shuffle(len(shuffled), func(i, j int) {
    shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
  })

  fmt.Println(shuffled)
}