VPF::двоичная быстрая сортировка - Форум программистов

niknor

Дата 28.5.2007, 15:54 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 44
Регистрация: 21.4.2006
Где: РОССИЯ, Набережны е челны

Репутация: нет
Всего: нет

писал прогу про марруты автобусов, и попытался сделать двоичную бс, но никак не могу найти ошибку(всё время зацикливается)
все исходники, прикрепил.
заранее спасибо

Присоединённый файл ( Кол-во скачиваний: 14 )

Bus.rar 92,24 Kb

JackYF

Дата 28.5.2007, 17:07 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

если в архиве исходники занимают около 100 Кб... то каков же их реальный размер?..

--------------------

Пожаловаться на меня как модератора можно здесь.

Lomir

Дата 28.5.2007, 17:15 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 30.1.2007
Где: Lithuania::Kaunas

Репутация: 1
Всего: 1

А не лучше код самой сортировки сюда кинуть...?
И вопше двоичная быстрая сортировка что такое?

Fin

Дата 28.5.2007, 18:42 (ссылка)

(нет голосов)

Загрузка ...

Дракон->Спать();

Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 3
Всего: 10

Вот моя недавняя наработка на эту тему:

binsort.h

Код


#ifndef BINSORT_H
#define BINSORT_H
/******************************************************************************
// Author:   Fin
// 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

Код


#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);
}

Применение:

Код


#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;
}

--------------------

Пролетал мимо.

Anark1

Дата 28.5.2007, 19:59 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 622
Регистрация: 15.12.2006
Где: RF -> Moscow

Репутация: нет
Всего: 11

Если я правильно понимаю, то эта сортировка именуется "Сортировкой Хоора"?

--------------------

Enjoy yourself, still you can...;)

Fin

Дата 28.5.2007, 20:04 (ссылка)

(нет голосов)

Загрузка ...

Дракон->Спать();

Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 3
Всего: 10

Anark1, Дональд Кнут в своем труде "Исскуство программирования" том 3, ее назвал Бинарная сортировка и приписал авторство P.Hiderbrandt, H.Isbitz, H.Rising, J. Schwartz . Опубликован в JCAM 6 (1959)

--------------------

Пролетал мимо.

niknor

Дата 28.5.2007, 21:46 (ссылка)

(нет голосов)

Загрузка ...

JackYF Там не исходники, а весь проект(ошибся))

Добавлено через 3 минуты и 59 секунд
Fin,

Код


enum SortDirection {up, down};

это, что значит??

Добавлено через 10 минут и 26 секунд
вот, если хотите и сама сортировка:

Код


void CBusDoc::ZamPos2(List &ls1, List &ls2)
{
    List temp;
    temp = ls2;
    ls2=ls1;
    ls1=temp;
}

inline int CBusDoc::digit(List ls, int B)
{
    switch(List::m_sKeyFieldNum)
    {
        case 1:    return (ls.nom >> bitsbyte*(bytesword-B-1)&(R-1) );
        case 2: return ls.NachP[B];
        case 3: return ls.KonP[B];
        case 4: return ls.Opisan[B];
        case 5: return (ls.vremya >> bitsbyte*(bytesword-B-1)&(R-1) );
        case 6: return (ls.interv >> bitsbyte*(bytesword-B-1)&(R-1) );
    }
}
void CBusDoc::quicksortB( List lst[], int l, int r, int d)
{
    int i=l, j=r;
    if( r<=l || d>= bitsword)
        return;
    while( j!=i )
    {
        while(digit(lst[i], d)==0 && (i<j)) 
            i++;
        while(digit(lst[j], d)==1 && (j>i)) 
            j--;

        ZamPos2(lst[i], lst[j]);
    }
    if( digit(lst[r], d) == 0 )
        j++;
    quicksortB(lst, l, j-1, d+l);
    quicksortB(lst, j, r, d+l);

}
void CBusDoc::SortirBin(CList<List, List&> &lst,int fst, int last)
{
    int k(lst.GetCount());
    List* mlst=new List[k];
    POSITION posI;
    for(int i(0); i<k; ++i)
    {
        posI=lst.FindIndex(i);
        mlst[i]=lst.GetAt(posI);
    }
    quicksortB(mlst, fst, last, 0);
    for(int i(0); i<k; ++i)
    {
        posI=lst.FindIndex(i);
        lst.SetAt(posI, mlst[i]);
    }
    delete []mlst;
}

Fin

Дата 28.5.2007, 22:24 (ссылка)

(нет голосов)

Загрузка ...

Дракон->Спать();

Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 3
Всего: 10

Это тип переменной. Переменная с таким типом может принимать только два значения up и down.

Добавлено через 3 минуты и 46 секунд
Более подробно про enum читай в учебниках по С++.

--------------------

Пролетал мимо.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »