sortowanie przez wstawianie?

Odpowiedz Nowy wątek
gościu
2010-03-15 21:44
gościu
0

siema właśnie przygotowuję się do zaimplementowania algorytmu sortowania przez wstawianie korzystajac z tablicy i dodatkowo listy za pomoca ktorej szybciej dojde do poziomu pewnych posortowanych fragmentow gotowych do scalania i tutaj moje pytanie brzmi czy wazne jest bym scalal posortowane elementy w ten sposob (zgodnie z regula drzewa):
1+1 1 1+1 1+1
2 + 1 2 + 2
3 + 4
7

czy moge rownie dobrze scalac posortowane elementy np 2 elementy + 6 1 element + 4 - ten sposob byl by dla mnie wygodniejszy (nie zgodnie z regula drzewa) jednak pytanie czy jest to stratne, oraz jak bardzo jest?
pozdrawiam :)

Pozostało 580 znaków

2010-03-15 21:47
Moderator

Rejestracja: 16 lat temu

Ostatnio: 5 minut temu

0

Zdecyduj się. To co opisałeś początkowo to jest sortowanie przez scalanie, działa w czasie O(nlogn).
To o co potem pytasz to sortowanie przez wstawianie dzialające w czasie O(n^2)


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

gościu
2010-03-15 21:55
gościu
0

ale byk oj ; o sory... caly czas chodzilo mi o sortowanie przez scalanie... pytanie czy jest to obojetne czy scalam posortowane fragmenty np 3 elementy + 15 elementow czy 9 + 9?... jeszcze raz sory za byka

Pozostało 580 znaków

2010-03-15 22:18
Moderator

Rejestracja: 16 lat temu

Ostatnio: 5 minut temu

0

Scalenie dwóch ciągów posortowanych z których jeden ma długość n, a drugi m to O(n+m)
Więc jak widać nie ma w tym wypadku, teoretycznie, znaczenia długość jednego i drugiego ciągu.
Inna kwestia jest taka że łatwiej napisac algorytm który będzie robił równe kawałki ;)


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

gościu
2010-03-15 22:43
gościu
0

dzieki ;) dokladnie o to mi chodzilo :) jak by nie patrzec to latwiej napisac program ktory dzieli tablice na 2 za kazdym razem az do samego dna - pojedynczych elementow ale z drugiej strony mozna przeleciec raz tablice skorzystac z list i z gory z przypadkowych danych otrzymac podciagi posortowane nawet do kilku elementow a pozniej juz tylko scalac elementy a skoro to juz zupelnie obojetne jak beda scalane byle elementy 2 podciagow byly posortowane to juz w zasadzie jestem gotowy do implementacji bo inaczej to bym musial jeszcze pokombinowac troszke :) jeszcze raz dzieki i pozdro! :)

Pozostało 580 znaków

2010-03-15 23:23
Moderator

Rejestracja: 16 lat temu

Ostatnio: 5 minut temu

0

Oj nie nie. Nie myl pojęć. To co chciałbyś zrobić mogłoby znacznie przyspieszyć algorytm, tylko że go po prostu utrudni. Zauważ ze optymistyczny przypadek zwykłego scalania to O(nlogn) bez względu na dane. A z taką optymalizacja o jakiej mówisz to O(n).
Zauważ ze jeśli wybierasz początkowo te naturalne serie z początkowej tablicy to potem tych scaleń będzie mniej! Samo scalenie jest tak samo kosztowne, to prawda, ale wykona sie mniej razy.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2010-03-16 00:39

Rejestracja: 15 lat temu

Ostatnio: 1 godzina temu

0

Scalanie zajmuje czas Theta(n + m) jeśli korzystamy z dodakowej pamięci rzędu min(n, m). Scalanie w miejscu zajmuje czas O((n + m) log (n + m)). Tak więc klasyczne sortowanie przez scalanie zajmuje Theta(n lg n), a sortowanie przez scalanie w miejscu (tak jest chyba w stlu) to O(n lg ^ 2 n).


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0