Алгоритмы. Сортировка. Таблицы указателей

Данная статья посвящена алгоритмам. Она основана на книге “Род Стивене. Готовые алгоритмы”.  Я пытался для себя разобраться с некоторыми моментами, ну и собственно сделал этот небольшой пост.

В статье об указателях, мы вскользь упомянули о возможности сортировки массивов при помощи указателей. Но как это сделать на практике? Узнаем об этом в данной статье на принципиальном уровне.

Проблема

Итак, если сортировать напрямую – перемещая сами данные, а не указатели на них, то это явные шаги к потере производительности алгоритма.  В теории, когда мы оцениваем функцией O(f(N)), мы получим тоже число шагов для данных разной тяжести так сказать, для данных разного размера, занимаемого в памяти, а на практике – нашему компьютерному другу, возможно придется при сортировке таскать не кирпичи, а вагоны, образно выражаясь, то есть на данные по 4 байта а по несколько мегабайт.

Какой же выход?

-создать массив указателей на данные

-отсортировать указатели, с помощью значений в соответствующих данных

Род Стивене предлагает в книге вот такой пример

Пусть у нас есть такая структура данных

Разместим их в массиве и проделаем следующее

Заметьте, что сами данные остались на том же месте – отсортировали только массив указателей, чем сильно облегчили жизнь нашему компьютерному другу.

Если нужно сортировать несколькими методами – под каждый из них можно создать свой индексный массив, например так…

В этой статье мы рассмотрели общий принцип сортировки массивов при помощи указателей.

by Stanislav_Panteleev