Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort. Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

Property Value
dbo:abstract
  • الترتيب السريع (Quicksort) هي خوارزمية لترتيب المصفوفات (تصاعديّا أو تنازليّا) من ابتكار الإنجليزي توني هور في 1961. (ar)
  • Rychlé řazení nebo rychlé třídění, známý také pod anglickým názvem quicksort je jeden z nejrychlejších běžný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á (O(N log N)), v nejhorším případě (kterému se ale v praxi jde obvykle vyhnout) je však jeho časová náročnost O(N2). Další výhodou algoritmu je jeho jednoduchost. Objevil jej britský počítačový vědec Charles Antony Richard Hoare v roce 1961. (cs)
  • Στην επιστήμη των υπολογιστών η γρήγορη ταξινόμηση (Αγγλικά: Quick-sort ή ως partition-exchange sort ) είναι ένας αλγόριθμος ταξινόμησης ο οποίος αναπτύχθηκε από τον Tony Hoare, που κατά μέσο όρος κάνει O(nlogn) συγκρίσεις για να ταξινομήσει n στοιχεία. Στην χειρότερη, σπάνια περίπτωση κάνει O(n2) συγκρίσεις. Ο αλγόριθμος γρήγορης ταξινόμησης συχνά είναι γρηγορότερος από αντίστοιχους άλλους O(nlogn) αλγορίθμους και κατατάσσεται στους αλγορίθμους διαίρει και βασίλευε (όπου το πρόβλημα διασπάται σε μικρότερα προβλήματα και λύνεται το κάθε πρόβλημα ξεχωριστά). Ο αλγόριθμος αυτός μπορεί να υλοποιηθεί με αναδρομική συνάρτηση. (el)
  • En angla kaj en kelkaj lingvoj Quicksort kaj esperante „rapida ordigo“ estas unu el la plej rapidaj kutimaj bazitaj sur komparado de elementoj. Ĝia averaĝa tempa komplekseco estas la plej bona por algoritmoj de la grupo (O(N log N)), en la plej malbona kazo (kiun eblas kutime eviti) estas ĝia tempa komplekseco O(N2). Plia avantaĝo de la algoritmo estas ĝia simpleco. Siro Charles Antony Richard Hoare malkovris ĝin en 1961. (eo)
  • Quicksort (englisch quick ‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (lateinisch Divide et impera!, englisch 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). Im Durchschnitt führt der Quicksort-Algorithmus Vergleiche durch. Im schlechtesten Fall werden Vergleiche durchgeführt, was aber in der Praxis sehr selten vorkommt. (de)
  • Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort. Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting. Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved. Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. (en)
  • El ordenamiento rápido (quicksort en inglés) es un algoritmo de ordenacion creado por el científico británico en computación C. A. R. Hoare. (es)
  • Quicksort merupakan Algoritme pengurutan yang dikembangkan oleh Tony Hoare. performa rata-rata pengurutan O(n log n) untuk mengurutkan n item. Algoritme ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting Pergantian Pembagi. Pada kasus terburuknya, algoritme ini membuat perbandingan O(n2), malaupun kejadian seperti ini sangat langka. Quicksort sering lebih cepat dalam praktiknya daripada algoritme urut gabung dan heapshort. Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n). Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan algoritme sorting yang stabil. (in)
  • En informatique, le tri rapide ou tri pivot (en anglais quicksort) 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 des cas est en effet peu probable lorsque l'algorithme est correctement mis en œuvre et il est possible de s'en prémunir définitivement avec la variante Introsort. 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. (fr)
  • クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 n個のデータをソートする際の最良計算量および平均計算量はOである。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はOである。また数々の変種がある。安定ソートではない。 (ja)
  • 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다.그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로한다. 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다.이러한 경우의 C코드 예: 51, 52, 3, 2, 1 를 정렬하면 1, 2, 3, 52, 51 이 된다. (ko)
  • Sortowanie szybkie (ang. quicksort) – jeden z popularnych algorytmów sortowania działających na zasadzie „dziel i zwyciężaj”. Sortowanie szybkie (ang. QuickSort) zostało wynalezione w 1962 przez C.A.R. Hoare’a. Algorytm sortowania szybkiego jest wydajny: jego średnia złożoność obliczeniowa jest rzędu . Ze względu na szybkość i prostotę implementacji jest powszechnie używany. Jego implementacje znajdują się w bibliotekach standardowych wielu środowisk programowania. (pl)
  • Quicksort is een recursief sorteeralgoritme bedacht door Tony Hoare. Hij werkte destijds aan een project in verband met computervertalingen. Daarvoor was het nodig om korte Russische zinnen snel en efficiënt te sorteren. Het algemene werkingsprincipe van quicksort wordt weleens kort omschreven als verdeel en heers. (nl)
  • 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 para o .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 fácil e rápido.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. (pt)
  • Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем обменов при упорядочении элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. (ru)
  • Quicksort är en sorteringsalgoritm som används för att sortera objekt efter ett visst mått. Upphovsman anses vara . Den sorterar objekt med tidskomplexitet i värsta fall och med en genomsnittlig tidskomplexitet . (sv)
  • Швидке сортування (англ. Quick Sort) — алгоритм сортування, добре відомий як алгоритм, розроблений Тоні Гоаром, який не потребує додаткової пам'яті і виконує у середньому операцій. Однак, у найгіршому випадку робить порівнянь. Позаяк алгоритм використовує дуже прості цикли і операції, він працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям. Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв'язному списку. Швидке сортування є алгоритмом на основі порівнянь і не є стабільним. (uk)
  • 快速排序(英語:Quicksort),又稱劃分交換排序(partition-exchange sort),簡稱快排,一種排序算法,最早由東尼·霍爾提出。在平均狀況下,排序個項目要(大O符号)次比較。在最壞狀況下則需要次比較,但這種狀況並不常見。事實上,快速排序通常明顯比其他演算法更快,因為它的內部循环(inner loop)可以在大部分的架構上很有效率地達成。 (zh)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 3268249 (xsd:integer)
dbo:wikiPageLength
  • 60198 (xsd:integer)
dbo:wikiPageRevisionID
  • 986042109 (xsd:integer)
dbo:wikiPageWikiLink
dbp:averageTime
  • O (en)
dbp:bestTime
  • O (en)
  • or O (en)
dbp:caption
  • Animated visualization of the quicksort algorithm. The horizontal lines are pivot values. (en)
dbp:class
dbp:date
  • July 2017 (en)
dbp:optimal
  • No (en)
dbp:section
  • Relation to other algorithms (en)
dbp:space
  • O auxiliary (en)
dbp:stability
dbp:time
  • O (en)
dbp:wikiPageUsesTemplate
dct:subject
rdf:type
rdfs:comment
  • الترتيب السريع (Quicksort) هي خوارزمية لترتيب المصفوفات (تصاعديّا أو تنازليّا) من ابتكار الإنجليزي توني هور في 1961. (ar)
  • Rychlé řazení nebo rychlé třídění, známý také pod anglickým názvem quicksort je jeden z nejrychlejších běžný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á (O(N log N)), v nejhorším případě (kterému se ale v praxi jde obvykle vyhnout) je však jeho časová náročnost O(N2). Další výhodou algoritmu je jeho jednoduchost. Objevil jej britský počítačový vědec Charles Antony Richard Hoare v roce 1961. (cs)
  • Στην επιστήμη των υπολογιστών η γρήγορη ταξινόμηση (Αγγλικά: Quick-sort ή ως partition-exchange sort ) είναι ένας αλγόριθμος ταξινόμησης ο οποίος αναπτύχθηκε από τον Tony Hoare, που κατά μέσο όρος κάνει O(nlogn) συγκρίσεις για να ταξινομήσει n στοιχεία. Στην χειρότερη, σπάνια περίπτωση κάνει O(n2) συγκρίσεις. Ο αλγόριθμος γρήγορης ταξινόμησης συχνά είναι γρηγορότερος από αντίστοιχους άλλους O(nlogn) αλγορίθμους και κατατάσσεται στους αλγορίθμους διαίρει και βασίλευε (όπου το πρόβλημα διασπάται σε μικρότερα προβλήματα και λύνεται το κάθε πρόβλημα ξεχωριστά). Ο αλγόριθμος αυτός μπορεί να υλοποιηθεί με αναδρομική συνάρτηση. (el)
  • En angla kaj en kelkaj lingvoj Quicksort kaj esperante „rapida ordigo“ estas unu el la plej rapidaj kutimaj bazitaj sur komparado de elementoj. Ĝia averaĝa tempa komplekseco estas la plej bona por algoritmoj de la grupo (O(N log N)), en la plej malbona kazo (kiun eblas kutime eviti) estas ĝia tempa komplekseco O(N2). Plia avantaĝo de la algoritmo estas ĝia simpleco. Siro Charles Antony Richard Hoare malkovris ĝin en 1961. (eo)
  • El ordenamiento rápido (quicksort en inglés) es un algoritmo de ordenacion creado por el científico británico en computación C. A. R. Hoare. (es)
  • クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 n個のデータをソートする際の最良計算量および平均計算量はOである。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はOである。また数々の変種がある。安定ソートではない。 (ja)
  • Sortowanie szybkie (ang. quicksort) – jeden z popularnych algorytmów sortowania działających na zasadzie „dziel i zwyciężaj”. Sortowanie szybkie (ang. QuickSort) zostało wynalezione w 1962 przez C.A.R. Hoare’a. Algorytm sortowania szybkiego jest wydajny: jego średnia złożoność obliczeniowa jest rzędu . Ze względu na szybkość i prostotę implementacji jest powszechnie używany. Jego implementacje znajdują się w bibliotekach standardowych wielu środowisk programowania. (pl)
  • Quicksort is een recursief sorteeralgoritme bedacht door Tony Hoare. Hij werkte destijds aan een project in verband met computervertalingen. Daarvoor was het nodig om korte Russische zinnen snel en efficiënt te sorteren. Het algemene werkingsprincipe van quicksort wordt weleens kort omschreven als verdeel en heers. (nl)
  • 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 para o .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 fácil e rápido.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. (pt)
  • Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем обменов при упорядочении элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. (ru)
  • Quicksort är en sorteringsalgoritm som används för att sortera objekt efter ett visst mått. Upphovsman anses vara . Den sorterar objekt med tidskomplexitet i värsta fall och med en genomsnittlig tidskomplexitet . (sv)
  • 快速排序(英語:Quicksort),又稱劃分交換排序(partition-exchange sort),簡稱快排,一種排序算法,最早由東尼·霍爾提出。在平均狀況下,排序個項目要(大O符号)次比較。在最壞狀況下則需要次比較,但這種狀況並不常見。事實上,快速排序通常明顯比其他演算法更快,因為它的內部循环(inner loop)可以在大部分的架構上很有效率地達成。 (zh)
  • Quicksort (englisch quick ‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (lateinisch Divide et impera!, englisch 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). (de)
  • Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort. Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. (en)
  • En informatique, le tri rapide ou tri pivot (en anglais quicksort) 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. 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. (fr)
  • Quicksort merupakan Algoritme pengurutan yang dikembangkan oleh Tony Hoare. performa rata-rata pengurutan O(n log n) untuk mengurutkan n item. Algoritme ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting Pergantian Pembagi. Pada kasus terburuknya, algoritme ini membuat perbandingan O(n2), malaupun kejadian seperti ini sangat langka. Quicksort sering lebih cepat dalam praktiknya daripada algoritme urut gabung dan heapshort. Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n). (in)
  • 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다.그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로한다. (ko)
  • Швидке сортування (англ. Quick Sort) — алгоритм сортування, добре відомий як алгоритм, розроблений Тоні Гоаром, який не потребує додаткової пам'яті і виконує у середньому операцій. Однак, у найгіршому випадку робить порівнянь. Позаяк алгоритм використовує дуже прості цикли і операції, він працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям. Швидке сортування є алгоритмом на основі порівнянь і не є стабільним. (uk)
rdfs:label
  • ترتيب سريع (ar)
  • Rychlé řazení (cs)
  • Quicksort (de)
  • Γρήγορη ταξινόμηση (el)
  • Rapida ordigo (eo)
  • Quicksort (es)
  • Quicksort (en)
  • Tri rapide (fr)
  • Quicksort (in)
  • クイックソート (ja)
  • 퀵 정렬 (ko)
  • Sortowanie szybkie (pl)
  • Quicksort (nl)
  • Quicksort (pt)
  • Быстрая сортировка (ru)
  • Швидке сортування (uk)
  • Quicksort (sv)
  • 快速排序 (zh)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:knownFor of
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of