Оригінал статті знайдете за адресою http://www.efgh.com/software/zsort.htm

Мова:

С

Автор:

Філіп Дж. Ердельскі

Дата:

10 березня 2001 р

Використання:

Публічний домен; немає обмежень на використання

Портативність:

Будь-який компілятор C

Ключові слова:

Сортування

Анотація:

Досить загальний пакет для сортування довільних елементів, що мають однаковий розмір, використовуючи сортування злиття в пам’яті та сортування файлів, коли пам’ять недостатня.

Джерело:

zsort.txt

Зміст

  1. Вступ
  2. Сортування
  3. Пошук дублікатів
  4. Підрахунок відмінних предметів
  5. Підрахунок частот елемента
  6. Стабільні сорти
  7. Послідовне замовлення
  8. Модифікації

 1. Введення

Я написав багато пакетів сортування. Я називаю це «ZSORT» в надії, що це буде останній пакет, який я коли-небудь повинен писати. 😉

 

Він обробляє предмети абсолютно довільного характеру, за винятком того, що всі вони мають однаковий розмір.

Він використовує алгоритм сортування поєднань, який є нерекурсивним і порядку NlogN у всіх випадках.

Це може усунути дублікати елементів під час сортування, якщо вказано цю опцію.

Це може бути перервано, якщо виявлено певний користувачем стан при порівнянні двох елементів.

Вона досить ефективна у використанні ресурсів. Малі сорти можна зробити у пам’яті.

Він використовує тимчасові файли для обробки великих видів.

У пакеті використовується лічильник типу «unsigned long» для підрахунку елементів у тимчасових файлах, і він буде невдало невизначеною, якщо лічильник переповнюється.

 2. Сортування

Пакет складається з файлу заголовка ZSORT.H, який повинен бути включений у кожен модуль вихідного коду, який використовує пакет, та модуль вихідного коду ZSORT.C, який повинен бути скомпільований та пов’язаний з результуючою програмою. Він написаний у C, але його можна викликати з C або C ++. Джерельний файл ZSORT.TXT містить обидва файли; вам доведеться їх розділити. Файл ZSORT.C також містить програму тестування, яку потрібно видалити перед використанням пакета для інших цілей.

 

Процес сортування починається з наступного виклику функції, який виділяє деяку необхідну пам’ять і повертає ручку для передачі інших функцій пакунку:

h = ZsortOpen (розмір, порівняння, пам’ять, покажчик)
непідписаний розмір розмір елементів для сортування, в байтах (всі елементи повинні бути однакового розміру)
Порівняти ZSORTCOMPARE функція порівняння, як описано нижче
непідписана пам’ять максимальна кількість предметів для сортування у пам’яті
порожній * покажчик користувацький покажчик, який буде переданий до порівняння функція
ZSORT h ручка для передачі інших функцій, або NULL якщо операція не працює через брак пам’яті

Функція порівняння визначається наступним чином:

n = порівняти (p, q, покажчик);
void * p покажчик на перший елемент
void * q покажчик на другий елемент
порожній * покажчик покажчик передано ZsortOpen ()
int n ZCOMPABORT, якщо сортування буде перервано
ZCOMPDUPP, якщо * p та * q є дублікатами, * p до бути збережений і * q повинен бути вилучений,
ZCOMPDUPQ, якщо * p та * q є дублікатами, * q до бути збереженим і * p потрібно видалити,
від’ємне значення, крім вищесказаного, якщо * p повинен передувати * q у відсортованому порядку,
позитивне значення, відмінне від вищевказаного, якщо * p це слідувати * q сортований порядок,
нуль, якщо відносне положення * p і * q в відсортований порядок не вказаний

Якщо функція порівняння повертає ZCOMPDUPP або ZCOMPDUPQ для будь-якої пари елементів, вона не повинна повертати 0 для будь-якої іншої пари елементів (і навпаки).

Функція порівняння повинна визначати послідовне упорядкування всіх предметів. Детальніше в розділі 7 нижче.

Функція порівняння може вносити зміни до частин елементів, що не беруть участь у порівнянні. Ці зміни з’являться в елементах, коли вони завантажуються.

Потім елементи надсилаються по одному за раз на наступну функцію:

result = ZsortSubmit (h, p);
ZSORT h; ручка повернута успішним дзвінком ZsortOpen ()
const void * p;

int результат

вказівник на пункт, що підлягає подачі; елемент єскопійовано до внутрішнього буфера, тому його не потрібно залишатиметься дійсним після повернення цієї функції
0 успішна робота
ZSORTABORT Операція перервана
ZSORTMEMFAIL Збій виділення пам’яті
ZSORTFILEERR Помилка тимчасового файлу

У пакеті найменше виділяються предмети в пам’яті. Коли перевищено максимум, зазначений у дзвінку ZsortOpen, він записує перевищення елементів у тимчасові файли. Якщо аргумент «пам’ять» для ZsortOpen дуже великий, подання окремого елемента може призвести до значної затримки, поки блок буде сортуватися, перш ніж буде записаний в тимчасовий файл.

Коли всі елементи були надіслані, для вилучення елементів у відсортованому порядку послідовно називається така функція:

result = ZsortRetrieve (h, p);
ZSORT h; ручка повернута успішним дзвінком ZsortOpen ()
void * p; покажчик на буфер для отримання відновленого елемента; повинен бути виділений абонентом
int результат; 0 успішна робота
ZSORTEND більше елементів
ZSORTABORT Операція перервана
ZSORTMEMFAIL Збій виділення пам’яті
ZSORTFILEERR Помилка тимчасового файлу

Останній виклик ZsortRetrieve () повертає ZSORTEND як функціональне значення і не повертає жодного елемента.

Перший виклик ZsortRetrieve () зазвичай робить більшу частину фактичного сортування, тому він може не повернутися швидко.

Не потрібно завантажувати всі відсортовані елементи. Якщо ZsortSubmit () ще раз викликається до того, як всі елементи будуть завантажені, тоді всі інші елементи будуть втрачені та розпочнеться новий сорт.

Якщо ZsortRetrieve () знову викликається після повернення ZSORTEND, він продовжує повертати ZSORTEND.

Для додаткових сортів на інших блоках елементів з однаковим розміром, функцією порівняння та іншими параметрами просто повторюйте виклики з ZsortSubmit () та ZsortRetrieve (). Блоки пам’яті та тимчасові файли, створені для першого сортування, будуть повторно використані перед тим, як інші будуть розподілені.

Нарешті, щоб випустити всі блоки пам’яті та закрити тимчасові файли, викликайте наступну функцію (якщо це не зробить, це може призвести до витоку ресурсу):

ZsortClose (h, стерти);
ZSORT h; ручка повернута успішним дзвінком                         ZsortOpen ()
int стираю; ненульовий (true), якщо пам’ять блокується і тимчасово Файли повинні бути стерті перед нимизвільняються або видаляються

Якщо ZsortSubmit () або ZsortRetrieve () повертає помилку (ZSORTABORT, ZSORTMEMFAIL або ZSORTFILEERR), сортування має бути відмінено, а ZsortClose () слід викликати. Невиконання цього може призвести до витоку ресурсів.

Пакет викликає наступні стандартні функції бібліотеки C:

fclose() fread() malloc() tmpfile()
fgetc() free() memcpy()
fputc() fwrite() rewind()

Пакет безпечний для потоку в обмеженій кількості. Різні потоки можуть виконувати різного роду різними ручками без перешкод, за умови, що функція бібліотеки, яку він виконує, безпечна для потоку.

3. Пошук дублікатів

Щоб визначити, чи містить набір елементів дублікати, просто напишіть функцію порівняння, щоб він припинив сортування, коли йому пропонується порівнювати дублікати, НЕ повертає 0 для недискетних, а також реалізує незмінний штампування в інших відношеннях. (Див. Розділ 7 нижче.)

Це, загалом, швидше, ніж сортування набору, а потім вивчення результату, щоб побачити, чи є копії двох послідовних елементів. Але це завжди працює?

Функція порівняння називається лише приблизно 0,5 * N * logN разів, хоча існують N * (N-1) пар елементів. Як ми знаємо, що буде запропоновано порівняти дублікати?

Припустимо, з метою протиріччя, що існує підмножина з двох або більше дубльованих елементів, однак функція порівняння не викликається для будь-якої пари в підмножині, але лише для пар, що складають щонайменше один елемент поза піднабору. Тоді уявіть два злегка різних набори, в яких елементи у підмножині не зовсім ідентичні, але все ж стоять в однакових відносинах з елементами поза підмножини. Наприклад:

Old set: 9, 1, 2, 3, 4,   4,   4,   5, 6, 7
New set: 9, 1, 2, 3, 4.1, 4.2, 4.3, 5, 6, 7
New set: 9, 1, 2, 3, 4.2, 4.1, 4.3, 5, 6, 7

Тепер сортуйте два нових набори з таким же алгоритмом. Оскільки елементи в підмножині ніколи не порівнюються один з одним, сортування обробляє їх однаково. Але це призведе хоча б до одного з нових наборів до неправильного порядку. Це протиріччя, яке ми шукали.

4. Підрахунок відмінних предметів

Щоб визначити кількість окремих елементів у наборі, просто напишіть функцію порівняння, щоб відмовитися від дублікатів. Потім відправте всі елементи і підрахуйте, скільки разів ZsortRetrieve () повертає 0.

5. Розрахунок частоти елементів

Припустимо, нам потрібен список частот набору предметів; тобто список окремих елементів, а також кількість разів, коли кожен відображається в наборі. Ми могли просто сортувати набір, а потім пройти через результати. Проте існує більш ефективний спосіб, особливо якщо кількість окремих предметів набагато менше, ніж кількість предметів.

Об’єднайте кожен елемент з підрахунком, який ініціюється до 1, коли елемент подано. Коли функція порівняння знаходить дублікати елементів, дозвольте йому додавати кількість елементів у елементі, які слід відхилити, до рахунку в елементі, який потрібно зберегти. Отриманий відсортований набір — це бажаний список частот.

6. Стабільні сорти

Стабільний сорт — це такий, який зберігає відносне положення елементів, які функція порівняння не оцінює.

Як і раніше, ZSORT не є стабільним. Якщо бажаний стабільний сорт, до кожного елемента перед його поданням ZsortSubmit () слід додавати зростаючий серійний номер. Тоді функція порівняння може оцінювати порівнювані позиції за їхніми серійними номерами.

7. Послідовне замовлення

Функція порівняння повинна визначати послідовне упорядкування предметів. Усі найпоширеніші упорядкування (алфавітний, чисельний, хронологічний та ін.) Є послідовними. Проте в окремих випадках може знадобитися вивчити всі відповідні правила.

Як зазначено вище, якщо функція порівняння повертає ZCOMPDUPP або ZCOMPDUPQ для будь-якої пари елементів, вона не повинна повертати 0 для будь-якої іншої пари елементів (і навпаки).

Два пункти, які ідентичні або для яких функція порівняння повертає 0, ZCOMPDUPP або ZCOMPDUPQ називаються еквівалентними. Це співвідношення має бути математично рівномірним співвідношенням; тобто вона має бути рефлексивною, симетричною та транзитивною:

(Reflexive) Будь-який елемент еквівалентний самій.
(Симетричний) Якщо А еквівалентно B, то B еквівалентно А.
(Транзитивний) Якщо А еквівалентне В і В еквівалентно С, то А еквівалентно С.
Для повернення інших значень, функція порівняння повинна відповідати цим умовам:

Якщо порівняти (p, q, покажчик)> 0, то порівняйте (q, p, покажчик) <0, і навпаки. (Транзитивний) Якщо порівняти (p, q, покажчик)> 0 і порівняти (q, r, покажчик)> 0, то порівняйте (p, r, покажчик)> 0.
Якщо порівняти (p, q, покажчик)> 0, * p еквівалентно * pp, а * q еквівалентно * qq, тоді порівняйте (pp, qq, pointers)> 0.

8. Модифікації

Якщо визначення ZCOMPDUPP та ZCOMPDUPQ вилучено з ZSORT.H, функція видалення дублювання пакунка буде вимкнена, а код, який його реалізує, буде видалено.

Аналогічним чином, якщо визначення ZCOMPABORT буде видалено з ZSORT.H, функція переривання пакету буде вимкнена, а код, який його реалізує, буде видалено.

Необхідно стежити, щоб спеціальні значення ZCOMPABORT, ZCOMPDUPP та ZCOMPDUPQ не були повернуті внаслідок регулярного порівняння. У файлі ZSORT.H ці параметри встановлюються в граничні значення в діапазоні типу «int» для 32-бітних машин. Якщо ви збираєте пакет для 16-розрядної машини, вам доведеться змінити ці значення.

Стандартні функції зіставлення strcmp (), stricmp (), memcmp () та memicmp () зазвичай повертають лише значення в деякому досить обмеженому діапазоні, як правило, між -256 та 256 включно. Однак це не цілком гарантовано. Для абсолютної переносимості вам, можливо, доведеться уникати використання бібліотечних версій цих функцій і використовувати замінники, такі як:

int strcmp(const char *p, const char *q)     {       int n;       while (1)       {         n = * (unsigned char *) p — * (unsigned char *) q;         if (n != 0 || *p == 0)           break;         p++;         q++;       }       return n;     }      int stricmp(const char *p, const char *q)     {       int n;       while (1)       {         n = toupper(* (unsigned char *) p) —           toupper(* (unsigned char *) q);         if (n != 0 || *p == 0)           break;         p++;         q++;       }       return n;     }      int memcmp(const void *p, const void *q, unsigned size)     {       int n = 0;       unsigned i;       for (i = 0; i < size; i++)       {         n = ((unsigned char *) p)[i] — ((unsigned char *) q)[i];         if (n != 0)           break;       }       return n;     }      int memicmp(const void *p, const void *q, unsigned size)     {       int n = 0;       unsigned i;       for (i = 0; i < size; i++)       {         n = toupper(((unsigned char *) p)[i]) —           toupper(((unsigned char *) q)[i]);         if (n != 0)           break;       }       return n;     }

Крім того, ви можете використовувати функцію звичайної бібліотеки та поставити тест після нього, як це:

     n = strcmp(p, q);     if (n < 0)       n = -1;

Це працює тому, що значення ZCOMPABORT, ZCOMPDUPP та ZCOMPDUPQ всі негативні.

Written by