// Done by TheTutor -- 12/16/01
// Перевод © 2005 Евгений Казеко
// www.gamecoder.kazeko.com
// evgeniy@kazeko.com
/*
Эта обучалка объясняет функцию qsort() - отличную функцию для сортировки массивов.
Некоторые не используют qsort(), потому что нечетко представляют, как ее использовать.
Поэтому обучалка познакомит вас с qsort(), если вы не знаете о ней, и покажет,
как правильно ее использовать.
Начнем сортировку.
*/
#include <stdlib.h> // Подключаем этот файл чтобы использовать qsort() и rand()
#include <stdio.h>
#define MAX 10 // Максимальное число элементов массива
// Эта функция печатает массив целых чисел.
// "num" это количество целых чисел, которые следует напечатать.
void printArray(int*, int num);
/* Это первая функция, которая работает с qsort() -- в qsort() требуется передать
указатель на "функцию сравнения" -- Это должна быть функция, которая СРАВНИВАЕТ
два элемента в массиве, который мы будем сортировать. Возвращаемые значения
работают следующим образом:
Возвращается число меньше нуля, если element1 меньше чем element2.
Возвращается 0, если element1 равен element2.
Возвращается число больше нуля, если element1 больше element2
Если вы посмотрите на объявление функции, вы заметите, что мы указываем
для элементов 1 и 2 тип "const void*". -- Причиной, по которой мы ОБЯЗАНЫ
передавать const void*, является то, что qsort() может сортировать данные
ЛЮБОГО типа, и ее прототип ожидает от вас передачи данных таким образом.
Кроме того, передавая переменные "const" мы гарантируем, что compare()
НЕ изменит то, что мы передаем (это хорошо, потому что мы хотим отсортированный,
а не измененный массив). Когда мы будем описывать функцию, мы преобразуем тип
данных в "int", чтобы мы могли правильно написать ее код.
*/
int compare(const void *element1, const void *element2);
// В main мы создадим массив целых чисел, затем напечатаем его на экран, отсортируем его,
// затем напечатаем сортированный массив на экран и завершим программу.
int main()
{
// Сначала нам нужен массив
int array[MAX] = {0}; // Обнуляем массив
int i; // Счетчик цикла
for(i = 0; i < MAX; i++)
array[i] = rand()%500; // Заполним массив случайными числами
printArray(array,MAX);
// А теперь qsort() по параметрам:
// array -- Это указатель на массив данных для сортировки. Еще раз - это
// может быть массив данных float, double, структур, которые вы определяете,
// или каких угодно других типов.
// MAX -- Это количество элементов массива
// sizeof(int) -- Это "размер элемента массива в байтах" -- qsort() нужно знать
// размер "типа переменных", которые вы передаете.
// Если передается массив переменных float, нужно указать sizeof(float).
// compare -- Это написанная нами функция, которая говорит qsort() как распределять
// данные -- ее объявление (в прототипе qsort() - прим.перев.) выглядит вот так:
// int (__cdecl *compare )(const void *elem1, const void *elem2)
// Как видите, довольно устрашающе :)
// (обычный указатель на функцию, см. предыдущую обучалку - прим.перев.)
qsort(array,MAX,sizeof(int),compare); // Сортируем массив
printArray(array,MAX);
return 0;
}
// Печатаем массив -- "num" указывает, сколько чисел в массиве
void printArray(int *aaa, int num)
{
int i = 0; // Индекс и счетчик цикла
for(; i < num; i++)
printf("%d ",aaa[i]);
printf("\n\n"); // Несколько пробелов
}
// А вот и функция сравнения -- Как видите, она очень простая :)
// Как вы помните, мы возвращаем отрицательное число, если element1 < element2
// положительное число, если element1 > element2
// и ноль, если element1 == element2
int compare(const void *element1, const void *element2)
{
/* И что означают все эти () и * ???
Сперва посмотрим вот на это:
*(int*)element1
"(int*)" означает "void*, который передали, на самом деле int*"
Затем, символ "*" слева от "(int*)" означает преобразование указателя
в число, на которое он указывает. ("Dereference the pointer").
То же самое применимо и к "element2". -- Таким образом, когда все
это будет проделано, вы получите целочисленные значения, которые
хранятся в памяти по адресам, на которые указывают element1 и element2,
и затем вы возвращаете значение, получаемое вычитанием этих чисел. -- Вот и все :)
*/
return *(int*)element1 - *(int*)element2;
}
/*
Вопросы и ответы ---
Q: Обязательно ли называть функцию сравнения "compare"?
A: Нет -- Назовите ее так, как вам нравится :)
Q: Нужно ли объявлять функцию, используя const void*? -- То есть
если я знаю, что я передаю целые числа, могу ли я сделать следующее:
int compare(const int *e1, const int *e2); ?
A: Не можете -- Нужно обязательно использовать const void*
Q: Быстрая ли функция qsort()?
A: Да, qsort означает "quick sort" (быстрая сортировка)
Q: Что делать, если мне нужно сортировать от большего к меньшему?
A: Просто поменяйте местами "element1" и "element2" в теле функции compare
*/
/*
| TheTutor
| thetutor@gametutorials.com
| © 2001-2002 GameTutorials
*/
// Перевод © 2005 Евгений Казеко
// www.gamecoder.kazeko.com
// evgeniy@kazeko.com
|
