[Algorytm - C++] QuickSort iteracyjny (?)

	B O A R D
	» Board » Zadaj pytanie » Archiwum » Szukaj » Stylizacja

M E N U

» Nowości

» Archiwum

» Recenzje / Testy

» Board

» Rejestracja

Szukaj @ TwojePC

	OBECNI NA TPC
	» ReMoS 00:20 » RaPToRR 00:10 » Conan Bar 23:54 » Star Ride 23:42 » piszczyk 23:37 » PCCPU 23:29 » metacom 23:07 » rooter666 23:06 » Matti 23:03 » biEski 22:59 » waski 22:59 » alien1 22:51 » abes99 22:49 » Pan Tadeu 22:49 » piotrszac 22:46 » Flo 22:45 » Kelso1 22:44 » Druzil 22:44 » rulezDC 22:39 » Soulfly 22:39 Dzisiaj przeczytano 832 postów, wczoraj 61370 Szybkie ładowanie jest: włączone.

ccc

A R C H I W A L N A W I A D O M O Ś Ć

[Algorytm - C++] QuickSort iteracyjny (?) , waski 22/10/04 10:09
Witam
Dalej sie mecze z programem porownujacym szybkosci roznych typow sortowania.
Prowadzacy lab powiedzial, ze mamy porownac takze szybkosc QS rekurencyjnego i iteracyjnego. Tylko ze o tym iteracyjnym nic nie moge znalezc :/
Zaczynam sie zastanawiac, czy po prostu nie wpuszcza nas w maliny :) W sumie to z definicji QS jest metoda "dziel i zwyciezaj", czyli jego implementacja powinna byc rekurencyjna...

Napisac tego tez jakos za bardzo nie moge - jakby tablica miala wielkosc bedaca potega 2 to zawsze da sie ja podzielic na 2 rowne czesci, potem na 4 itd. Problem stanowi nieparzysta liczba elementow...
np jak mamy 7 elementow to musimy tablice podzielic nierownomiernie - tylko co potem? Zapisywac gdzies informacje dotyczaca wczesniejszego podzialu tablicy?

W iteracji trzeba by sortowac (jesli sie myle poprawcie mnie):
1. najpierw cala tablica [np o indeksach 0-99]
2. potem jej pierwsza i druga 'polowe' 0-49, 50-99
3. pozniej coraz mniejsze czesci 0-24, 25-49, 50-74, 75-99
az dojdziemy do podzialu co dwa elementy - wtedy po posortowaniu koniec algorytmu

Moze znacie jakies www z opisem tego cuda? :)

Co mojego poprzedniego posta
http://twojepc.pl/boardPytanie80311.htm
to zeby dzialalo QueryPerformanceCounter wystarczy dodac #include <windows.h> :)

z gory dzieki za pomoc

SNAFU
Situation Normal, All Fucked Up

Da sie zrobic iteracyjnie , MARC 22/10/04 12:08
Poszukaj w kasiazkach "Algorytmy i struktury danych" Banachowski, Diks, Rytter i "Algorytmy + struktury danych = programy" Wirtha. Tam znajdziesz wlasciwie gotowe rozwiazania.
W skrocie to pomysl opiera sie na odkladaniu danych o dzielonych przedzialach na stos, a potem zdejmowaniu ich z niego przy zalozeniu, ze pierwszy odlozony przedzial jest zdejmowany jako ostatni. A poniewaz zawsze przy podiale dostaniesz jakies dwa przedzialy, to jeden odkladasz na stos do dalszej obrobki, a drugi przetwarzasz dalej iteracyjnie jesli mozesz, a jesli nie to zdejmujesz przedzial ze stosu.
To chyba tyle w skrocie algorytmu. Mam nadzieje, ze jest zrozumialy.
1. zrozumialy jest , waski 22/10/04 18:59
  tylko ze o ile wiem to w obu ksiazkach algorytmy pisza w Pascalu zamiast w C/C++ ;)
  najwyzej trzeba bedzie to przerobic jakos i tyle
  dzieki za podpowiedz
  SNAFU
  Situation Normal, All Fucked Up
  1. To chyba nie problem... , MARC 23/10/04 13:10
    Przerobienie algorytmu z Pascala na C ni epowinno stanowic zadnego problemu. Zreszta pisze sie je w Pascalu, aby byly najbardziej zrozumiale i najlatwiej je bylo przeniesc na inne jezyki.
    No i widzialem kiedys ksiazke o algorytmach z przykladamia wylacznie w C/C++, ale nie pamietam teraz nazwy. Poszukaj moze w jakiejs ksiegarni internetowej.