Добро пожаловать на Pro Pawn - Портал о PAWN-скриптинге.
Показано с 1 по 7 из 7
  1. #1
    Аватар для $continue$
    Заблокирован

    Статус
    Оффлайн
    Регистрация
    02.08.2014
    Адрес
    г. Киров (aka Вятка)
    Сообщений
    1,457
    Репутация:
    263 ±

    RadixSort - поразрядная сортировка

    Описание:

    Сам алгоритм работает так (кто знает, что такое mod, тот разберется):
      Открыть/закрыть
    .
    Сам алгоритм был переписан с С++ (т.к я не думаю, что алгоритм получился бы не идентичным).

     Временная сложность (скрины взяты с хабры)




    Параметры:
    arr[] - массив, который нужен отсортировать.
    size - размер массива (необязательный параметр)

    Возвращаемое значение:
    arr - отсортированный массив

    Код:
    PHP код:
    #if !defined MAX_SIZE_ARRAY_SORT
        #define MAX_SIZE_ARRAY_SORT 1000
    #endif

    stock GetMaxValue(arr[], size sizeof(arr), &index=-1)
    {
        new 
    max_arr arr[0];
        for (new 
    1sizei++)
        {
            if (
    arr[i] > max_arr)
            {
                
    max_arr arr[i];
                
    index i;
            }
        }
        return 
    max_arr;
    }
    stock CountSort(arr[], size sizeof(arr), exp)
    {
        new 
    output[MAX_SIZE_ARRAY_SORT]; // костыль из не возможности dynamic memory
        
    new icount[10];
        for (
    0sizei++)
            
    count[(arr[i] / exp) %10] ++;

        for (
    110i++)
            
    count[i] += count[1];

        for (
    size 1>= 0i--)
        {
            
    output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            
    count[(arr[i] / exp) % 10]--;
        }

        for (
    0sizei++)
            
    arr[i] = output[i];
    }
    stock RadixSort(arr[], size sizeof(arr))
    {
        new 
    max_val GetMaxValue(arrsize);
        for (new 
    exp 1max_val exp 0exp *= 10)
            
    CountSort(arrsizeexp);

    Пример использования:
    PHP код:
    #include <radix_sort>
    main()
    {
        new 
    arr[] = { 2481216203040151416200 };
        
    RadixSort(arr);
        for(new 
    0sizeof(arr); i++)
            
    printf("Index: %d | value: %d"iarr[i]);
        
    printf("max value in array: %d"arr[sizeof(arr) - 1]);

    Готовая библиотека для использования: download
    Последний раз редактировалось $continue$; 11.07.2017 в 13:36.

  2. #2
    Аватар для Pa4enka
    Пользователь

    Статус
    Оффлайн
    Регистрация
    22.04.2016
    Адрес
    Украина
    Сообщений
    55
    Репутация:
    10 ±
    Зачем в функции getMaxValue аргумент index?

  3. #3
    Аватар для $continue$
    Заблокирован

    Статус
    Оффлайн
    Регистрация
    02.08.2014
    Адрес
    г. Киров (aka Вятка)
    Сообщений
    1,457
    Репутация:
    263 ±
    Чтобы вернуть индекс до сортировки в котором максимальное значение
    Цитата Сообщение от Pa4enka Посмотреть сообщение
    Зачем в функции getMaxValue аргумент index?

  4. #4
    Аватар для DeimoS
    Модератор?

    Статус
    Оффлайн
    Регистрация
    27.01.2014
    Адрес
    Восточный Мордор
    Сообщений
    4,885
    Репутация:
    1782 ±
    PHP код:
    main()
    {
        new 
    arr[] = { 2481216203040151416200 };
        
    RadixSort(arr);
        for(new 
    0sizeof(arr); i++)
            
    printf("Index: %d | value: %d"iarr[i])// Нет точки с запятой
        
    printf("max value in array: %d"arr[sizeof(arr) - 1]);

    Связаться со мной можно в личных сообщениях этой группы

    Широко известно, что идеи стоят 0.8333 цента каждая (исходя из рыночной цены 10 центов за дюжину).
    Великих идей полно, на них нет спроса.
    Воплощение идеи в законченную игру требует долгой работы,
    таланта, терпения и креативности, не говоря уж о затратах денег, времени и ресурсов.
    Предложить идею просто, воплотить – вот в чём проблема

    Steve Pavlina

  5. Пользователь сказал cпасибо:
    $continue$ (11.07.2017)
  6. #5
    Аватар для $continue$
    Заблокирован

    Статус
    Оффлайн
    Регистрация
    02.08.2014
    Адрес
    г. Киров (aka Вятка)
    Сообщений
    1,457
    Репутация:
    263 ±
    Доберусь до ПК - скомпилирую код, кроме того название вспомогательных функции нужно сделать в стиле CamelCase

  7. #6
    Аватар для $continue$
    Заблокирован

    Статус
    Оффлайн
    Регистрация
    02.08.2014
    Адрес
    г. Киров (aka Вятка)
    Сообщений
    1,457
    Репутация:
    263 ±
    Обновлено.
    • Исправлены ошибки с компиляцией
    • Добавлена готовая библиотека

  8. #7
    Аватар для Geebrox
    Пользователь

    Статус
    Оффлайн
    Регистрация
    24.08.2015
    Адрес
    Ташкент
    Сообщений
    375
    Репутация:
    96 ±
    Думаю стоит добавить проверку на то, что имеется ли функция GetMaxValue, возможно это название используется не только в этом инклюде, или добавить тег

 

 

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •