Реализация Bucket Sort в Objective C

Я реализовал различные алгоритмы сортировки в Objective-C (быстрая сортировка, сортировка слиянием, пузырьковая сортировка). Но я не нашел четкой реализации алгоритма Bucket Sort.

Я пытаюсь найти простую и эффективную реализацию алгоритма Bucket Sort в задаче C.


person 6rod9    schedule 05.12.2017    source источник


Ответы (1)


Я закончил тем, что сделал это сам, вот моя реализация, если кому-то это нужно:

- (NSArray*)bucketSort:(NSArray<NSNumber*> *)array buckets:(NSInteger)k {

    // Initialize array of buckets
    NSMutableArray<NSMutableArray*> *buckets = [NSMutableArray arrayWithCapacity:k];
    for (int i=0; i < buckets.count; i++)
        buckets[i] = [NSMutableArray new];

    // Add elements to buckets
    for (int i=0; i < buckets.count; i++) {
        NSInteger index = k * array[i].floatValue; // Asuming "array" has values between 0 and 1
        if (index < buckets.count) [buckets[index] addObject:array[i]];
    }

    NSMutableArray *sortedArray = [NSMutableArray new];

    // Sort individual buckets
    // Concatenate all sorted buckets in order
    for (int i=0; i < buckets.count; i++) {
        buckets[i] = [self quickSort:buckets[i]]; // Sorting algorithm like quicksort/mergesort/insertionsort
        [sortedArray addObjectsFromArray:buckets[i]];
    }

    return sortedArray;
}
person 6rod9    schedule 05.12.2017
comment
У вас есть if без else при добавлении элементов в сегменты, поэтому либо if является избыточным, либо некоторые элементы не могут быть добавлены ни в один сегмент. Вы также можете сделать его более эффективным, объединив два последних цикла, но вам придется решить, соответствует ли это вашей простой цели. (Конечно, сортировка чисел с плавающей запятой с помощью массивов Obj-C никогда не будет особенно эффективной, но это ортогонально эффективной реализации алгоритма как таковой.) HTH - person CRD; 06.12.2017
comment
@CRD Вы правы, if без else предназначено, это просто безопасная проверка, чтобы не выйти за пределы массива и не привести к сбою программы. Отчет об исключении или ошибке должен идти else вероятно. Спасибо за замечание по поводу последних двух петель, исправлю решение. Не могли бы вы порекомендовать другую коллекцию для реализации этого алгоритма в Obj-C? - person 6rod9; 06.12.2017
comment
Если вы действительно сортируете большое количество базовых значений (целые числа, числа с плавающей запятой), то использование стандартных массивов значений C (которые могут быть динамически выделены) будет быстрее, чем массивы объектов Objective-C (где сам массив является объектом, а содержит ваши значения, завернутые как объекты). Это не зависит от алгоритма сортировки. Для небольшого количества значений (поэтому накладные расходы незначительны) и, конечно, для объектов вы должны использовать обычно используемые коллекции на основе объектов. - person CRD; 06.12.2017