CSharp_Practice/Tasks/RadixSortTask.txt at main · VladimirVaize/CSharp_Practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
Система генерации и сортировки подземелья

Контекст

Ты разрабатываешь roguelike RPG. В игре есть подземелья, которые генерируются процедурно.
Каждая комната в подземелье имеет свои параметры, и игрок может открыть карту,
на которой комнаты отсортированы по глубине (уровню сложности).

Геймдизайнер хочет, чтобы система работала быстро, даже если в подземелье будет до 100 000 комнат.
Обычные сортировки (O(n log n)) работают, но геймдизайнер слышал про линейную сортировку
и хочет использовать её для максимальной производительности.

Твоя задача — реализовать сортировку комнат подземелья по их глубине с помощью поразрядной сортировки (Radix sort).

Что нужно сделать
1. Создай класс Room
   У комнаты должны быть следующие поля/свойства:
   - int Id - Уникальный идентификатор комнаты (генерируется автоматически)
   - string Name - Название комнаты (например, "Тронный зал", "Подземная река")
   - int Depth - Глубина комнаты (уровень сложности). Значение от 0 до 9999.
   - int EnemyCount - Количество врагов в комнате (для дополнительного контекста)
   - bool IsVisited - Посетил ли игрок эту комнату

2. Создай класс Dungeon
   Класс должен содержать:
   - List<Room> или массив Room[] для хранения комнат
   - Метод AddRoom(Room room) для добавления комнаты
   - Метод SortRoomsByDepthRadix() — главный метод, который сортирует комнаты по полю Depth
     с помощью поразрядной сортировки (LSD - Least Significant Digit)

3. Реализуй поразрядную сортировку
   Особенности:
   - Глубина комнаты (Depth) может быть от 0 до 9999.
   - Нужно отсортировать сами объекты Room, а не только числа.
   - Используй LSD Radix Sort (сортировка от младшего разряда к старшему).
   - Вспомогательные методы:
     - GetDigit(int number, int digitPosition) — получение цифры в определенном разряде
       (единицы, десятки, сотни, тысячи).
     - Стабильная сортировка по разряду с использованием дополнительного массива
       (Counting sort для цифр 0-9).

4. Добавь бенчмарк для сравнения
   Создай метод, который:
   - Генерирует подземелье с 20 000 комнат со случайной глубиной (0-9999).
   - Сортирует комнаты с помощью:
     - Твоей Radix Sort
     - Стандартного List.Sort() (для сравнения)
   - Замеряет время выполнения обоих методов и выводит в консоль.

5. Требования к коду
   - Обобщения (Generics): Метод сортировки должен быть максимально переиспользуемым.
     Хорошо, если получится написать обобщенный метод RadixSort<T>(T[] array, Func<T, int> keySelector),
     где ключ для сортировки выбирается через делегат.
   - Делегаты: Используй делегаты (встроенные Func, Action) для передачи ключа сортировки
     и для callback-уведомлений.
   - События: Добавь события в класс Dungeon:
     - RoomAdded — возникает при добавлении новой комнаты.
     - SortCompleted — возникает после завершения сортировки (передает время выполнения).
   - Обработка ошибок: Добавь проверки на null и пустую коллекцию.
   - Сериализация: Добавь метод SaveToJson(string path),
     который сохраняет отсортированный список комнат в JSON-файл (используй System.Text.Json).
     В названии файла укажи дату и время сортировки.
   - Работа с файловой системой: Создавай папку Saves в директории приложения, если её нет.
   - IDisposable: Если потребуется работа с файловыми потоками — реализуй освобождение ресурсов.

6. Демонстрация в Main()
   Создай консольное приложение, которое:
   1. Генерирует подземелье с 20 комнатами (для наглядного вывода).
   2. Выводит комнаты до сортировки.
   3. Сортирует с помощью Radix sort.
   4. Выводит комнаты после сортировки.
   5. Выполняет бенчмарк с 20 000 комнат.
   6. Сохраняет результат сортировки в JSON-файл.


Пример вывода

=== Генерация подземелья (20 комнат) ===
До сортировки:
1. Тронный зал (Глубина: 845, Врагов: 12)
2. Подземная река (Глубина: 23, Врагов: 5)
3. Забытая гробница (Глубина: 1247, Врагов: 8)
...

После сортировки (Radix sort):
1. Подземная река (Глубина: 23, Врагов: 5)
2. Тронный зал (Глубина: 845, Врагов: 12)
3. Забытая гробница (Глубина: 1247, Врагов: 8)
...

=== Бенчмарк (20 000 комнат) ===
Radix sort: 00:00:00.0234
List.Sort:  00:00:00.0341

Сортировка завершена! Результат сохранен в Saves/dungeon_2025-03-23_15-30-45.json


Бонусное задание (если будет легко)
   Добавь возможность сортировки по нескольким ключам:
   - Сначала по глубине (Depth)
   - Затем по количеству врагов (EnemyCount) внутри одинаковой глубины

Для этого нужно модифицировать Radix sort, чтобы она учитывала составной ключ.
Можно использовать сдвиги битов или сортировку от младшего ключа к старшему.


Подсказки
   Получение цифры в разряде:
   - return (number / (int)Math.Pow(10, digitPosition)) % 10;