Re: sortowanie - Grupy dyskusyjne w eGospodarka.pl

eGospodarka.pl › Grupy › pl.comp.programming › sortowanie › Re: sortowanie

Received: by 10.52.175.5 with SMTP id bw5mr1360560vdc.16.1350178766725; Sat, 13 Oct
2012 18:39:26 -0700 (PDT)
Received: by 10.52.175.5 with SMTP id bw5mr1360560vdc.16.1350178766725; Sat, 13 Oct
2012 18:39:26 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!opal.futuro.pl!news.internetia.pl!news.
nask.pl!news.nask.org.pl!goblin3!goblin.stu.neva.ru!news.ripco.com!news.glorb.c
om!l8no49009929qao.0!news-out.google.com!r17ni24752519qap.0!nntp.google.com!l8n
o49009926qao.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-m
ail
Newsgroups: pl.comp.programming
Date: Sat, 13 Oct 2012 18:39:26 -0700 (PDT)
In-Reply-To: <k5d34d$nt1$1@node2.news.atman.pl>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=89.229.34.123;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
NNTP-Posting-Host: 89.229.34.123
References: <k59gbj$be7$1@node2.news.atman.pl>
<6...@g...com>
<k59jgh$mb7$1@mx1.internetia.pl> <k59jvr$360$1@node1.news.atman.pl>
<k59q5n$np3$1@mx1.internetia.pl> <k5a1ih$slr$1@node2.news.atman.pl>
<k5bd6c$a6c$1@mx1.internetia.pl> <k5blvn$3nk$1@node1.news.atman.pl>
<k5chsn$f2b$1@mx1.internetia.pl>
<6...@g...com>
<5079e395$0$1305$65785112@news.neostrada.pl>
<a...@g...com>
<5079ec94$0$1309$65785112@news.neostrada.pl>
<k5crml$h7t$1@node2.news.atman.pl>
<5079f663$0$26697$65785112@news.neostrada.pl>
<k5ctos$j0l$1@node2.news.atman.pl>
<2...@g...com>
<k5d34d$nt1$1@node2.news.atman.pl>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <b...@g...com>
Subject: Re: sortowanie
From: "M.M." <m...@g...com>
Injection-Date: Sun, 14 Oct 2012 01:39:26 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:199867
[ ukryj nagłówki ]
W dniu niedziela, 14 października 2012 03:05:18 UTC+2 użytkownik bartekltg napisał:
> Każdy if to pojście w prawo lub w lewo w drzewie decyzyjny.
> To jest drzewo binarne o 20! liściach. Czyli o wysokości
> ceil[log_2 (20!)] = 62 (PK już o tym pisał).
> To teraz wszystkie rozmiary w każdym kroku znasz.
Kazdy if zwieksza ilosc mozliwych sciezek wykonania
programu dwa razy. Czyli tak jak napisales, okolo log(20!).

Dla tego zrodla:
http://pastebin.com/RGhkx6u6

mam takie wyniki na swoim kompie:

873 859 809 800 667 561 440 421 260 148
selection time 0.420000s
873 859 809 800 667 561 440 421 260 148
insertion time 0.710000s
873 859 809 800 667 561 440 421 260 148
boubles time 1.010000s
873 859 809 800 667 561 440 421 260 148
sort10 time 1.290000s
873 859 809 800 667 561 440 421 260 148
qsort time 1.860000s
148 260 421 440 561 667 800 809 859 873
stl::qsort time 2.140000s

Czyli nawet dla 10 danych nie oplaca sie
rozwinac petli - widac ze algorytm sort10 dziala wolniej
niz selection.

Pozdrawiam