|
| Опубликовано 13.03.2014 16:07 (11 лет назад) # |
Может тут помогут умные люди... Не могу реализовать данный алгоритм Bucket Sort на Си. Накопал примеров, но нет именно на Си (или не рабочие, уже не помню). Так же пробовал "переводить" с других немного известных языков. Короче опыта все же мало в этом.
Может кто знает как с этим быть? Примерчик с университетских лет на паскале какой-нибудь.
17-го Deadline вся группа пеньков, которым достался вариант с этим алгоритмом, в печали. |
|
|
|
|
| Опубликовано 13.03.2014 16:49 (11 лет назад) # |
Алгоритм не такой уж трудный. Требуется к нему работа со списками (в Си нет списков, надо реализовать) и сортировка вставкой.
Лучше напиши код, который нашел, здесь или ссылку, может кто поможет. Советую посмотреть книжку "Алгоритмы: построение и анализ". |
|
|
|
|
| Опубликовано 13.03.2014 20:56 (11 лет назад) # |
Лучше напиши что не получается, на каком шаге и какая проблема.
Потому что реализация достаточно простая, нужна сортировка (хоть пузырем), и умение связать воедино пару-тройку форов и ифов. Для начала достаточно сортировать массивы.
Начни с двух корзин, там все совсем просто. |
|
|
|
|
| Опубликовано 13.03.2014 22:06 (11 лет назад) # |
даже если использовать этот алгоритм то после распределения по группам все равно нужно использовать какой либо алгоритм сортировки (как я понял)/или рекурсию у тебя что конкретно надо ?
какой должен быть прототип функции (массив целых чисел какой длинны)? (может смогу написать но лень может победить)
редакция от ParTizan, 13.03.2014 22:16 |
|
|
|
|
| Опубликовано 13.03.2014 22:11 (11 лет назад) # |
(может смогу написать но лень может победить)
Сомневаешься в своем проигрыше? |
|
|
|
|
| Опубликовано 13.03.2014 22:39 (11 лет назад) # |
pelmenka написал:
(может смогу написать но лень может победить)
Сомневаешься в своем проигрыше?
я как кот Шредингера |
|
|
|
|
| Опубликовано 14.03.2014 13:11 (11 лет назад) # |
Требуется к нему работа со списками (в Си нет списков, надо реализовать)
Как раз этому обучали.
даже если использовать этот алгоритм то после распределения по группам все равно нужно использовать какой либо алгоритм сортировки (как я понял)/или рекурсию у тебя что конкретно надо ?
Ничего конкретного нет, мне важно исследование данных алгоритмов и способность показать их работу, на крайняк.
Исследования проходят на целочисленных массивах длинны от 50000 до 1000000.
Как такового кода у меня нет. Препод отправил на википедию, но код, что там дам, я уже пытался написать. msbits, конкатенация, переменная k и входные данные меня поставили в ступор. Так же препод отправил меня читать книжку какую-то, пойду посмотрю.
|
|
|
|
|
| Опубликовано 14.03.2014 14:40 (11 лет назад) # |
http://citforum.ru/programming/c/h22.shtml
по моему то, что тебе надо. (пункт 2,2,6)
редакция от ParTizan, 14.03.2014 14:41 |
|
|
|
|
| Опубликовано 14.03.2014 15:32 (11 лет назад) # |
| 2.2.6 это быстрая сортировка (quick sort) |
|
|
|
|
| Опубликовано 14.03.2014 16:06 (11 лет назад) # |
я имею в веду распределяющую
сразу же идет после qicksort |
|
|
|
|
| Опубликовано 14.03.2014 16:26 (11 лет назад) # |
Распределяющая - прикольный способ. Правда въехать в него сложнее, чем в сортировку bucket, хотя чем-то напоминает.
А пример у них не работает. У меня выдал такое:
0 7 18 3 52 4 6 8 5 13 42 30 35 26
7 8 13 18 26 30 35 42 52
Отсортировал, но по дороге потерял (;
редакция от bsivko, 14.03.2014 16:26 |
|
|
|
|
| Опубликовано 15.03.2014 16:53 (11 лет назад) # |
Просмотрел все имеющиеся книженции. Чтож завтра попробую кое-что написать, но думаю опять ничего не выйдет.
Скринчик.
Что есть ключ переменной? Я такого не изучал. Это хэш-ключ? Как это добыть?
lowkey и highkey откуда в итоге взять? Запоминать каждый раз, когда засуну новый элемент?
succ(lowkey) to highkey это просто перебор или succ все же что-то внесет?
К тому же читал что-то на счет самого разделения на кармашки, но похоже недопонял. Ведра могут делиться по единицам, десяткам, сотням и т.д. в зависимости от размера массива. Получается для элементов в пределах 10,000,000 мне и создавать такие ведра? И как это вообще происходит?
Типа взял ведра по 100 и решаю куда запихать 654, делю 654 на 100, получаю 6 и его ключ и тогда пихаю в нужное ведро? У каждого числа свой ключик будет? Мне говорили, что возможны совпадения каким-то образом...
DSA... Looks like it's time for plan C.
редакция от LetsOffBrains, 15.03.2014 16:55 |
|
|
|
|
| Опубликовано 15.03.2014 19:03 (11 лет назад) # |
| для начала тебе надо сделать ведра - в С++ для етого можно использовать списки, а в С самому надо писать (главное сделать конкатенацию етих ведер, добавление нового елемента и функцию сортировки внутри ведра) потом Типа взял ведра по 100 и решаю куда запихать 654, делю 654 на 100, получаю 6 и добавляешь в 6 ведро... как все по ведрам раскидал делаешь сортировку в каждом и складываешь их в правильном порядке в большое ведро(массив)... я так понял етот алгоритм... проблема тут только сделать сами ведра, но я думаю можно найти где нить код для С который реализует списки=)) |
|
|
|
|
| Опубликовано 15.03.2014 19:51 (11 лет назад) # |
LetsOffBrains написал:
Типа взял ведра по 100
Ведра берутся не по размеру, а по диапазону.
Каждое ведро должно быть способно вместить в себя весь исходный массив.
Самый простейший случай выбора ведер - сделать равномерно по диапазону. Например в исходном массиве 100 чисел, минимальное 7, а максимальное 133. а ведер 3. Каждое ведро захватывает одинаковый диапазон, 7..48, 49..91, 92..133. Но в каждое из них могут попасть все элементы (здесь 99, а вообще 100), поэтому макс размер вместимости ведра должен быть минимум 100.
Делаем первый прогон и разбрасываем по ведрам. Каждое из них сортируем какой-нибудь сортировкой. В результате ведра имеют отсортированные числа, и сами по себе они идут друг за другом в порядке сортировки. И нам достаточно объединить их вместе в один массив последовательно. |
|
|
|
|
| Опубликовано 16.03.2014 08:23 (11 лет назад) # |
Грац, написал эту шнягу. Осталось довести до ума сортировку списков т.к. я устал ждать, когда же отсортируется массив в миллион элементов. Саму сортировку я сделал довольно глупо, и не знаю как ее оптимизировать т.к. как с массивом с ней не поработаешь.
Вот что вышло, весь модуль:
struct listnode{
int a;
struct listnode *next;
};
struct listnode *list_addfront( struct listnode *list, int value){
struct listnode *newnode;
newnode = list_createnode(value);
if(newnode != NULL){
newnode->next = list;
return newnode;
}
return list;
};
void list_sort( struct listnode *list){
int temp, f = 0;
struct listnode *first;
first = list;
while(list != NULL){
if(list->a > list->next->a){
temp = list->a;
list->a = list->next->a;
list->next->a = temp;
f = 1;
}
if(list->next->next != NULL){
list = list->next;
}
else{
if(f){
list = first;
f = 0;
}
else{
break;
}
}
}
}
void bucket_sort(int a[], int n){
int i = 0, j = 0, k = 10000, q;
if(n / k < 10){
q = 10;
}
else{
q = n / k;
}
struct listnode *head[q];
while(i < q){
head[i] = NULL;
i++;
}
i = 0;
while(i<n){
head[a[i] / k] = list_addfront( head[a[i] / k], a[i]);
i++;
}
i = 0;
while(i < q){
list_sort(head[i]);
i++;
}
i = 0;
while(i < q){
while(head[i] != NULL){
a[j] = head[i]->a;
head[i] = head[i]->next;
//printf("%d ", a[j]);
j++;
}
i++;
}
//printf("\n");
}
Соответственно list_sort - моя глупая сортировка. Как можно оптимизировать сортировку со списком такого вида?
UPD #1. Табуляция не сохраняется(
редакция от LetsOffBrains, 16.03.2014 08:25 |
|
|
|