Quicksort (original) (raw)

About DBpedia

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) při obvyklé implementaci. Další výhodou algoritmu je jeho jednoduchost. Objevil jej britský počítačový vědec Charles Antony Richard Hoare v roce 1961.

thumbnail

Property Value
dbo:abstract الترتيب السريع (بالإنجليزية: Quicksort) هي خوارزمية لترتيب المصفوفات (تصاعديّا أو تنازليّا) من ابتكار الإنجليزي توني هور في 1961. ترتيب سريع هي خوارزمية فرز فعالة. تم تطويره بواسطة عالم الكمبيوتر البريطاني توني هور في عام 1959 ونشر في عام 1961، ولا يزال خوارزمية الفرز شائعة الاستخدام. عندما يتم تنفيذه بشكل جيد، يمكن أن يكون أسرع إلى حد ما من دمج الفرز وحوالي مرتين أو ثلاث مرات أسرع من فرز الكومة. الترتيب السريع هو خوارزمية فرق تسد. إنه يعمل عن طريق تحديد عنصر «محوري» من المصفوفة وتقسيم العناصر الأخرى إلى مصفوفتين فرعيتين، وفقًا لما إذا كانت أقل من المحور أو أكبر منه. لهذا السبب، يطلق عليه أحيانًا فرز تبادل الأقسام. ثم يتم فرز المصفوفات الفرعية بشكل متكرر. يمكن القيام بذلك ، مما يتطلب مساحات إضافية صغيرة من الذاكرة لإجراء الفرز. كما أن الترتيبال سريع هو ، مما يعني أنه يمكنه فرز العناصر من أي نوع يتم تحديد علاقة «أقل من» (رسميًا، ترتيب إجمالي). لا تعد عمليات التنفيذ الفعالة لـ ترتيب سريع من النوع المستقر، مما يعني أنه لا يتم الاحتفاظ بالترتيب النسبي لعناصر الفرز المتساوية. يُظهر التحليل الرياضي للفرز السريع أن الخوارزمية، في المتوسط، تأخذ O (n سجل ن) مقارنات لفرز ن العناصر. في أسوأ الحالات، تقوم بإجراء مقارنات O (n 2)، على الرغم من أن هذا السلوك نادر. (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) při obvyklé implementaci. Další výhodou algoritmu je jeho jednoduchost. Objevil jej britský počítačový vědec Charles Antony Richard Hoare v roce 1961. (cs) 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 i consumeixen més recursos). (ca) Quicksort (englisch quick ‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche 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 dass er, abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack, ohne zusätzlichen Speicherplatz auskommt. 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) Στην επιστήμη των υπολογιστών η γρήγορη ταξινόμηση (Αγγλικά: Quick-sort ή ως partition-exchange sort ) είναι ένας αλγόριθμος ταξινόμησης ο οποίος αναπτύχθηκε από τον Τόνι Χορ, που κατά μέσο όρος κάνει 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 (batzuetan ordenazio azkarra edo partizio-truke bidezko ordenazioa deitzen dena) hainbat balio ordenatzeko algoritmo eraginkorrenetako bat da. Tony Hoare informatikari britainiarrak 1959an garatu eta 1961ean argitaratu zuen, ohiko ordenatze-algoritmo bat da oraindik. Ongi inplementatzen denean, beste algoritmo lehiakide nagusiak ( eta ) baino bizpahiru aldiz azkarragoa izan daiteke. Quicksort zatitu eta irabazi erako algoritmo bat da. Ordenatu behar diren elementuen artean pibot ("pivot") elementu bat hautatuz eta gainerako elementuak bi azpi-bektoretan zatituz funtzionatzen du, batetik pibota baino txikiagoak direnak eta bestetik handiagoak direnak. Gero azpi-bektore bietako bakoitza era berean ordenatzen da, modu errekurtsiboan. Hori lekuan bertan (in-place) egin daitekeenez, memoria gehigarri txikiak behar ditu ordenaketa egiteko. Quicksort konparazio bidezko ordenazioa da, hau da, edozein motatako elementuak ordenatu ditzake "gutxiago baino" erako erlazio bat (formalki, 'hurrenkera osoa', 'erabateko ordena') definituta baldin badago. Quicksort-en ezarpen eraginkorrak ez dira orden egonkorrak, hau da, orden berdineko elementuen orden erlatiboa ez da mantentzen. Quicksort-en analisi matematikoak erakusten du ezen algoritmoak, batez beste, O(n log n) konparaketak egiten dituela n elementu ordenatzeko. Kasurik okerrenean, O(n2) alderaketak egiten ditu, nahiz eta kasu hori arraroa izan. (eu) Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions. 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. For this reason, it is sometimes called partition-exchange sort. 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. Most implementations of quicksort are not stable, meaning that the relative order of equal sort items is not preserved. Mathematical analysis of quicksort shows that, on average, the algorithm takes comparisons to sort n items. In the worst case, it makes comparisons. (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. 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 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), walaupun 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) クイックソート（英: quicksort）は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 個のデータをソートする際の最良計算量および平均計算量は （ランダウの記号）である。他のソート法と比べて一般的に最も高速だと言われているが、対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はである。安定ソートではない。 (ja) 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) 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다.그리고 퀵 정렬은 정렬을 위해 평균적으로 O(log n)만큼의 memory를 필요로한다. 이는 재귀적 호출로 발생하는 것이며, 최악의 경우 O(n)의 공간복잡도를 보인다. 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다.이러한 경우의 C코드 예: 51, 52, 3, 2, 1를 정렬하면 1, 2, 3, 52, 51 이 된다. (ko) Quicksort è un algoritmo di ordinamento ricorsivo in place non stabile. Tale procedura ricorsiva viene comunemente detta partition: preso un elemento chiamato "pivot" da una struttura dati (es. array) si pongono gli elementi minori a sinistra rispetto al pivot e gli elementi maggiori a destra. L'operazione viene quindi reiterata sui due insiemi risultanti fino al completo ordinamento della struttura. Il Quicksort, termine che tradotto letteralmente in italiano indica ordinamento rapido, è l'algoritmo di ordinamento che ha, nel caso medio, prestazioni migliori tra quelli basati su confronto. È stato ideato da Charles Antony Richard Hoare nel 1961. (it) 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), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем обменов при упорядочении элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. (ru) Quicksort är en sorteringsalgoritm som används för att sortera objekt efter ett visst mått. Upphovsman anses vara (en). Den sorterar objekt med tidskomplexitet i värsta fall och med en genomsnittlig tidskomplexitet . (sv) 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），又稱分区交換排序（partition-exchange sort），簡稱快排，一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序個項目要（大O符号）次比較。在最壞狀況下則需要次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他演算法更快，因為它的內部循环（inner loop）可以在大部分的架構上很有效率地達成。 (zh) Швидке сортування (англ. Quick Sort) — алгоритм сортування, розроблений Тоні Гоаром, який не потребує додаткової пам'яті і виконує у середньому операцій. Однак, у найгіршому випадку робить порівнянь. Позаяк алгоритм використовує дуже прості цикли і операції, він працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям. Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв'язному списку. Швидке сортування є алгоритмом на основі порівнянь і не є стабільним. (uk)
dbo:thumbnail wiki-commons:Special:FilePath/Sorting_quicksort_anim.gif?width=300
dbo:wikiPageExternalLink http://opendatastructures.org/versions/edition-0.1e/ods-java/11_1_Comparison_Based_Sorti.html%23SECTION001412000000000000000 http://www.cs.rpi.edu/~musser/gp/introsort.ps http://www.sorting-algorithms.com/quick-sort http://www.sorting-algorithms.com/quick-sort-3-way https://web.archive.org/web/20150302145415/http:/www.sorting-algorithms.com/quick-sort https://web.archive.org/web/20150306071949/http:/www.sorting-algorithms.com/quick-sort-3-way https://web.archive.org/web/20180629183103/http:/www.tomgsmith.com/quicksort/content/illustration/ http://portal.acm.org/citation.cfm%3Fid=SERIES11430.63445 http://www.cs.swan.ac.uk/~csfm/Courses/CS_332/quicksort.pdf
dbo:wikiPageID 3268249 (xsd:integer)
dbo:wikiPageLength 71148 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1123786962 (xsd:integer)
dbo:wikiPageWikiLink dbr:Robert_Sedgewick_(computer_scientist) dbr:Pat_Morin dbr:Tail_call dbr:Binary_search_tree dbr:Binary_tree_sort dbr:Binomial_coefficient dbr:Jon_Bentley_(computer_scientist) dbr:Best,_worst_and_average_case dbr:Unix dbr:Version_7_Unix dbr:Dutch_national_flag_problem dbr:Insertion_sort dbr:Integer_overflow dbr:Introduction_to_Algorithms dbr:Introsort dbr:Thomas_H._Cormen dbr:Analysis_of_algorithms dbr:Master_theorem_(analysis_of_algorithms) dbr:McGraw-Hill dbr:Median dbr:Network-attached_storage dbr:Object_(computer_science) dbr:Task_parallelism dbr:The_Computer_Journal dbr:Clifford_Stein dbr:Branch_misprediction dbr:Moscow_State_University dbc:Divide-and-conquer_algorithms dbr:SIAM_Journal_on_Computing dbr:MIT_Press dbr:Magnetic_tape_data_storage dbr:Call_stack dbr:Sixpence_(British_coin) dbr:Stable_sort dbr:Stirling's_approximation dbr:Communications_of_the_ACM dbr:Comparison_sort dbr:Parallel_algorithm dbr:Prefix_sum dbr:Median_of_medians dbc:Articles_with_example_pseudocode dbc:Comparison_sorts dbc:Sorting_algorithms dbc:1961_in_computing dbr:Timsort dbr:Tony_Hoare dbr:Total_order dbr:Disk_storage dbr:Divide-and-conquer_algorithm dbr:Linked_list dbr:Percentile dbr:Quickselect dbr:Samplesort dbr:ALGOL dbr:Expected_value dbr:Faron_Moller dbr:Parallel_random-access_machine dbr:Primitive_data_type dbr:Recurrence_relation dbr:Heapsort dbr:Java_(programming_language) dbr:Java_version_history dbr:Charles_E._Leiserson dbr:Chernoff_bound dbr:LLVM dbr:Swansea_University dbr:Tail_recursion dbr:Divide_and_conquer_algorithm dbr:Donald_Knuth dbr:Douglas_McIlroy dbr:Autocode dbr:C_standard_library dbr:Sorting_algorithm dbr:Data_cache dbr:Data_dependencies dbr:In-place_algorithm dbr:Integer_sorting dbr:Merge_sort dbr:Bucket_sort dbr:Radix_sort dbr:Recursion_(computer_science) dbr:Selection_sort dbr:Cache_memory dbr:Machine_translation dbr:Qsort dbr:Selection_algorithm dbr:Shellsort dbr:Uniform_distribution_(discrete) dbr:External_sorting dbr:Pseudocode dbr:Transdichotomous_model dbr:National_Physical_Laboratory,_UK dbr:Ninther dbr:Richard_J._Cole dbr:Parallel_Random_Access_Machine dbr:Quadratic_time dbr:Main_memory dbr:Loop_blocking dbr:Ronald_L._Rivest dbr:File:Quicksort-diagram.svg dbr:File:Quicksort-example.gif dbr:Wikt:recurse
dbp:bestTime or (en)
dbp:caption Animated visualization of the quicksort algorithm. The horizontal lines are pivot values. (en)
dbp:class dbr:Sorting_algorithm
dbp:date July 2017 (en)
dbp:optimal No (en)
dbp:section Relation to other algorithms (en)
dbp:space auxiliary (en)
dbp:stability dbr:Sorting_algorithm
dbp:wikiPageUsesTemplate dbt:= dbt:Annotated_link dbt:Cite_journal dbt:Cite_web dbt:Contradict-inline dbt:ISBN dbt:Main dbt:Math dbt:Mono dbt:Mvar dbt:Portal dbt:R dbt:Reflist dbt:Rp dbt:Section_link dbt:Sfrac dbt:Short_description dbt:Use_dmy_dates dbt:Why dbt:Wikibooks dbt:Self-published_inline dbt:PAGENAMEBASE dbt:Infobox_algorithm dbt:Sorting
dcterms:subject dbc:Divide-and-conquer_algorithms dbc:Articles_with_example_pseudocode dbc:Comparison_sorts dbc:Sorting_algorithms dbc:1961_in_computing
gold:hypernym dbr:Algorithm
rdf:type dbo:Software yago:WikicatComparisonSorts yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Category105838765 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Event100029378 yago:Idea105833840 yago:Kind105839024 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 yago:WikicatAlgorithms
rdfs:comment 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) při obvyklé implementaci. Další výhodou algoritmu je jeho jednoduchost. Objevil jej britský počítačový vědec Charles Antony Richard Hoare v roce 1961. (cs) 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 i consumeixen més recursos). (ca) Στην επιστήμη των υπολογιστών η γρήγορη ταξινόμηση (Αγγλικά: Quick-sort ή ως partition-exchange sort ) είναι ένας αλγόριθμος ταξινόμησης ο οποίος αναπτύχθηκε από τον Τόνι Χορ, που κατά μέσο όρος κάνει 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年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 個のデータをソートする際の最良計算量および平均計算量は （ランダウの記号）である。他のソート法と比べて一般的に最も高速だと言われているが、対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はである。安定ソートではない。 (ja) 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) 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), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем обменов при упорядочении элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. (ru) Quicksort är en sorteringsalgoritm som används för att sortera objekt efter ett visst mått. Upphovsman anses vara (en). Den sorterar objekt med tidskomplexitet i värsta fall och med en genomsnittlig tidskomplexitet . (sv) 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），又稱分区交換排序（partition-exchange sort），簡稱快排，一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序個項目要（大O符号）次比較。在最壞狀況下則需要次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他演算法更快，因為它的內部循环（inner loop）可以在大部分的架構上很有效率地達成。 (zh) الترتيب السريع (بالإنجليزية: Quicksort) هي خوارزمية لترتيب المصفوفات (تصاعديّا أو تنازليّا) من ابتكار الإنجليزي توني هور في 1961. ترتيب سريع هي خوارزمية فرز فعالة. تم تطويره بواسطة عالم الكمبيوتر البريطاني توني هور في عام 1959 ونشر في عام 1961، ولا يزال خوارزمية الفرز شائعة الاستخدام. عندما يتم تنفيذه بشكل جيد، يمكن أن يكون أسرع إلى حد ما من دمج الفرز وحوالي مرتين أو ثلاث مرات أسرع من فرز الكومة. يُظهر التحليل الرياضي للفرز السريع أن الخوارزمية، في المتوسط، تأخذ O (n سجل ن) مقارنات لفرز ن العناصر. في أسوأ الحالات، تقوم بإجراء مقارنات O (n 2)، على الرغم من أن هذا السلوك نادر. (ar) Quicksort (englisch quick ‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche 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 dass er, abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack, ohne zusätzlichen Speicherplatz auskommt. (de) Quicksort (batzuetan ordenazio azkarra edo partizio-truke bidezko ordenazioa deitzen dena) hainbat balio ordenatzeko algoritmo eraginkorrenetako bat da. Tony Hoare informatikari britainiarrak 1959an garatu eta 1961ean argitaratu zuen, ohiko ordenatze-algoritmo bat da oraindik. Ongi inplementatzen denean, beste algoritmo lehiakide nagusiak ( eta ) baino bizpahiru aldiz azkarragoa izan daiteke. (eu) 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 is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions. 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. Most implementations of quicksort are not stable, meaning that the relative order of equal sort items is not preserved. (en) 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), walaupun 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 è un algoritmo di ordinamento ricorsivo in place non stabile. Tale procedura ricorsiva viene comunemente detta partition: preso un elemento chiamato "pivot" da una struttura dati (es. array) si pongono gli elementi minori a sinistra rispetto al pivot e gli elementi maggiori a destra. L'operazione viene quindi reiterata sui due insiemi risultanti fino al completo ordinamento della struttura. (it) 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다.그리고 퀵 정렬은 정렬을 위해 평균적으로 O(log n)만큼의 memory를 필요로한다. 이는 재귀적 호출로 발생하는 것이며, 최악의 경우 O(n)의 공간복잡도를 보인다. (ko) Швидке сортування (англ. Quick Sort) — алгоритм сортування, розроблений Тоні Гоаром, який не потребує додаткової пам'яті і виконує у середньому операцій. Однак, у найгіршому випадку робить порівнянь. Позаяк алгоритм використовує дуже прості цикли і операції, він працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям. Швидке сортування є алгоритмом на основі порівнянь і не є стабільним. (uk)
rdfs:label ترتيب سريع (ar) Quicksort (ca) Rychlé řazení (cs) Quicksort (de) Γρήγορη ταξινόμηση (el) Rapida ordigo (eo) Quicksort (es) Quicksort (eu) Tri rapide (fr) Quicksort (in) Quicksort (it) 퀵 정렬 (ko) クイックソート (ja) Quicksort (nl) Quicksort (en) Sortowanie szybkie (pl) Быстрая сортировка (ru) Quicksort (pt) Quicksort (sv) 快速排序 (zh) Швидке сортування (uk)
owl:sameAs freebase:Quicksort yago-res:Quicksort wikidata:Quicksort dbpedia-ar:Quicksort dbpedia-az:Quicksort dbpedia-bg:Quicksort http://bn.dbpedia.org/resource/কুইক_সর্ট dbpedia-ca:Quicksort dbpedia-cs:Quicksort dbpedia-de:Quicksort dbpedia-el:Quicksort dbpedia-eo:Quicksort dbpedia-es:Quicksort dbpedia-et:Quicksort dbpedia-eu:Quicksort dbpedia-fa:Quicksort dbpedia-fi:Quicksort dbpedia-fr:Quicksort dbpedia-he:Quicksort http://hi.dbpedia.org/resource/क्विक_सॉर्ट dbpedia-hu:Quicksort http://hy.dbpedia.org/resource/Արագ_տեսակավորում dbpedia-id:Quicksort dbpedia-is:Quicksort dbpedia-it:Quicksort dbpedia-ja:Quicksort dbpedia-ka:Quicksort dbpedia-kk:Quicksort dbpedia-ko:Quicksort dbpedia-lmo:Quicksort http://lt.dbpedia.org/resource/Greitojo_rikiavimo_algoritmas http://lv.dbpedia.org/resource/Ātrās_kārtošanas_algoritms dbpedia-nl:Quicksort dbpedia-no:Quicksort dbpedia-pl:Quicksort dbpedia-pt:Quicksort dbpedia-ro:Quicksort dbpedia-ru:Quicksort dbpedia-sh:Quicksort dbpedia-simple:Quicksort dbpedia-sk:Quicksort dbpedia-sl:Quicksort dbpedia-sr:Quicksort dbpedia-sv:Quicksort dbpedia-th:Quicksort dbpedia-tr:Quicksort dbpedia-uk:Quicksort http://uz.dbpedia.org/resource/Quicksort dbpedia-vi:Quicksort dbpedia-zh:Quicksort https://global.dbpedia.org/id/4WAKo
prov:wasDerivedFrom wikipedia-en:Quicksort?oldid=1123786962&ns=0
foaf:depiction wiki-commons:Special:FilePath/Sorting_quicksort_anim.gif wiki-commons:Special:FilePath/Quicksort-diagram.svg wiki-commons:Special:FilePath/Quicksort-example.gif
foaf:isPrimaryTopicOf wikipedia-en:Quicksort
is dbo:knownFor of dbr:Tony_Hoare
is dbo:wikiPageDisambiguates of dbr:QS
is dbo:wikiPageRedirects of dbr:QuickSort dbr:Quick_sort dbr:Quick3 dbr:Quick3_sort dbr:Hoaresort dbr:Parallel_quicksort dbr:Quick_Sort dbr:Randomized_quicksort dbr:Partition-exchange_sort dbr:Partition_exchange_sort dbr:Balanced_quicksort dbr:External_quicksort
is dbo:wikiPageWikiLink of dbr:Cache-oblivious_distribution_sort dbr:American_flag_sort dbr:Program_optimization dbr:Prolog dbr:Proportion_extend_sort dbr:QuickSort dbr:Quick_sort dbr:Robert_Sedgewick_(computer_scientist) dbr:Scala_(programming_language) dbr:List_of_algorithms dbr:Primality_Testing_for_Beginners dbr:Binary_logarithm dbr:Binary_search_algorithm dbr:Binary_search_tree dbr:Block_sort dbr:David_Pentecost dbr:Algorithmic_efficiency dbr:Jon_Bentley_(computer_scientist) dbr:Best,_worst_and_average_case dbr:List_of_pioneers_in_computer_science dbr:Pathological_(mathematics) dbr:Patience_sorting dbr:Peter_Landin dbr:University_of_Oxford dbr:C++_Standard_Library dbr:Dutch_national_flag_problem dbr:Input_enhancement_(computer_science) dbr:Insertion_sort dbr:Introselect dbr:Introsort dbr:Library_sort dbr:List_of_programmers dbr:Random_permutation_statistics dbr:Q_sort dbr:Quick3 dbr:Quick3_sort dbr:Analysis_of_algorithms dbr:Median dbr:Low-discrepancy_sequence dbr:One-liner_program dbr:Ostrich_algorithm dbr:NP-easy dbr:Python_syntax_and_semantics dbr:Quickhull dbr:Timeline_of_algorithms dbr:Timeline_of_mathematics dbr:Glossary_of_computer_science dbr:Convex_hull_algorithms dbr:Logarithm dbr:Lutz_Michael_Wegner dbr:MVEL dbr:Cache-oblivious_algorithm dbr:Comment_(computer_programming) dbr:Comparison_sort dbr:Competitive_analysis_(online_algorithm) dbr:Computational_complexity dbr:Computational_complexity_theory dbr:Computationally_bounded_adversary dbr:Functional_fixedness dbr:Harmonic_series_(mathematics) dbr:Kruskal's_algorithm dbr:Performance_tuning dbr:Pivot dbr:Pivot_element dbr:Total_functional_programming dbr:Median_of_medians dbr:1960_in_science dbr:1960s dbr:Bubble_sort dbr:Time_complexity dbr:Tony_Hoare dbr:Treap dbr:Tree_sort dbr:Divide-and-conquer_algorithm dbr:Las_Vegas_algorithm dbr:Quickselect dbr:Samplesort dbr:Dynamic_programming dbr:Erlang_(programming_language) dbr:Flashsort dbr:Parametric_search dbr:Partial_sorting dbr:Joy_(programming_language) dbr:QS dbr:Heapsort dbr:J_(programming_language) dbr:Hybrid_algorithm dbr:John_M._Scholes dbr:Big_O_notation dbr:Reinventing_the_wheel dbr:Direct_function dbr:Average-case_complexity dbr:Sorting_algorithm dbr:Spreadsort dbr:ITMO_University dbr:In-place_algorithm dbr:Merge_sort dbr:Merton_College,_Oxford dbr:Bucket_sort dbr:OCaml dbr:Radix_sort dbr:Raku_(programming_language) dbr:Random_geometric_graph dbr:Randomized_algorithm dbr:Recursion_(computer_science) dbr:Qsort dbr:Selection_algorithm dbr:Shellsort dbr:Software dbr:Sort_(C++) dbr:Nested_function dbr:External_memory_algorithm dbr:External_sorting dbr:In_situ dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Ruzzo–Tompa_algorithm dbr:Fisher–Yates_shuffle dbr:Multi-key_quicksort dbr:Self-balancing_binary_search_tree dbr:Sorted_array dbr:Soft_heap dbr:Splaysort dbr:Parallel_algorithms_for_minimum_spanning_trees dbr:Sequential_access dbr:Hoaresort dbr:Parallel_quicksort dbr:Quick_Sort dbr:Randomized_quicksort dbr:Partition-exchange_sort dbr:Partition_exchange_sort dbr:Balanced_quicksort dbr:External_quicksort
is foaf:primaryTopic of wikipedia-en:Quicksort