sortowanie przez wstawianie?

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 :)

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)

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

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

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! :)

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.

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).

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