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://ttttt.me/HexletLearningBot. Там можно задать любой вопрос и повлиять на проект

Упражнение не проходит проверку — что делать? 😶

Если вы зашли в тупик, то самое время поговорить с нашим асситентом Тота во вкладке "Обсуждение". Как правильно задать вопрос:

В моей среде код работает, а здесь нет 🤨

Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.

Мой код отличается от решения учителя 🤔

Это нормально 🙆, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи. В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.

Прочитал урок — ничего не понятно 🙄

Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в обратной связи нашего сообщества

Нашли ошибку? Есть что добавить? Пулреквесты приветствуются

Привет! Я Тота и моя задача помочь в обучении. Чтобы активировать меня, нужно зарегистрироваться или залогиниться, если у вас уже есть аккаунт

Loading...

Ваше упражнение проверяется по этим тестам

1package solution
2
3import (
4	"testing"
5
6	"github.com/stretchr/testify/assert"
7)
8
9func TestUniqueSortedUserIDs(t *testing.T) {
10	a := assert.New(t)
11	a.Equal([]int64{}, UniqueSortedUserIDs([]int64{}))
12	a.Equal([]int64{10}, UniqueSortedUserIDs([]int64{10}))
13	a.Equal([]int64{55}, UniqueSortedUserIDs([]int64{55, 55}))
14	a.Equal([]int64{22, 33, 55}, UniqueSortedUserIDs([]int64{55, 55, 33, 22}))
15	a.Equal([]int64{2, 33, 55, 88, 103}, UniqueSortedUserIDs([]int64{55, 2, 88, 33, 2, 2, 55, 103, 33, 88}))
16}
17

Решение учителя откроется через:

20:00
waiting_clock