Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 08.10.2009, 23:23   #1
lennon
Заблокирован
 
Регистрация: 18.11.2007
Сообщений: 254
По умолчанию Быстрая сортировка

Описывал ли кто то этот алгоритм конкретно для массива строк?
Строки сортирую с помощью void qs(LList * list,bool firstsort,bool req,int pos);
Можно ли сделать по другому?
Код:
void Swap(LList * list,int i,int j)
{
	string str1 = list->Strings(i);
	string str2 = list->Strings(j);
	list->Rewrite(str2,i);
	list->Rewrite(str1,j);
}

int FindKey(LList * list,int i, int j,int word)
{
	int first = Ord(list->Strings(i)[word]);
	for (int n=i;n<=j;n++)
	{
		if (Ord(list->Strings(n)[word]) > first) return n;
		else if (Ord(list->Strings(n)[word]) < first) return i; 
	}
	return -1;
}

int FindPartrition(LList * list,int i,int j,int key,int word)
{
	do
	{
		Swap(list,i,j);
		while (Ord(list->Strings(i)[word]) < key) i++;
		while(Ord(list->Strings(j)[word]) >= key) j--;
	}while(i<j);

	return i;
}

void QuickSort(LList * list, int i,int j,int word)
{
	int id = FindKey(list,i,j,word);
	if (id != -1)
	{
		int key = list->Strings(id)[word];
		int k = FindPartrition(list,i,j,key,word);
		QuickSort(list,i,k-1,word);
		QuickSort(list,k,j,word);
	}
}

void qs(LList * list,bool firstsort,bool req,int pos)
{
	int count = 0;
	bool found = false;
	char ch = 0;
	QuickSort(list,0,list->Count-1,0);

	for (int i=0;i<list->Count;i++)
	{
		if (list->Strings(i)[pos-1] == list->Strings(i+1)[pos-1])
		{
			ch = list->Strings(i)[pos-1];
			count++;
		}
		else if (ch != 0)
		{
			int p = i-1;
			LList * temp = new LList;
			for (int j=i-1;j<i+count;j++) temp->Add(list->Strings(j));
			QuickSort(temp,0,temp->Count-1,pos);
			for (int j=0;j<temp->Count;j++) list->Rewrite(temp->Strings(j),p++);
			qs(list,false,true,++pos);
			count=0;
			ch = 0;
			pos = 1;
		}
		else if (req) break;
	}
}
lennon вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Быстрая сортировка Serious Общие вопросы Delphi 2 02.11.2010 13:38
Сортировка методом линейного выбора и "быстрая" сортировка Карол Помощь студентам 4 27.09.2009 19:52
Быстрая сортировка Syltan Общие вопросы C/C++ 7 18.09.2009 17:35
быстрая сортировка ГРИГОРИЙ-кореш Помощь студентам 1 16.04.2009 18:13
Быстрая сортировка списка ManU Паскаль, Turbo Pascal, PascalABC.NET 2 08.12.2008 11:57