Бесплатный курс по go. Зарегистрируйтесь для отслеживания прогресса →

Go: Сортировка слайсов

Сортировка массива — распространненая задача в программировании. Во всех языках существуют готовые решения для этой задачи, и Go — не исключение. Стандартный пакет sort предоставляет функции для сортировки:

nums := []int{2,1,6,5,3,4}

sort.Slice(nums, func(i, j int) bool {
    return nums[i] < nums[j]
})

fmt.Println(nums) // [1 2 3 4 5 6]

Рассмотрим функцию Slice(x interface{}, less func(i, j int) bool). В описании функции присутствует неизвестный тип данных interface{}. Понятие интерфейса будет рассмотренно в следующих модулях курса. Следует запомнить, что пустой интерфейс interface{} в Go означает тип данных, под который подходит любой другой тип. Например:

func Print(arg interface{}) {
    fmt.Println(arg)
}

func main() {
    Print("hello!")
    Print(123)
    Print([]int{1,5,10})
}

Вывод:

hello!
123
[1 5 10]

То есть в функцию Slice(x interface{}, less func(i, j int) bool) передается слайс любого типа данных, как первый аргумент. Вторым аргументом передается функция, которая сравнивает 2 индекса и определяет должен ли первый элемент по индексу i находиться перед элементом по индексу j.

"Под капотом" в функции sort.Slice используется быстрая сортировка. В пакете также присутствует сортировка вставками sort.SliceStable:

nums := []int{2,1,6,5,3,4}

sort.SliceStable(nums, func(i, j int) bool {
    return nums[i] < nums[j]
})

fmt.Println(nums) // [1 2 3 4 5 6]

Выбор алгоритма зависит от набора и размера данных, архитектуры процессора, скорости доступа к памяти, то есть от многих факторов. Для большинства стандартных случаев используется sort.Slice, пока производительность или нестабильность алгоритма не станет "узким горлышком".

Задание

Реализуйте функцию UniqueSortedUserIDs(userIDs []int64) []int64, которая возвращает отсортированный слайс, состоящий из уникальных идентификаторов userIDs. Обработка должна происходить in-place, то есть без выделения доп. памяти.


Советы


Нашли ошибку? Есть что добавить? Пулреквесты приветствуются https://github.com/hexlet-basics
Если вы столкнулись с трудностями и не знаете, что делать, задайте вопрос в нашем большом и дружном сообществе