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

    Статус
    Оффлайн
    Регистрация
    02.08.2014
    Адрес
    г. Киров (aka Вятка)
    Сообщений
    1,460
    Репутация:
    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
    Адрес
    Украина
    Сообщений
    60
    Репутация:
    11 ±
    Зачем в функции getMaxValue аргумент index?

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

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

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

    Статус
    Оффлайн
    Регистрация
    27.01.2014
    Адрес
    Восточный Мордор
    Сообщений
    5,123
    Репутация:
    1831 ±
    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]);

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

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

    Steve Pavlina

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

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

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

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

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

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

 

 

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

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

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

Ваши права

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