Бесплатный курс по 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) передается слайс любого типа данных, как первый аргумент. Вторым аргументом передается функция, которая берет элементы по индексу и определяет должен ли элемент по индексу 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
Если вы столкнулись с трудностями и не знаете, что делать, задайте вопрос в нашем большом и дружном сообществе