sort.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538
  1. /*!
  2. Temelia - Sorting algorithms implementation source file.
  3. Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
  4. @author Dascalu Laurentiu
  5. This program is free software; you can redistribute it and
  6. modify it under the terms of the GNU General Public License
  7. as published by the Free Software Foundation; either version 3
  8. of the License, or (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program; if not, write to the Free Software
  15. Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16. */
  17. #include "include/sort.h"
  18. #include <stdlib.h>
  19. #include <string.h>
  20. // Private functions.
  21. // Merge sort.
  22. static void _merge_sort(void *data, int begin, int end, void *key_at(
  23. void *data, int index), void set_key_at(void *data, int index,
  24. void *new_value), int compare(void *x, void *y, void *context),
  25. void *context);
  26. static void _merge(void *data, int begin, int middle, int end, void *key_at(
  27. void *data, int index), void set_key_at(void *data, int index,
  28. void *new_value), int compare(void *x, void *y, void *context),
  29. void *context);
  30. // Quick sort.
  31. static void _quick_sort(void *data, int begin, int end, void *key_at(
  32. void *data, int index), void set_key_at(void *data, int index,
  33. void *new_value), int compare(void *x, void *y, void *context),
  34. void *context);
  35. static int _partition(void *data, int begin, int end, void *key_at(void *data,
  36. int index), void set_key_at(void *data, int index, void *new_value),
  37. int compare(void *x, void *y, void *context), void *context);
  38. // Heap sort.
  39. static void _heapify(void *data, int n, void *key_at(void *data, int index),
  40. void set_key_at(void *data, int index, void *new_value), int compare(
  41. void *x, void *y, void *context), void *context);
  42. static void _sift_down(void *data, int begin, int end, void *key_at(void *data,
  43. int index), void set_key_at(void *data, int index, void *new_value),
  44. int compare(void *x, void *y, void *context), void *context);
  45. // Radix sort.
  46. static int _digit(int x, int y);
  47. static int _power(int x);
  48. int is_sorted(void *data, int size, void *(*key_at)(void *data, int index),
  49. int (*compare)(void *x, void *y, void *context), void *context)
  50. {
  51. int i;
  52. _ASSERT(data, ==, NULL, NULL_POINTER, -1);
  53. _ASSERT(compare, ==, NULL, NULL_POINTER, -1);
  54. for (i = 0; i < size - 1; i++)
  55. if (compare(key_at(data, i), key_at(data, i + 1), context) > 0)
  56. return 0;
  57. return 1;
  58. }
  59. void bubble_sort(void *data, int size, void *(*key_at)(void *data, int index),
  60. void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
  61. void *x, void *y, void *context), void *context)
  62. {
  63. void *aux;
  64. int ordonat, i;
  65. _ASSERT(data, ==, NULL, NULL_POINTER,);
  66. _ASSERT(compare, ==, NULL, NULL_POINTER,);
  67. _ASSERT(size, <=, 1, INVALID_INPUT,);
  68. do
  69. {
  70. ordonat = 0;
  71. for (i = 0; i < size - 1; i++)
  72. {
  73. if (compare(key_at(data, i), key_at(data, i + 1), context) > 0)
  74. {
  75. aux = key_at(data, i);
  76. set_key_at(data, i, key_at(data, i + 1));
  77. set_key_at(data, i + 1, aux);
  78. ordonat = 1;
  79. }
  80. }
  81. } while (ordonat);
  82. }
  83. void insertion_sort(void *data, int size, void *(*key_at)(void *data, int index),
  84. void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
  85. void *x, void *y, void *context), void *context)
  86. {
  87. int i, j;
  88. void *key, *aux;
  89. _ASSERT(data, ==, NULL, NULL_POINTER,);
  90. _ASSERT(compare, ==, NULL, NULL_POINTER,);
  91. _ASSERT(size, <=, 1, INVALID_INPUT,);
  92. for (j = 1; j < size; j++)
  93. {
  94. key = key_at(data, j);
  95. i = j - 1;
  96. while (i >= 0 && compare(key_at(data, i), key, context) > 0)
  97. {
  98. aux = key_at(data, i);
  99. set_key_at(data, i, key_at(data, i + 1));
  100. set_key_at(data, i + 1, aux);
  101. i--;
  102. }
  103. }
  104. }
  105. void merge_sort(void *data, int size, void *(*key_at)(void *data, int index),
  106. void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
  107. void *x, void *y, void *context), void *context)
  108. {
  109. _ASSERT(data, ==, NULL, NULL_POINTER,);
  110. _ASSERT(compare, ==, NULL, NULL_POINTER,);
  111. _ASSERT(size, <=, 1, INVALID_INPUT,);
  112. _merge_sort(data, 0, size - 1, key_at, set_key_at, compare, context);
  113. }
  114. void quick_sort(void *data, int size, void *(*key_at)(void *data, int index),
  115. void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
  116. void *x, void *y, void *context), void *context)
  117. {
  118. _ASSERT(data, ==, NULL, NULL_POINTER,);
  119. _ASSERT(compare, ==, NULL, NULL_POINTER,);
  120. _ASSERT(size, <=, 1, INVALID_INPUT,);
  121. _quick_sort(data, 0, size - 1, key_at, set_key_at, compare, context);
  122. }
  123. void selection_sort(void *data, int size, void *(*key_at)(void *data, int index),
  124. void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
  125. void *x, void *y, void *context), void *context)
  126. {
  127. int i, j, min;
  128. void *aux;
  129. _ASSERT(data, ==, NULL, NULL_POINTER,);
  130. _ASSERT(compare, ==, NULL, NULL_POINTER,);
  131. _ASSERT(size, <=, 1, INVALID_INPUT,);
  132. for (i = 0; i < size - 1; i++)
  133. {
  134. min = i;
  135. for (j = i + 1; j < size; j++)
  136. if (compare(key_at(data, j), key_at(data, min), context) < 0)
  137. min = j;
  138. aux = key_at(data, i);
  139. set_key_at(data, i, key_at(data, min));
  140. set_key_at(data, min, aux);
  141. }
  142. }
  143. void shell_sort(void *data, int size, void *(*key_at)(void *data, int index),
  144. void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
  145. void *x, void *y, void *context), void *context)
  146. {
  147. int i, j, increment;
  148. void *temp;
  149. _ASSERT(data, ==, NULL, NULL_POINTER,);
  150. _ASSERT(compare, ==, NULL, NULL_POINTER,);
  151. _ASSERT(size, <=, 1, INVALID_INPUT,);
  152. increment = size / 2;
  153. while (increment > 0)
  154. {
  155. for (i = increment; i < size; i++)
  156. {
  157. j = i;
  158. temp = key_at(data, i);
  159. while ((j >= increment) && (compare(key_at(data, j - increment),
  160. temp, context) > 0))
  161. {
  162. set_key_at(data, j, key_at(data, j - increment));
  163. j -= increment;
  164. }
  165. set_key_at(data, j, temp);
  166. }
  167. if (increment == 2)
  168. increment = 1;
  169. else
  170. increment = (int) (increment / 2.2);
  171. }
  172. }
  173. void heap_sort(void *data, int size, void *(*key_at)(void *data, int index),
  174. void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
  175. void *x, void *y, void *context), void *context)
  176. {
  177. int end;
  178. void *aux;
  179. _ASSERT(data, ==, NULL, NULL_POINTER,);
  180. _ASSERT(compare, ==, NULL, NULL_POINTER,);
  181. _ASSERT(size, <=, 1, INVALID_INPUT,);
  182. _heapify(data, size, key_at, set_key_at, compare, context);
  183. end = size - 1;
  184. while (end >= 0)
  185. {
  186. if (compare(key_at(data, 0), key_at(data, end), context) > 0)
  187. {
  188. aux = key_at(data, 0);
  189. set_key_at(data, 0, key_at(data, end));
  190. set_key_at(data, end, aux);
  191. end--;
  192. }
  193. else
  194. end--;
  195. _sift_down(data, 0, end, key_at, set_key_at, compare, context);
  196. }
  197. }
  198. void gnome_sort(void *data, int size, void *(*key_at)(void *data, int index),
  199. void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
  200. void *x, void *y, void *context), void *context)
  201. {
  202. int i, j;
  203. void *aux;
  204. _ASSERT(data, ==, NULL, NULL_POINTER,);
  205. _ASSERT(compare, ==, NULL, NULL_POINTER,);
  206. _ASSERT(size, <=, 1, INVALID_INPUT,);
  207. i = 1;
  208. j = 2;
  209. while (i < size)
  210. {
  211. if (compare(key_at(data, i - 1), key_at(data, i), context) < 0)
  212. {
  213. i = j;
  214. j++;
  215. }
  216. else
  217. {
  218. aux = key_at(data, i - 1);
  219. set_key_at(data, i - 1, key_at(data, i));
  220. set_key_at(data, i, aux);
  221. i--;
  222. if (i == 0)
  223. i = 1;
  224. }
  225. }
  226. }
  227. void cocktail_sort(void *data, int size, void *(*key_at)(void *data, int index),
  228. void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
  229. void *x, void *y, void *context), void *context)
  230. {
  231. int buttom, top, i;
  232. void *aux;
  233. int ordonat = 1;
  234. _ASSERT(data, ==, NULL, NULL_POINTER,);
  235. _ASSERT(compare, ==, NULL, NULL_POINTER,);
  236. _ASSERT(size, <=, 1, INVALID_INPUT,);
  237. buttom = 0;
  238. top = size - 1;
  239. while (ordonat)
  240. {
  241. ordonat = 0;
  242. for (i = buttom; i < top; i++)
  243. {
  244. if (compare(key_at(data, i), key_at(data, i + 1), context) > 0)
  245. {
  246. aux = key_at(data, i);
  247. set_key_at(data, i, key_at(data, i + 1));
  248. set_key_at(data, i + 1, aux);
  249. ordonat = 1;
  250. }
  251. }
  252. top--;
  253. for (i = top; i > buttom; i--)
  254. {
  255. if (compare(key_at(data, i - 1), key_at(data, i), context) > 0)
  256. {
  257. aux = key_at(data, i);
  258. set_key_at(data, i, key_at(data, i - 1));
  259. set_key_at(data, i - 1, aux);
  260. ordonat = 1;
  261. }
  262. }
  263. buttom++;
  264. }
  265. }
  266. void radix_sort(int *data, int size, int max_digits)
  267. {
  268. queue_t Q[10];
  269. int i, j, x, *y, *aux;
  270. _ASSERT(data, ==, NULL, NULL_POINTER,);
  271. _ASSERT(max_digits, <, 0, INVALID_INPUT,);
  272. _ASSERT(size, <=, 1, INVALID_INPUT,);
  273. for (i = 0; i < 10; i++)
  274. Q[i] = queue_new(size);
  275. for (i = 0; i < max_digits; i++)
  276. {
  277. for (j = 0; j < size; j++)
  278. {
  279. x = _digit(data[j], i);
  280. y = (int *) _new(sizeof(int));
  281. *y = data[j];
  282. queue_push_back(Q[x], y);
  283. }
  284. x = 0;
  285. for (j = 0; j < 10; j++)
  286. {
  287. while (!queue_is_empty(Q[j]))
  288. {
  289. aux = (int *) queue_get_front(Q[j]);
  290. data[x++] = *aux;
  291. queue_pop_front(Q[j]);
  292. _delete(aux);
  293. }
  294. }
  295. }
  296. for (i = 0; i < 10; i++)
  297. queue_delete(Q[i]);
  298. }
  299. #include <stdio.h>
  300. void number_sort(unsigned int *data, int size, int max_value)
  301. {
  302. int i;
  303. int j;
  304. unsigned int *count;
  305. unsigned int *aux;
  306. LOGGER("[number_sort] data %p, size %d, max_value %d\n", data, size,
  307. max_value);
  308. _ASSERT(data, ==, NULL, NULL_POINTER,);
  309. _ASSERT(size, <=, 1, INVALID_INPUT,);
  310. aux = (unsigned int *) _new(size * sizeof(unsigned int));
  311. count = (unsigned int *) _new(max_value * sizeof(unsigned int));
  312. _ASSERT(aux, ==, NULL, NULL_POINTER,);
  313. _ASSERT(count, ==, NULL, NULL_POINTER,);
  314. memset(count, 0, max_value * sizeof(unsigned int));
  315. for (j = 0; j < size; j++)
  316. {
  317. if (data[j] >= (unsigned int) max_value || data[j] < 0)
  318. {
  319. LOGGER("[numer_sort] invalid input %d\n", data[j]);
  320. temelia_errno = INVALID_INPUT;
  321. return;
  322. }
  323. count[data[j]]++;
  324. }
  325. for (i = 1; i < max_value; i++)
  326. count[i] += count[i - 1];
  327. for (j = size - 1; j >= 0; j--)
  328. {
  329. aux[count[data[j]] - 1] = data[j];
  330. count[data[j]]--;
  331. }
  332. memcpy(data, aux, size * sizeof(unsigned int));
  333. _delete(aux);
  334. _delete(count);
  335. }
  336. static void _merge_sort(void *data, int begin, int end, void *key_at(
  337. void *data, int index), void set_key_at(void *data, int index,
  338. void *new_value), int compare(void *x, void *y, void *context),
  339. void *context)
  340. {
  341. int mid;
  342. if (begin < end)
  343. {
  344. mid = (begin + end) / 2;
  345. _merge_sort(data, begin, mid, key_at, set_key_at, compare, context);
  346. _merge_sort(data, mid + 1, end, key_at, set_key_at, compare, context);
  347. _merge(data, begin, mid, end, key_at, set_key_at, compare, context);
  348. }
  349. }
  350. static void _merge(void *data, int begin, int middle, int end, void *key_at(
  351. void *data, int index), void set_key_at(void *data, int index,
  352. void *new_value), int compare(void *x, void *y, void *context),
  353. void *context)
  354. {
  355. int i, j, k;
  356. void **aux;
  357. aux = (void **) _new((end - begin + 1) * sizeof(void *));
  358. i = begin;
  359. j = middle + 1;
  360. k = 0;
  361. while (i <= middle && j <= end)
  362. {
  363. if (compare(key_at(data, i), key_at(data, j), context) >= 0)
  364. aux[k++] = key_at(data, j++);
  365. else
  366. aux[k++] = key_at(data, i++);
  367. }
  368. while (i <= middle)
  369. aux[k++] = key_at(data, i++);
  370. while (j <= end)
  371. aux[k++] = key_at(data, j++);
  372. for (i = 0; i < k; i++)
  373. set_key_at(data, begin + i, aux[i]);
  374. _delete(aux);
  375. }
  376. static void _quick_sort(void *data, int begin, int end, void *key_at(
  377. void *data, int index), void set_key_at(void *data, int index,
  378. void *new_value), int compare(void *x, void *y, void *context),
  379. void *context)
  380. {
  381. int middle;
  382. if (begin < end)
  383. {
  384. middle = _partition(data, begin, end, key_at, set_key_at, compare,
  385. context);
  386. _quick_sort(data, begin, middle, key_at, set_key_at, compare, context);
  387. _quick_sort(data, middle + 1, end, key_at, set_key_at, compare, context);
  388. }
  389. }
  390. static int _partition(void *data, int begin, int end, void *key_at(void *data,
  391. int index), void set_key_at(void *data, int index, void *new_value),
  392. int compare(void *x, void *y, void *context), void *context)
  393. {
  394. int i, j;
  395. void *pivot, *aux;
  396. pivot = key_at(data, begin + _rand() % (end - begin));
  397. i = begin - 1;
  398. j = end + 1;
  399. while (1)
  400. {
  401. do
  402. {
  403. i++;
  404. } while (i < end && compare(key_at(data, i), pivot, context) < 0);
  405. do
  406. {
  407. j--;
  408. } while (j > begin && compare(key_at(data, j), pivot, context) > 0);
  409. if (i >= j)
  410. return j;
  411. aux = key_at(data, i);
  412. set_key_at(data, i, key_at(data, j));
  413. set_key_at(data, j, aux);
  414. }
  415. }
  416. static void _heapify(void *data, int n, void *key_at(void *data, int index),
  417. void set_key_at(void *data, int index, void *new_value), int compare(
  418. void *x, void *y, void *context), void *context)
  419. {
  420. int start = n / 2 - 1;
  421. while (start >= 0)
  422. {
  423. _sift_down(data, start, n - 1, key_at, set_key_at, compare, context);
  424. start--;
  425. }
  426. }
  427. static void _sift_down(void *data, int begin, int end, void *key_at(void *data,
  428. int index), void set_key_at(void *data, int index, void *new_value),
  429. int compare(void *x, void *y, void *context), void *context)
  430. {
  431. int root, child;
  432. void *aux;
  433. root = begin;
  434. while ((root * 2 + 1) < end)
  435. {
  436. child = root * 2 + 1;
  437. if ((child < end) && (compare(key_at(data, child), key_at(data, child
  438. + 1), context) < 0))
  439. child++;
  440. if (compare(key_at(data, root), key_at(data, child), context) < 0)
  441. {
  442. aux = key_at(data, root);
  443. set_key_at(data, root, key_at(data, child));
  444. set_key_at(data, child, aux);
  445. root = child;
  446. }
  447. else
  448. return;
  449. }
  450. }
  451. static int _digit(int x, int y)
  452. {
  453. return (x / _power(y)) % 10;
  454. }
  455. static int _power(int x)
  456. {
  457. int p, i;
  458. p = 1;
  459. for (i = 0; i < x; i++)
  460. p *= 10;
  461. return p;
  462. }