123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538 |
- /*!
- Temelia - Sorting algorithms implementation source file.
- Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
- @author Dascalu Laurentiu
- This program is free software; you can redistribute it and
- modify it under the terms of the GNU General Public License
- as published by the Free Software Foundation; either version 3
- of the License, or (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
- #include "include/sort.h"
- #include <stdlib.h>
- #include <string.h>
- // Private functions.
- // Merge sort.
- static void _merge_sort(void *data, int begin, int end, void *key_at(
- void *data, int index), void set_key_at(void *data, int index,
- void *new_value), int compare(void *x, void *y, void *context),
- void *context);
- static void _merge(void *data, int begin, int middle, int end, void *key_at(
- void *data, int index), void set_key_at(void *data, int index,
- void *new_value), int compare(void *x, void *y, void *context),
- void *context);
- // Quick sort.
- static void _quick_sort(void *data, int begin, int end, void *key_at(
- void *data, int index), void set_key_at(void *data, int index,
- void *new_value), int compare(void *x, void *y, void *context),
- void *context);
- static int _partition(void *data, int begin, int end, void *key_at(void *data,
- int index), void set_key_at(void *data, int index, void *new_value),
- int compare(void *x, void *y, void *context), void *context);
- // Heap sort.
- static void _heapify(void *data, int n, void *key_at(void *data, int index),
- void set_key_at(void *data, int index, void *new_value), int compare(
- void *x, void *y, void *context), void *context);
- static void _sift_down(void *data, int begin, int end, void *key_at(void *data,
- int index), void set_key_at(void *data, int index, void *new_value),
- int compare(void *x, void *y, void *context), void *context);
- // Radix sort.
- static int _digit(int x, int y);
- static int _power(int x);
- int is_sorted(void *data, int size, void *(*key_at)(void *data, int index),
- int (*compare)(void *x, void *y, void *context), void *context)
- {
- int i;
- _ASSERT(data, ==, NULL, NULL_POINTER, -1);
- _ASSERT(compare, ==, NULL, NULL_POINTER, -1);
- for (i = 0; i < size - 1; i++)
- if (compare(key_at(data, i), key_at(data, i + 1), context) > 0)
- return 0;
- return 1;
- }
- void bubble_sort(void *data, int size, void *(*key_at)(void *data, int index),
- void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
- void *x, void *y, void *context), void *context)
- {
- void *aux;
- int ordonat, i;
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(compare, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- do
- {
- ordonat = 0;
- for (i = 0; i < size - 1; i++)
- {
- if (compare(key_at(data, i), key_at(data, i + 1), context) > 0)
- {
- aux = key_at(data, i);
- set_key_at(data, i, key_at(data, i + 1));
- set_key_at(data, i + 1, aux);
- ordonat = 1;
- }
- }
- } while (ordonat);
- }
- void insertion_sort(void *data, int size, void *(*key_at)(void *data, int index),
- void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
- void *x, void *y, void *context), void *context)
- {
- int i, j;
- void *key, *aux;
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(compare, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- for (j = 1; j < size; j++)
- {
- key = key_at(data, j);
- i = j - 1;
- while (i >= 0 && compare(key_at(data, i), key, context) > 0)
- {
- aux = key_at(data, i);
- set_key_at(data, i, key_at(data, i + 1));
- set_key_at(data, i + 1, aux);
- i--;
- }
- }
- }
- void merge_sort(void *data, int size, void *(*key_at)(void *data, int index),
- void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
- void *x, void *y, void *context), void *context)
- {
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(compare, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- _merge_sort(data, 0, size - 1, key_at, set_key_at, compare, context);
- }
- void quick_sort(void *data, int size, void *(*key_at)(void *data, int index),
- void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
- void *x, void *y, void *context), void *context)
- {
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(compare, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- _quick_sort(data, 0, size - 1, key_at, set_key_at, compare, context);
- }
- void selection_sort(void *data, int size, void *(*key_at)(void *data, int index),
- void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
- void *x, void *y, void *context), void *context)
- {
- int i, j, min;
- void *aux;
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(compare, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- for (i = 0; i < size - 1; i++)
- {
- min = i;
- for (j = i + 1; j < size; j++)
- if (compare(key_at(data, j), key_at(data, min), context) < 0)
- min = j;
- aux = key_at(data, i);
- set_key_at(data, i, key_at(data, min));
- set_key_at(data, min, aux);
- }
- }
- void shell_sort(void *data, int size, void *(*key_at)(void *data, int index),
- void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
- void *x, void *y, void *context), void *context)
- {
- int i, j, increment;
- void *temp;
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(compare, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- increment = size / 2;
- while (increment > 0)
- {
- for (i = increment; i < size; i++)
- {
- j = i;
- temp = key_at(data, i);
- while ((j >= increment) && (compare(key_at(data, j - increment),
- temp, context) > 0))
- {
- set_key_at(data, j, key_at(data, j - increment));
- j -= increment;
- }
- set_key_at(data, j, temp);
- }
- if (increment == 2)
- increment = 1;
- else
- increment = (int) (increment / 2.2);
- }
- }
- void heap_sort(void *data, int size, void *(*key_at)(void *data, int index),
- void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
- void *x, void *y, void *context), void *context)
- {
- int end;
- void *aux;
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(compare, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- _heapify(data, size, key_at, set_key_at, compare, context);
- end = size - 1;
- while (end >= 0)
- {
- if (compare(key_at(data, 0), key_at(data, end), context) > 0)
- {
- aux = key_at(data, 0);
- set_key_at(data, 0, key_at(data, end));
- set_key_at(data, end, aux);
- end--;
- }
- else
- end--;
- _sift_down(data, 0, end, key_at, set_key_at, compare, context);
- }
- }
- void gnome_sort(void *data, int size, void *(*key_at)(void *data, int index),
- void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
- void *x, void *y, void *context), void *context)
- {
- int i, j;
- void *aux;
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(compare, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- i = 1;
- j = 2;
- while (i < size)
- {
- if (compare(key_at(data, i - 1), key_at(data, i), context) < 0)
- {
- i = j;
- j++;
- }
- else
- {
- aux = key_at(data, i - 1);
- set_key_at(data, i - 1, key_at(data, i));
- set_key_at(data, i, aux);
- i--;
- if (i == 0)
- i = 1;
- }
- }
- }
- void cocktail_sort(void *data, int size, void *(*key_at)(void *data, int index),
- void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
- void *x, void *y, void *context), void *context)
- {
- int buttom, top, i;
- void *aux;
- int ordonat = 1;
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(compare, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- buttom = 0;
- top = size - 1;
- while (ordonat)
- {
- ordonat = 0;
- for (i = buttom; i < top; i++)
- {
- if (compare(key_at(data, i), key_at(data, i + 1), context) > 0)
- {
- aux = key_at(data, i);
- set_key_at(data, i, key_at(data, i + 1));
- set_key_at(data, i + 1, aux);
- ordonat = 1;
- }
- }
- top--;
- for (i = top; i > buttom; i--)
- {
- if (compare(key_at(data, i - 1), key_at(data, i), context) > 0)
- {
- aux = key_at(data, i);
- set_key_at(data, i, key_at(data, i - 1));
- set_key_at(data, i - 1, aux);
- ordonat = 1;
- }
- }
- buttom++;
- }
- }
- void radix_sort(int *data, int size, int max_digits)
- {
- queue_t Q[10];
- int i, j, x, *y, *aux;
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(max_digits, <, 0, INVALID_INPUT,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- for (i = 0; i < 10; i++)
- Q[i] = queue_new(size);
- for (i = 0; i < max_digits; i++)
- {
- for (j = 0; j < size; j++)
- {
- x = _digit(data[j], i);
- y = (int *) _new(sizeof(int));
- *y = data[j];
- queue_push_back(Q[x], y);
- }
- x = 0;
- for (j = 0; j < 10; j++)
- {
- while (!queue_is_empty(Q[j]))
- {
- aux = (int *) queue_get_front(Q[j]);
- data[x++] = *aux;
- queue_pop_front(Q[j]);
- _delete(aux);
- }
- }
- }
- for (i = 0; i < 10; i++)
- queue_delete(Q[i]);
- }
- #include <stdio.h>
- void number_sort(unsigned int *data, int size, int max_value)
- {
- int i;
- int j;
- unsigned int *count;
- unsigned int *aux;
- LOGGER("[number_sort] data %p, size %d, max_value %d\n", data, size,
- max_value);
- _ASSERT(data, ==, NULL, NULL_POINTER,);
- _ASSERT(size, <=, 1, INVALID_INPUT,);
- aux = (unsigned int *) _new(size * sizeof(unsigned int));
- count = (unsigned int *) _new(max_value * sizeof(unsigned int));
- _ASSERT(aux, ==, NULL, NULL_POINTER,);
- _ASSERT(count, ==, NULL, NULL_POINTER,);
- memset(count, 0, max_value * sizeof(unsigned int));
- for (j = 0; j < size; j++)
- {
- if (data[j] >= (unsigned int) max_value || data[j] < 0)
- {
- LOGGER("[numer_sort] invalid input %d\n", data[j]);
- temelia_errno = INVALID_INPUT;
- return;
- }
- count[data[j]]++;
- }
- for (i = 1; i < max_value; i++)
- count[i] += count[i - 1];
- for (j = size - 1; j >= 0; j--)
- {
- aux[count[data[j]] - 1] = data[j];
- count[data[j]]--;
- }
- memcpy(data, aux, size * sizeof(unsigned int));
- _delete(aux);
- _delete(count);
- }
- static void _merge_sort(void *data, int begin, int end, void *key_at(
- void *data, int index), void set_key_at(void *data, int index,
- void *new_value), int compare(void *x, void *y, void *context),
- void *context)
- {
- int mid;
- if (begin < end)
- {
- mid = (begin + end) / 2;
- _merge_sort(data, begin, mid, key_at, set_key_at, compare, context);
- _merge_sort(data, mid + 1, end, key_at, set_key_at, compare, context);
- _merge(data, begin, mid, end, key_at, set_key_at, compare, context);
- }
- }
- static void _merge(void *data, int begin, int middle, int end, void *key_at(
- void *data, int index), void set_key_at(void *data, int index,
- void *new_value), int compare(void *x, void *y, void *context),
- void *context)
- {
- int i, j, k;
- void **aux;
- aux = (void **) _new((end - begin + 1) * sizeof(void *));
- i = begin;
- j = middle + 1;
- k = 0;
- while (i <= middle && j <= end)
- {
- if (compare(key_at(data, i), key_at(data, j), context) >= 0)
- aux[k++] = key_at(data, j++);
- else
- aux[k++] = key_at(data, i++);
- }
- while (i <= middle)
- aux[k++] = key_at(data, i++);
- while (j <= end)
- aux[k++] = key_at(data, j++);
- for (i = 0; i < k; i++)
- set_key_at(data, begin + i, aux[i]);
- _delete(aux);
- }
- static void _quick_sort(void *data, int begin, int end, void *key_at(
- void *data, int index), void set_key_at(void *data, int index,
- void *new_value), int compare(void *x, void *y, void *context),
- void *context)
- {
- int middle;
- if (begin < end)
- {
- middle = _partition(data, begin, end, key_at, set_key_at, compare,
- context);
- _quick_sort(data, begin, middle, key_at, set_key_at, compare, context);
- _quick_sort(data, middle + 1, end, key_at, set_key_at, compare, context);
- }
- }
- static int _partition(void *data, int begin, int end, void *key_at(void *data,
- int index), void set_key_at(void *data, int index, void *new_value),
- int compare(void *x, void *y, void *context), void *context)
- {
- int i, j;
- void *pivot, *aux;
- pivot = key_at(data, begin + _rand() % (end - begin));
- i = begin - 1;
- j = end + 1;
- while (1)
- {
- do
- {
- i++;
- } while (i < end && compare(key_at(data, i), pivot, context) < 0);
- do
- {
- j--;
- } while (j > begin && compare(key_at(data, j), pivot, context) > 0);
- if (i >= j)
- return j;
- aux = key_at(data, i);
- set_key_at(data, i, key_at(data, j));
- set_key_at(data, j, aux);
- }
- }
- static void _heapify(void *data, int n, void *key_at(void *data, int index),
- void set_key_at(void *data, int index, void *new_value), int compare(
- void *x, void *y, void *context), void *context)
- {
- int start = n / 2 - 1;
- while (start >= 0)
- {
- _sift_down(data, start, n - 1, key_at, set_key_at, compare, context);
- start--;
- }
- }
- static void _sift_down(void *data, int begin, int end, void *key_at(void *data,
- int index), void set_key_at(void *data, int index, void *new_value),
- int compare(void *x, void *y, void *context), void *context)
- {
- int root, child;
- void *aux;
- root = begin;
- while ((root * 2 + 1) < end)
- {
- child = root * 2 + 1;
- if ((child < end) && (compare(key_at(data, child), key_at(data, child
- + 1), context) < 0))
- child++;
- if (compare(key_at(data, root), key_at(data, child), context) < 0)
- {
- aux = key_at(data, root);
- set_key_at(data, root, key_at(data, child));
- set_key_at(data, child, aux);
- root = child;
- }
- else
- return;
- }
- }
- static int _digit(int x, int y)
- {
- return (x / _power(y)) % 10;
- }
- static int _power(int x)
- {
- int p, i;
- p = 1;
- for (i = 0; i < x; i++)
- p *= 10;
- return p;
- }
|