Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Сортировка  (Прочитано 11963 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« : 24-02-2007 19:18 » 

Сушествует множество алгоритмов сортировки. От простого пузырька и до быстрых способов сортировки. Для больших массивов в основном используют встроенную сортировку QuikSort. Довольно быстрый алгоритм. Но в свое время я столкнулся с тем, что при определенном объеме массива, я получал вылет программы из-за переполнения стека. Пришлось искать другие пути. В книге Д.Кнута "Исскуство программирования" Том 3 упоменается малоприменяемый алгоритм Бинарная сортировка. Он считается самым быстрым алгоритмом сортировки. Его время выполнение растет практически линейно от объема массива. Но есть и недостатки. Алгорит каждый раз нужно подстраивать под данные.
Сушность алгоритма очень проста. Сначало сортируем массив по самому старшему биту. Все числа, у которых самый старший бит равен 1 откидываем в один хвост массива, 0 во второй хвост
У нас получилось два подмасива. Соответственно их сортируем также как и раньше, только уже по второму по старшенству биту. И так далее.

Вот моя реализация для массива безнакового 32 разрядного числа.
binsort.h
Код: (C++)
#ifndef BINSORT_H
#define BINSORT_H
/******************************************************************************
// Author:   Finch
// Subject:  Binary Sort Function of unsigned integer array
// Version    1.0
// Date       24/02/2007
-------------------------------------------------------------------------------
Function of Binary Sort big array
void Binsort(unsigned int *buffer, int size, SortDirection dir);
buffer - array of unsigned int
size   - size of buffer
dir    - Direction of sort (up, down)
*/
/////////////////////////////////////////////////////////////////////////////

enum SortDirection {up, down};  

void Binsort(unsigned int *buffer, int size, SortDirection dir);

#endif //BINSORT_H

binsort.cpp
Код: (C++)
#include "binsort.h"

inline void change(unsigned int *a, unsigned int *b) {(*a)^=(*b); (*b)^=(*a); (*a)^=(*b);}

void BinsortUp(int left, int right, int level, unsigned int *buffer)
{  
        if (level<32)
        {
           int begLeft=left;
           int begRight=right;
           unsigned ms=0x80000000>>level;
                int flag=0;
                while (begLeft<begRight)
                {
                        switch (flag)
                        {
                         case 0:
                                if (buffer[begLeft] & ms) begLeft++;
                                else flag |= 1;
                                if (!(buffer[begRight] & ms)) begRight--;
                                else flag |=2;
                                break;
                         case 1:
                                if (!(buffer[begRight] & ms)) begRight--;
                                else flag |=2;
                                break;
                         case 2:
                                if (buffer[begLeft] & ms) begLeft++;
                                else flag |= 1;
                                break;
                         case 3:
                                 change(&buffer[begLeft], &buffer[begRight]);
                                 flag=0;
                                break;
                        }
                }
       
                while ((left<begLeft) && (!(buffer[begLeft] & ms))) begLeft--;
                while ((begRight <right) && (buffer[begRight] & ms)) begRight++;
                if (left != begLeft)
                {
                        if ((begLeft-left)> 1) BinsortUp(left,begLeft,level+1,buffer);
                        else
                        {
                                if (buffer[begLeft] > buffer[left]) change(&buffer[begLeft], &buffer[left]);
                        }
                }
                if (begRight != right)
                {
                        if ((right-begRight)>1) BinsortUp(begRight, right, level+1, buffer);
                        else
                        {
                                if (buffer[begRight] < buffer[right]) change(&buffer[right],&buffer[begRight]);
                        }
                }
        }
}

void BinsortDown(int left, int right, int level, unsigned int *buffer)
{  
        if (level<32)
        {
           int begLeft=left;
           int begRight=right;
           unsigned ms=0x80000000>>level;
                int flag=0;
                while (begLeft<begRight)
                {
                        switch (flag)
                        {
                         case 0:
                                if (!(buffer[begLeft] & ms)) begLeft++;
                                else flag |= 1;
                                if (buffer[begRight] & ms) begRight--;
                                else flag |=2;
                                break;
                         case 1:
                                if (buffer[begRight] & ms) begRight--;
                                else flag |=2;
                                break;
                         case 2:
                                if (!(buffer[begLeft] & ms)) begLeft++;
                                else flag |= 1;
                                break;
                         case 3:
                                 change(&buffer[begLeft], &buffer[begRight]);
                                 flag=0;
                                break;
                        }
                }
       
                while ((left<begLeft) && (buffer[begLeft] & ms)) begLeft--;
                while ((begRight <right) && (!(buffer[begRight] & ms))) begRight++;
                if (left != begLeft)
                {
                        if ((begLeft-left)> 1) BinsortDown(left,begLeft,level+1,buffer);
                        else
                        {
                                if (buffer[begLeft] < buffer[left]) change(&buffer[begLeft], &buffer[left]);
                        }
                }
                if (begRight != right)
                {
                        if ((right-begRight)>1) BinsortDown(begRight, right, level+1, buffer);
                        else
                        {
                                if (buffer[begRight] > buffer[right]) change(&buffer[right],&buffer[begRight]);
                        }
                }
        }
}

void Binsort(unsigned int *buffer, int size, SortDirection dir)
{
   if (dir==up) BinsortUp(0, size-1, 0, buffer);
   else BinsortDown(0, size-1, 0, buffer);
}

Насчет скорости. Тестовая программа
Код: (C++)
#include <stdio.h>
#include <stdlib.h>
#include "binsort.h"

#define max 10000000   // Это 10 миллионов знаков в массиве :)
unsigned int buffer[max];


int main()
{
   int i;
   for(i=0; i<max; i++) buffer[i]=rand()*rand();
   Binsort(buffer,max,up);
   return 0;
}

Используемое время на моей машине
Цитата
real    0m11.038s
user    0m8.529s
sys     0m0.124s

Увеличиваем массив до 50 миллионов
Цитата
real    0m59.668s
user    0m46.147s
sys     0m0.596s

 
« Последнее редактирование: 25-02-2007 13:47 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 24-02-2007 19:33 » 

клёво )
Записан

Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 25-02-2007 09:45 » 

Не совсем понял смысл 8-й состояний, если некоторые друг друга дублируют.

Что же касается сложности, если я правильно понял приведённый код, то не сказал бы, что этот алгоритм такой же быстрый, как и быстрая сортировкой. Получается, что он выполняет n*b проходов, где n - размер массива, b - разрядность элементов массива. Например, сортировка юникодных строк максимальной длиной 50 символов даст сложность n*50*16=800*n. Да, она линейно растёт от n для одинаковых элементов, но в ряде случаев, думаю, проиграет даже пузырьковой. Можно реализовать для строк и сравнить. При этом если в массив из 9999 строк длиной 3 юникодных символа каждая вдруг добавить строку длиной 30 символов, мы тут же получим увеличение на 10000*27*16=4320000 проходов массива в силу дополнения более коротких строк нулями до длины самой длинной строки массива. Либо придётся сортировать массив в m запусков бинароной сортировки, где каждый запуск будет сортировать массив по очередному символу строки - сложность будет для юникода m*16*n.
« Последнее редактирование: 25-02-2007 09:48 от dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #3 : 25-02-2007 13:31 » 

dimka, Насчет 8 состояний, это рудимент. Я просто первоначально хотел ввести в конечный автомат также и разброску по рекурсии на следуюшие уровни.  Но потом после эксперементов, решил что такой способ, который я привел будет быстрее работать. Рудимент остался.
Насчет строк Ты не прав. Данный алгоритм не предназначен для плаваюшего количества  знаков. Хотя его можно и приспособить под данную задачу. Степень сложности алгоритма автоматически естественно увеличится.
Когда я отлаживал на 1 миллионе элементов, у меня редко степень вложенности падала ниже 22. Это нужно иметь не очень удачный случай, чтобы достичь 32. Для 1 тысячи элементов, степень вложенности держалась около 9.

В свое время я его реализовывал на дельфи. И тогда мне нужно было сортировать 32 байтные блоки в количестве 1 миллион штук. На 850 мегагерцовом Пентиуме 3 полная сортировка занимала около 8 секунд. Пузырек, как ты выразился, может быть рассортирует в будушем столетии. Дельфийский QuikSort у меня падал если массив превышал размер 1024 элемента. Причина падения : Переполнение стека.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #4 : 25-02-2007 13:45 » 

У себя в коде я убрал рудимент Улыбаюсь
Получил следуюшие результаты:
Для 50 миллионов элементов
Цитата
real    0m44.783s
user    0m35.654s
sys     0m0.392s

Для 10 миллионов элементов
Цитата
real    0m6.337s
user    0m6.224s
sys     0m0.080s

Сейчас в коде подправлю.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 25-02-2007 14:39 » 

Цитата: Finch
Насчет строк Ты не прав. Данный алгоритм не предназначен для плаваюшего количества  знаков. Хотя его можно и приспособить под данную задачу. Степень сложности алгоритма автоматически естественно увеличится.
Когда я отлаживал на 1 миллионе элементов, у меня редко степень вложенности падала ниже 22. Это нужно иметь не очень удачный случай, чтобы достичь 32. Для 1 тысячи элементов, степень вложенности держалась около 9.
Эти числа - 32, 22, 9, - если я правильно понимаю, это количества битов, на которые углубляется алгоритм для различения элементов. Плавающий размер элементов тут ни при чём, важен размер элементов. На целых, размером 32 бита, получается то, что ты описал. На объектах, размерами много большими 32-х бит, получается, что алгоритм работать будет также много дольше. Или я не понял этого алгоритма.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #6 : 25-02-2007 15:23 » new

Да. Ты правильно понял смысл алгоритма.

Востанавливаю историческую справедливость: Данный алгоритм разработали P.Hiderbrandt, H.Isbitz, H.Rising, J. Schwartz . Опубликован в JCAM 6 (1959)
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines