Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes comparisons to sort n items. In the worst case, it makes comparisons, though this behavior is rare. Quicksort is often faster in practice than other algorithms. Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented as an in-place sort, requiring only additional space.

PropertyValue
dbpedia-owl:abstract
  • Quicksort 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).
  • El ordenamiento rápido es un algoritmo creado por el matemático John von Neumann 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.
  • Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes comparisons to sort n items. In the worst case, it makes comparisons, though this behavior is rare. Quicksort is often faster in practice than other algorithms. Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented as an in-place sort, requiring only additional space. Quicksort (also known as "partition-exchange sort") is a comparison sort and, in space efficient implementations, is not a stable sort.
  • 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.
  • 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 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 sì 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.
  • クイックソート (quick sort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 最良計算量および平均計算量はOである。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はOである。また数々の変種がある。 安定ソートではない。
  • Bestand:Sorting quicksort anim. gif Animatie quicksort Bestand:Quicksort example small. png Quicksort-voorbeeld Bestand:Partition example. svg Quicksort-voorbeeld op een kleine lijst van getallen 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. Naquela época, Hoare trabalhou em um projeto de tradução de máquina para o National Physical Laboratory. 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 por comparação não-estável.
  • Быстрая сортировка, часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.
  • 快速排序是一種排序算法，由C. A. R. Hoare所發展的，以平均效能來說，排序 n 個項目要Θ(n log n)次比較。然而，在最壞的效能下，它需要Θ(n)次比較。一般來說，快速排序實際上明顯地比其他Θ(n log n) 演算法更快，因為它的內部循环（inner loop）可以在大部分的架構上很有效率地被實作出來，且在大部分真實世界的資料，可以決定設計的選擇，減少所需時間的二次方項之可能性。
  • 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).
  • Le tri rapide est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes. Dans le cas des tableaux, c'est un tri en place mais non stable. La complexité moyenne du tri rapide pour n éléments est proportionnelle à n log n, ce qui est optimal pour un tri par comparaison, mais la complexité dans le pire des cas est quadratique. Malgré ce désavantage théorique, c'est en pratique un des tris les plus rapides, et donc un des plus utilisés. Le pire cas est en effet peu probable lorsque l'algorithme est correctement implémenté. Le tri rapide ne peut cependant pas tirer avantage du fait que l'entrée est déjà presque triée. Dans ce cas particulier, il est plus avantageux d'utiliser le tri par insertion ou l'algorithme Smoothsort. Fichier:Sorting quicksort anim. gif Quicksort en action sur une liste de nombre aléatoires Les lignes horizontales sont les valeurs des pivots. Fichier:Quicksort example small. png Autre illustration de l'algorithme de tri rapide (Quicksort). Fichier:Partition example. svg Exemple de tri d'une petite liste de nombres
dbpedia-owl:thumbnail
dbpedia-owl:wikiPageExternalLink
dbpprop:averageTime
  • O
dbpprop:bestTime
  • O
dbpprop:caption
  • Visualization of the quicksort algorithm. The horizontal lines are pivot values.
dbpprop:class
dbpprop:optimal
  • No
dbpprop:space
  • O
dbpprop:stability
  • [Sorting_algorithm#Classification
dbpprop:time
  • O
dbpprop:wikiPageUsesTemplate
dcterms:subject
rdf:type
rdfs:comment
  • El ordenamiento rápido es un algoritmo creado por el matemático John von Neumann 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.
  • クイックソート (quick sort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 最良計算量および平均計算量はOである。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はOである。また数々の変種がある。 安定ソートではない。
  • Bestand:Sorting quicksort anim. gif Animatie quicksort Bestand:Quicksort example small. png Quicksort-voorbeeld Bestand:Partition example. svg Quicksort-voorbeeld op een kleine lijst van getallen 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.
  • Быстрая сортировка, часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.
  • 快速排序是一種排序算法，由C. A. R. Hoare所發展的，以平均效能來說，排序 n 個項目要Θ(n log n)次比較。然而，在最壞的效能下，它需要Θ(n)次比較。一般來說，快速排序實際上明顯地比其他Θ(n log n) 演算法更快，因為它的內部循环（inner loop）可以在大部分的架構上很有效率地被實作出來，且在大部分真實世界的資料，可以決定設計的選擇，減少所需時間的二次方項之可能性。
  • 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).
  • Quicksort 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.
  • Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes comparisons to sort n items. In the worst case, it makes comparisons, though this behavior is rare. Quicksort is often faster in practice than other algorithms. Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented as an in-place sort, requiring only additional space.
  • 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.
  • 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. Naquela época, Hoare trabalhou em um projeto de tradução de máquina para o National Physical Laboratory. 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.
  • Le tri rapide est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes. Dans le cas des tableaux, c'est un tri en place mais non stable. La complexité moyenne du tri rapide pour n éléments est proportionnelle à n log n, ce qui est optimal pour un tri par comparaison, mais la complexité dans le pire des cas est quadratique.
rdfs:label
  • Quicksort
  • Quicksort
  • Pikalajittelu
  • Tri rapide
  • Quicksort
  • クイックソート
  • Quicksort
  • Quicksort
  • Sortowanie szybkie
  • Quicksort
  • Быстрая сортировка
  • Quicksort
  • 快速排序
owl:sameAs
foaf:depiction
foaf:page
is dbpedia-owl:knownFor of
is dbpedia-owl:wikiPageDisambiguates of
is dbpedia-owl:wikiPageRedirects of
is dbpprop:knownFor of
is owl:sameAs of
is foaf:primaryTopic of