| 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)
|
| 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)
|