| dbpprop:abstract
|
- Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes \Theta(n\log n) comparisons to sort n items. However, in the worst case, it makes \Theta(n^2) comparisons. Typically, quicksort is significantly faster in practice than other \Theta(n \log n) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.
- Quicksort (von engl. quick‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (lat. Divide et impera!, engl. Divide and conquer) arbeitet. Er wurde ca. 1960 von C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von vielen Forschern verbessert. Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und ohne zusätzlichen Speicherplatz auskommt (abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack). thumb|Eine zufällige Permutation des Umfangs <math>n</math>, in der jedes Element von 1 bis <math>n</math> lediglich einmal vorkommt, wird mit Quicksort sortiert.
- L'ordenament ràpid, quicksort en anglès, és un algorisme basat en la tècnica de divideix i venceràs, que permet, de mitjana, ordenar n elements en un temps proporcional a n log n. Aquesta és probablement la tècnica d'ordenament més ràpida que es coneix. Fou desenvolupada per C. Antony R. Hoare el 1960. L'algorisme original és recursiu, però s'utilitzen versions iteratives per a millorar-ne el rendiment (els algorismes recursius són en general més lents que els iteratius i consumeixen més recursos).
- Quicksort neboli rychlé (rekurzivní) řazení do tříd je jeden z nejrychlejších známých algoritmů řazení založených na porovnávání prvků. Jeho průměrná časová složitost je pro algoritmy této skupiny nejlepší možná, v nejhorším případě (kterému se ale v praxi jde obvykle vyhnout) je však jeho časová náročnost O(N²). Další výhodou algoritmu je jeho jednoduchost.
- El ordenamiento rápido es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
- Pikalajittelu (quicksort) on C. A. R. Hoaren kehittämä epävakaa lajittelualgoritmi, jossa joukosta valitaan tietty alkio vertailukohdaksi. Tätä alkiota nimitetään sarana-alkioksi (pivot), koska se yhdistää aineiston eri osat. Muut alkiot lajitellaan kahteen ryhmään sarana-alkiota käyttäen (esimerkiksi alkiota pienemmät ja suuremmat/yhtäsuuret), joille rekursiivisesti toistetaan sama ryhmittely uudella sarana-alkiolla.
- Le tri rapide (en anglais quicksort) est une méthode de tri inventée par C.A.R. Hoare en 1961 et fondée sur la méthode de conception diviser pour régner. Il peut être implémenté sur un tableau (tri sur place) ou sur des listes; son utilisation la plus répandue concerne tout de même les tableaux. Le Quicksort est un tri dont la complexité moyenne est en <math>O(n\ \log n)</math>, mais dont la complexité dans le pire des cas est <math>O(n^2)</math>. Malgré ce désavantage théorique, c'est en pratique un des tris sur place le plus rapide pour des données réparties aléatoirement. Les entrées donnant lieu au comportement quadratique dépendent de l'implémentation de l'algorithme, mais sont souvent (si l'implémentation est maladroite) les entrées déjà presque triées. Il sera plus avantageux alors d'utiliser le tri par insertion ou l'algorithme Smoothsort.
- Fájl:Sorting quicksort anim. gif Oszlopok magasság szerinti gyorsrendezése. A pirossal jelölt elem a támpont. A gyorsrendezés vagy quicksort algoritmus egy tömb elemeinek sorba rendezésére. C. A. R. Hoare találmánya, egyike azon rendezéseknek, amiknek a bonyolultsága átlagos esetben \Theta(n\log n). A gyorsrendezés általában gyorsabb az egyéb \Theta(n\log n) rendezéseknél, mert a belső ciklusa a legtöbb architektúrán nagyon hatékonyan implementálható, és az adatok jellegének ismeretében az algoritmus egyes elemei megválaszthatóak úgy, hogy csak nagyon ritkán fusson négyzetes ideig. A gyorsrendezés egy összehasonlító rendezés, és – hatékonyan implementálva – nem stabil rendezés.
- Quicksort è un ottimo algoritmo di ordinamento ricorsivo in place che, come merge sort, si basa sul paradigma divide et impera. La base del suo funzionamento è l'utilizzo ricorsivo della procedura partition: preso un elemento da una struttura dati si pongono gli elementi minori a sinistra rispetto a questo e gli elementi maggiori a destra. Il Quicksort, termine che tradotto letteralmente in italiano indica ordinamento rapido, è l'algoritmo di ordinamento che ha, in generale, prestazioni migliori tra quelli basati su confronto. È stato ideato da Charles Antony Richard Hoare nel 1961. Il Quicksort è molto popolare dato che è facilmente implementabile ed è un buon algoritmo general purpose, che ha un buon comportamento in un'ampia varietà di situazioni ed in molti casi richiede meno risorse di qualsiasi altro algoritmo. Offre inoltre il vantaggio di operare direttamente sul file da ordinare (utilizzando un piccolo stack ausiliario), e per effettuare l'ordinamento di N elementi richiede mediamente solo <math> n \log n\!</math> operazioni e ha un ciclo interno estremamente breve. Gli svantaggi sono dati dal fatto che non è stabile, nel caso peggiore ha un comportamento quadratico ed è particolarmente fragile: un semplice errore nella sua implementazione può passare inosservato ma causare in certe situazioni un drastico peggioramento nelle prestazioni dell'algoritmo. Il Quicksort è stato sottoposto a un'analisi matematica approfondita ed estremamente precisa, tanto che le sue prestazioni sono state comprese a fondo e il suo comportamento è stato descritto in modo molto accurato. I risultati ottenuti in fase di analisi sono stati verificati sperimentalmente in modo esteso e l'algoritmo di base è stato migliorato al punto da diventare il metodo ideale per un gran numero di applicazioni pratiche. Sono stati svolti inoltre numerosi studi per migliorare le prestazioni anche in considerazione del fatto che la ricerca di un algoritmo di ordinamento più veloce è una delle principali attrattive dell'informatica. Praticamente dal momento in cui Hoare pubblicò per la prima volta il suo lavoro, la letteratura specializzata iniziò a proporre versioni migliorate dell'algoritmo. Sono state provate e analizzate molte idee, ma l'algoritmo è così ben bilanciato da far si che il miglioramento apportato in una parte del programma quasi inevitabilmente dia luogo a un peggioramento delle prestazioni in qualche altro punto. Per la sua estrema facilità è stato scelto in molte librerie di linguaggi come il C di implementare di base una funzione che effettui l'ordinamento del Quicksort. C'è da tenere presente che spesso ci si può sorprendere del comportamento indesiderato e inatteso in presenza di input particolari, specialmente se si tratta di versioni dell'algoritmo messe a punto accuratamente. Se un'applicazione non giustifica il lavoro necessario ad assicurare che l'implementazione del Quicksort sia esente da errori lo Shell sort rappresenta una scelta sicura in grado di garantire prestazioni sufficientemente buone a fronte di un minore sforzo implementativo.
- ファイル:Sorting quicksort anim. gif クイックソートのアニメーション クイックソートは、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 最良計算量および平均計算量はO<math>(n\log n)</math>である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO<math>(n^2)</math>である。また数々の変種がある。 安定ソートではない。
- Quicksort is een sorteer-algoritme uitgevonden door Tony Hoare.
- Sortowanie szybkie – jeden z popularnych algorytmów sortowania działających na zasadzie "dziel i zwyciężaj". Sortowanie QuickSort zostało wynalezione w 1962 przez C.A.R. Hoare'a
- O algoritmo Quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960, quando visitou a Universidade de Moscovo como estudante. Ele criou o 'Quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais facil e rapidamente. Foi publicado em 1962 após uma série de refinamentos. O Quicksort é um algoritmo de ordenação não-estável.
- Quicksort este un celebru algoritm de sortare, dezvoltat de C. A. R. Hoare şi care, în medie, efectuează <math>\theta(n \log{n})</math> comparaţii pentru a sorta n elemente. În cazul cel mai rău, efectuează <math>O(n^2)</math> comparaţii. De obicei, în practică, quicksort este mai rapid decât ceilalţi algoritmi de sortare de complexitate <math>\theta(n \log{n})</math> deoarece bucla sa interioară are implementări eficiente pe majoritatea arhitecturilor şi, în plus, în majoritatea implementărilor practice se pot lua, la proiectare, decizii ce ajută la evitarea cazului când complexitatea algoritmului este de <math>O(n^2)</math>
- Файл:Sorting quicksort anim. gif Анимированная схема алгоритма Быстрая сортировка, часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.
- Quicksort är en av de snabbaste sorteringsalgoritmerna. Den sorterar n objekt med tidskomplexitet O (n) i värsta fall och med en genomsnittlig tidskomplexitet O (n log n). En förutsättning för att man når denna komplexitet är att man väljer rätt pivot-element, ett slumpvist valt är bra men man brukar nöja sig med medianen av 3 (ett från början ett från slutet och ett från mitten av listan).
- Hızlı Sıralama günümüzde yaygın olarak kullanılan bir sıralama algoritmasıdır. Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda, <math>\mathcal{O}(n~log)</math> karmaşılığıyla, en kötü durumda ise <math>\mathcal{O}(n^2)</math> karmaşıklığıyla sıralar. Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına eşittir.
- Швидке сортування — алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Хоаром, який не потребує додаткової пам'яті і виконує у середньому <math>\;O(n\log\;n)</math> операцій. Однак, у найгіршому випадку робить <math>O(n^2)</math> порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності. Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин вудбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв’язному списку. Швидке сортування є алгоритмом на основі порівнянь, і не є стабільним.
- 快速排序是一種排序算法，由C. A. R. Hoare所發展的，以平均效能來說，排序 n 個項目要Θ(n log n)次比較。然而，在最壞的效能下，它需要Θ(n)次比較。一般來說，快速排序實際上明顯地比其他Θ(n log n) 演算法更快，因為它的內部回圈（inner loop）可以在大部分的架構上很有效率地被實作出來，且在大部分真實世界的資料，可以決定設計的選擇，減少所需時間的二次方項之可能性。
|
| rdfs:comment
|
- Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes \Theta(n\log n) comparisons to sort n items. However, in the worst case, it makes \Theta(n^2) comparisons.
- Quicksort (von engl. quick‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (lat. Divide et impera!, engl. Divide and conquer) arbeitet. Er wurde ca. 1960 von C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von vielen Forschern verbessert.
- L'ordenament ràpid, quicksort en anglès, és un algorisme basat en la tècnica de divideix i venceràs, que permet, de mitjana, ordenar n elements en un temps proporcional a n log n. Aquesta és probablement la tècnica d'ordenament més ràpida que es coneix. Fou desenvolupada per C. Antony R. Hoare el 1960.
- Quicksort neboli rychlé (rekurzivní) řazení do tříd je jeden z nejrychlejších známých algoritmů řazení založených na porovnávání prvků. Jeho průměrná časová složitost je pro algoritmy této skupiny nejlepší možná, v nejhorším případě (kterému se ale v praxi jde obvykle vyhnout) je však jeho časová náročnost O(N²). Další výhodou algoritmu je jeho jednoduchost.
- El ordenamiento rápido es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
- Pikalajittelu (quicksort) on C. A. R. Hoaren kehittämä epävakaa lajittelualgoritmi, jossa joukosta valitaan tietty alkio vertailukohdaksi. Tätä alkiota nimitetään sarana-alkioksi (pivot), koska se yhdistää aineiston eri osat. Muut alkiot lajitellaan kahteen ryhmään sarana-alkiota käyttäen (esimerkiksi alkiota pienemmät ja suuremmat/yhtäsuuret), joille rekursiivisesti toistetaan sama ryhmittely uudella sarana-alkiolla.
- Le tri rapide (en anglais quicksort) est une méthode de tri inventée par C.A.R. Hoare en 1961 et fondée sur la méthode de conception diviser pour régner. Il peut être implémenté sur un tableau (tri sur place) ou sur des listes; son utilisation la plus répandue concerne tout de même les tableaux. Le Quicksort est un tri dont la complexité moyenne est en <math>O(n\ \log n)</math>, mais dont la complexité dans le pire des cas est <math>O(n^2)</math>.
- Fájl:Sorting quicksort anim. gif Oszlopok magasság szerinti gyorsrendezése. A pirossal jelölt elem a támpont. A gyorsrendezés vagy quicksort algoritmus egy tömb elemeinek sorba rendezésére. C. A. R. Hoare találmánya, egyike azon rendezéseknek, amiknek a bonyolultsága átlagos esetben \Theta(n\log n).
- Quicksort è un ottimo algoritmo di ordinamento ricorsivo in place che, come merge sort, si basa sul paradigma divide et impera. La base del suo funzionamento è l'utilizzo ricorsivo della procedura partition: preso un elemento da una struttura dati si pongono gli elementi minori a sinistra rispetto a questo e gli elementi maggiori a destra.
- ファイル:Sorting quicksort anim.
- Quicksort is een sorteer-algoritme uitgevonden door Tony Hoare.
- Sortowanie szybkie – jeden z popularnych algorytmów sortowania działających na zasadzie "dziel i zwyciężaj". Sortowanie QuickSort zostało wynalezione w 1962 przez C.A.R. Hoare'a
- O algoritmo Quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960, quando visitou a Universidade de Moscovo como estudante. Ele criou o 'Quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais facil e rapidamente. Foi publicado em 1962 após uma série de refinamentos.
- Quicksort este un celebru algoritm de sortare, dezvoltat de C. A. R. Hoare şi care, în medie, efectuează <math>\theta(n \log{n})</math> comparaţii pentru a sorta n elemente. În cazul cel mai rău, efectuează <math>O(n^2)</math> comparaţii.
- Файл:Sorting quicksort anim. gif Анимированная схема алгоритма Быстрая сортировка, часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром.
- Quicksort är en av de snabbaste sorteringsalgoritmerna. Den sorterar n objekt med tidskomplexitet O (n) i värsta fall och med en genomsnittlig tidskomplexitet O (n log n). En förutsättning för att man når denna komplexitet är att man väljer rätt pivot-element, ett slumpvist valt är bra men man brukar nöja sig med medianen av 3 (ett från början ett från slutet och ett från mitten av listan).
- Hızlı Sıralama günümüzde yaygın olarak kullanılan bir sıralama algoritmasıdır. Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda, <math>\mathcal{O}(n~log)</math> karmaşılığıyla, en kötü durumda ise <math>\mathcal{O}(n^2)</math> karmaşıklığıyla sıralar. Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına eşittir.
- Швидке сортування — алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Хоаром, який не потребує додаткової пам'яті і виконує у середньому <math>\;O(n\log\;n)</math> операцій. Однак, у найгіршому випадку робить <math>O(n^2)</math> порівнянь.
- 快速排序是一種排序算法，由C. A. R.
|
![[RDF Data]](/statics/sw-cube.png)
