Данная статья посвящена алгоритмам. Она основана на книге “Род Стивене. Готовые алгоритмы”. Я пытался для себя разобраться с некоторыми моментами, ну и собственно сделал этот небольшой пост.
В статье об указателях, мы вскользь упомянули о возможности сортировки массивов при помощи указателей. Но как это сделать на практике? Узнаем об этом в данной статье на принципиальном уровне.
Проблема
Итак, если сортировать напрямую – перемещая сами данные, а не указатели на них, то это явные шаги к потере производительности алгоритма. В теории, когда мы оцениваем функцией O(f(N)), мы получим тоже число шагов для данных разной тяжести так сказать, для данных разного размера, занимаемого в памяти, а на практике – нашему компьютерному другу, возможно придется при сортировке таскать не кирпичи, а вагоны, образно выражаясь, то есть на данные по 4 байта а по несколько мегабайт.
Какой же выход?
-создать массив указателей на данные
-отсортировать указатели, с помощью значений в соответствующих данных
Род Стивене предлагает в книге вот такой пример
Пусть у нас есть такая структура данных
|
1 2 3 4 5 6 7 8 9 10 11 |
type PEmployee=^TEmployee; TEmployee = record ID:integer; LastName:string; FirstName:string; // Other fields... end; |
Разместим их в массиве и проделаем следующее
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
var EmployeeData: array [1..10000] of TEmployee; // Объявили массив PArrayTEmployee: array [1..10000] of PEmployee; //Массив указателей ... //Заполнили массив EmployeeData какими-то данными ... //Заполняем массив указателей, например так... for i := 1 to 10000 do PArrayTEmployee[i] := @EmployeeData[i] ; //Далее сортируем любым способом по любому полю, например, по ID with PArrayTEmployee[i].ID do someSorting... .... //Когда отсортировали можем обращаться к элементам отсортированного массива //например так... ^PArrayTEmployee[1] //Это будет первый элемент отсортированного массива. |
Заметьте, что сами данные остались на том же месте – отсортировали только массив указателей, чем сильно облегчили жизнь нашему компьютерному другу.
Если нужно сортировать несколькими методами – под каждый из них можно создать свой индексный массив, например так…
|
1 2 3 4 |
PArrayTEmployee_SortMethod1: array [1..10000] of PEmployee; PArrayTEmployee_SortMethod2: array [1..10000] of PEmployee; PArrayTEmployee_SortMethod3: array [1..10000] of PEmployee; PArrayTEmployee_SortMethod4: array [1..10000] of PEmployee; |
В этой статье мы рассмотрели общий принцип сортировки массивов при помощи указателей.