Re: sortowanie - Grupy dyskusyjne w eGospodarka.pl

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

Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!news.supermedia.pl!news.nask.pl!news.nask.org.pl!newsfeed.neostrada.pl
!unt-exc-01.news.neostrada.pl!unt-spo-a-02.news.neostrada.pl!news.neostrada.pl.
POSTED!not-for-mail
Newsgroups: pl.comp.programming
From: PK <P...@n...pl>
Subject: Re: sortowanie
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>
User-Agent: slrn/pre1.0.0-18 (Linux)
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Date: 13 Oct 2012 22:35:00 GMT
Lines: 16
Message-ID: <5079ec94$0$1309$65785112@news.neostrada.pl>
Organization: Telekomunikacja Polska
NNTP-Posting-Host: 95.49.152.153
X-Trace: 1350167700 unt-rea-a-02.news.neostrada.pl 1309 95.49.152.153:6729
X-Complaints-To: a...@n...neostrada.pl
Xref: news-archive.icm.edu.pl pl.comp.programming:199840
[ ukryj nagłówki ]

On 2012-10-13, kenobi <p...@g...com> wrote:
> a jaki to jest ? ;-)

Nie chodziło się na żaden wstęp do programowania ani nie czytało Knutha,
co?

Optymalny sort dla wektora liczb o znanej długości, to po prostu drzewo
decyzyjne (binarne) z porównaniami elementów. Jeśli wykonujesz tylko
konieczne porównania, to takie drzewo wyznacza Ci dolne ograniczenie dla
pesymistycznych wariantów (czyli ile porównań zawsze wystarcza do
posortowania n liczb).

Okazuje się, że do posortowania 20 liczb wystarczają 62 porównania.

pozdrawiam,
PK