Sorting algorithm (original) (raw)
في المعلوماتية أو الرياضيات، خوارزمية الترتيب هي خوارزمية تمكن من تنظيم مجموعة عناصر حسب ترتيب محدد. العناصر المراد ترتيبها توجد في مجموعة مزودة بعلاقة ترتيب.
| Property | Value |
|---|---|
| dbo:abstract | في المعلوماتية أو الرياضيات، خوارزمية الترتيب هي خوارزمية تمكن من تنظيم مجموعة عناصر حسب ترتيب محدد. العناصر المراد ترتيبها توجد في مجموعة مزودة بعلاقة ترتيب. (ar) En informàtica i matemàtiques un algorisme d'ordenació és un algorisme que posa elements d'una seguint l'ordre donat per una relació d'ordre. Les relacions d'ordre més usades són l'ordre numèric i l'ordre lexicogràfic. Ordenar eficientment és important per a posteriorment usar en forma d'altres algorismes com els de , , (per exemple, per a la comparació de llistes), atès que per a aplicar certs algorismes és necessari que prèviament els elements es trobin ordenats. També és útil per a posar dades en forma canònica i per a generar resultats llegibles per a humans. (ca) Řadicí nebo třídicí algoritmus je algoritmus zajišťující uspořádání dané sady (pole, seznamu, souboru) datových záznamů do požadovaného pořadí. Pro porovnávání se obvykle nepoužívá celý záznam, ale jeho jedna nebo více jeho položek nazývaných klíče. Tyto položky bývají zpravidla numerické, které se řadí podle hodnoty nebo řetězcové, které se řadí abecedně. Řazení je velmi častá úloha, která je také částí mnoha dalších algoritmů; vývoji co možná nejefektivnějších algoritmů řazení se proto věnuje velké úsilí. Z hlediska řazení se vstupní data chápou jako soubor dvojic klíč–hodnota, přičemž po seřazení je posloupnost klíčů monotónní, zatímco na připojené hodnoty se při řazení nebere zřetel a pouze se přesouvají vždy s odpovídajícím klíčem. Podle toho, zda se zachovává pořadí položek se stejným klíčem, rozlišuje algoritmy řazení na stabilní a nestabilní. (cs) Στην επιστήμη των υπολογιστών ο αλγόριθμος ταξινόμησης είναι ένας αλγόριθμος που μεταθέτει τα στοιχεία μίας ακολουθίας έτσι ώστε να έχουν μία συγκεκριμένη σειρά. Παραδείγματα τέτοιων σειρών αποτελούν η και η . Πιο συγκεκριμένα ένας αλγόριθμος ταξινόμησης είναι ένας αλγόριθμος που δοσμένης μίας ακολουθίας εισόδου και μίας συνάρτησης δίαταξης , παράγει μία ακολουθία εξόδου τέτοια ώστε: 1. * 2. * Η ακολουθία αποτελεί μετάθεση της Η συνάρτηση είναι αυτή που καθορίζει τη σειρά ταξινόμησης. Έτσι επιλέγοντας η σειρά ταξινόμησης είναι η φθίνουσα. (el) Unter einem Sortierverfahren versteht man in der Informatik einen Algorithmus, der dazu dient, ein Tupel (i. Allg. ein Array) zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist („kleiner-gleich“), z. B. die lexikographische Ordnung von Zeichenketten oder die numerische Ordnung von Zahlen. Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten bezüglich der Zeitkomplexität (Anzahl der nötigen Operationen) sowie der Platzkomplexität (zusätzlich zum Eingabe-Array benötigter weiterer Speicherplatz). Die Komplexität eines Algorithmus wird üblicherweise in der Landau-Notation dargestellt (s. u. Ausdrücke wie ). Die Zeitkomplexität hängt bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bei günstigster „Vorsortierung“), Average Case (Normalfall) und Worst Case (schlechtester Fall ~ die Werte sind „maximal ungünstig vorgeordnet“).Häufig sind zusätzliche Faktoren zu beachten, die Einfluss auf Zeit- oder Platzkomplexität haben, zum Beispiel langsamer Zugriff auf extern liegende Daten, begrenzte Größe des Arbeitsspeichers oder ähnliches. Man unterscheidet zudem zwischen stabilen und instabilen Sortierverfahren. Stabile Sortierverfahren sind solche, die die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind, nicht verändern, während instabile Sortierverfahren dies nicht garantieren. Ist beispielsweise die Mitarbeiterliste einer Firma nach Nachname geordnet und wird anschließend nach Alter (in Jahren) sortiert, so bleibt die (Nachnamen-)Reihenfolge unter gleichaltrigen Mitarbeitern bei einem stabilen Sortierverfahren bestehen. Zudem unterscheidet man zwischen Sortierverfahren, die in-place (auch in situ) arbeiten, d. h. der zusätzliche Speicherbedarf ist unabhängig von der Anzahl der zu sortierenden Elemente (also konstant und meist gering), und solchen, bei denen er abhängig ist (out-of-place oder ex situ). Und man unterscheidet auch zwischen natürlichen Sortierverfahren, die bei vorsortierten Daten schneller arbeiten als bei unsortierten Daten, und solchen, die es nicht tun. Algorithmen, bei denen der Kontrollfluss von den Daten abhängt, nennt man adaptiv und dementsprechend Sortierverfahren, die nicht von den Eingabedaten abhängen, nicht-adaptiv. Nicht-adaptive Algorithmen sind demnach besonders interessant für Hardware-Implementierungen. Manuelles Sortieren (etwa von Karteikarten) sowie elektro-mechanische Sortierverfahren (z. B. für Lochkarten) entsprechen meist einem der hier beschriebenen softwarebasierten Sortierverfahren, oder Mischtypen. (de) En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos. Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, BubbleSort fue analizado desde 1956. Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventado hasta el día de hoy (por ejemplo, el ordenamiento de biblioteca se publicó por primera vez en el 2004). Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores. (es) Konputazioan eta matematiketan ordenazio algoritmoa zerrenda edo bektore baten elementuak ordena-erlazio batek emandako sekuentzia batean jartzen duen algoritmoa da, hau da, irteeraren emaitza sarrerako permutazio bat edo berrantolaketa izan behar da. Ordena erlazio erabilienak orden numerikoa eta orden lexikografikoa dira .Antolamendu eraginkorrak garrantzitsuak dira azkar exekutatzeko, zerrenda ordenatuak behar dituzten beste algoritmo batzuen (hala nola bilaketa- eta fusio-algoritmoen) erabilera optimizatzeko. Datuak kanonikoki jartzeko eta gizakiek irakurtzeko moduko emaitzak sortzeko ere balio du. Informatika hasi zenetik, ordenatzeko arazoak ikerketa asko erakarri ditu, agian, modu erraz eta familiarra izan arren, modu eraginkorrean ebazteko konplexutasuna dela eta. Adibidez, BubbleSort 1956. urteaz geroztik aztertu da. Askok konpondutako arazoa dela uste badute ere, gaur egun ordenatzeko algoritmo erabilgarriak asmatzen jarraitzen dute (adibidez, liburutegi sorta 2004an argitaratu zen lehenengo aldiz). Ordenatzeko algoritmoak informatikako sarrera klaseetan ohikoak dira,non problemarako algoritmoen ugaritasunak sarrera atsegina ematen baitu algoritmoen nukleo-kontzeptuen aniztasunari buruz, esate baterako, O notazioa, zatitu eta konkistatzeko algoritmoak, datu egiturak., txarrena, onena eta batez besteko kasuen azterketa eta muga txikiagoak. (eu) Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur. La collection à trier est souvent donnée sous forme de tableau, afin de permettre l'accès direct aux différents éléments de la collection, ou sous forme de liste, ce qui peut se révéler être plus adapté à certains algorithmes et à l'usage de la programmation fonctionnelle. Bon nombre d'algorithmes de tri procèdent par comparaisons successives, et peuvent donc être définis indépendamment de l'ensemble auquel appartiennent les éléments et de la relation d’ordre associée. Un même algorithme peut par exemple être utilisé pour trier des réels selon la relation d'ordre usuelle « est inférieur ou égal à » et des chaînes de caractères selon l'ordre lexicographique. Ces algorithmes se prêtent naturellement à une implémentation polymorphe. Les algorithmes de tri sont souvent étudiés dans les cours d'algorithmique pour introduire des notions comme la complexité algorithmique ou la terminaison. La classification des algorithmes de tri est très importante, car elle permet de choisir l’algorithme le plus adapté au problème traité, tout en tenant compte des contraintes imposées par celui-ci. Les principales caractéristiques qui permettent de différencier les algorithmes de tri, outre leur principe de fonctionnement, sont la complexité temporelle, la complexité spatiale et le caractère stable. (fr) Dalam Ilmu Komputer, Algoritme penyortiran merupakan algoritme yang menempatkan elemen pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerik dan urutan leksikografis. Penyortiran yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritme lain seperti algoritme pencarian dan yang membutuhkan data input di dalam daftar terurut, yang juga sering digunakan untuk menganonikalisasi data dan menghasilkan output yang dapat dibaca manusia. Untuk lebih lanjutnya, output harus melengkapi dua syarat ini: 1. * Output merupakan urutan yang tidak menurut (nondecreasing) (setiap elemen tidak lebih kecil dari elemen sebelumnya menurut dari urutan keseluruhan yang diinginkan. 2. * Output merupakan permutasi (pengurutan kembali) dari inputan yang diberikan. Sejak permulaan komputasi, masalah pengurutan ini telah menarik penelitian yang serius, mungkin dikarenakan kerumitan dari penyelesaian secara efisien disamping mudah, dan dengan statemen yang kita mengerti. Sebagai contoh, pertama sekali ditemukan pada tahun 1956. Walaupun banyak yang memperkirakan masalahnya telah terselesaikan, banyak algoritme penyortiran baru yang masih ditemukan samap sekarang (sebagai contoh, Library Sort yang baru dipublikasikan pertama sekali pada tahun 2006). Algoritme penyortiran sangat umum pada setiap kelas pengenalan bidang Ilmu Komputer, dimana banyaknya algoritme untuk masalah ini menyediakan pengenalan awal mengenai banyaknya konsep algoritme inti, seperti Notasi Big O, Algoritme Pembagi, Struktur Data, Algoritme Acak, Analisis Best, Worst, Average Case, Running Time Calculation, dan Batas Atas dan Bawah. (in) In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output. Formally, the output of any sorting algorithm must satisfy two conditions: 1. * The output is in monotonic order (each element is no smaller/larger than the previous element, according to the required order). 2. * The output is a permutation (a reordering, yet retaining all of the original elements) of the input. For optimum efficiency, the input data should be stored in a data structure which allows random access rather than one that allows only sequential access. (en) Un algoritmo di ordinamento ((EN) sorting algorithm) è un algoritmo che viene utilizzato per posizionare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di quello che lo segue. In assenza di altre specifiche, la relazione d'ordine viene sempre considerata totale (cioè tale da rendere sempre possibile il confronto tra due elementi dell'insieme): le relazioni d'ordine parziale danno origine agli algoritmi di ordinamento topologico. A seconda del verso della relazione considerato, un ordinamento può essere ascendente o discendente. (it) 컴퓨터 과학과 수학에서 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는 데 유용히 쓰인다. 버블 정렬은 1956년에 분석되었다. 수없이 많은 논의를 거쳐왔지만, 쓸만한 새로운 정렬 알고리즘들은 현재도 계속 발명되고 있다(예를 들어, 라이브러리 정렬은 2004년에 발표되었다). 정렬 알고리즘은 다양한 핵심 알고리즘 개념 — 점근 표기법, 분할 정복 알고리즘, 자료 구조, 최악의 경우, 평균적인 경우, 최선의 경우 등 — 을 소개하는 데 적당하기 때문에, 컴퓨터 과학 강의에서 입문 과정으로 유행하고 있다. (ko) Een sorteeralgoritme is een algoritme om elementen van een lijst in een bepaalde volgorde te zetten. In de geschiedenis van het programmeren zijn vele algoritmen voor deze taak bedacht die zich onderscheiden door verschillende snelheid, geheugengebruik en gedrag bij toename van het aantal te sorteren elementen. Het sorteren van bijvoorbeeld een pak speelkaarten stelt andere eisen dan het sorteren van het telefoonboek van New York. Het bestuderen van sorteeralgoritmen is in veel informaticaopleidingen een manier om veel aspecten van het gebruik van computers uit te leggen. Sorteeralgoritmen vinden ook toepassing bij datacompressie en geheugenbeheer. Donald Knuth heeft in zijn klassieke werk The art of computer programming een belangrijk deel aan sorteer- en zoekalgoritmen gewijd. (nl) ソート (英: sort) は、データの集合を一定の規則に従って並べること。日本語では整列（せいれつ）、並べ替え（ならべかえ）、分類（ぶんるい）などと訳される。 主に配列や連結リストのような、リストデータ構造に分類されるコレクション（コンテナ）に格納されている要素データを、全順序関係によって並べ替えることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、英: ascending order）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、英: descending order）という。 対象となるコレクションのデータ構造や必要とされる出力、また時間的コストと空間的コストの兼ね合いによって、ソートに使われるアルゴリズムは異なる。 (ja) Sortowanie – jeden z podstawowych problemów informatyki, polegający na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp. Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwienia stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka. Jeśli jest konieczne posortowanie zbioru większego niż wielkość dostępnej pamięci, stosuje się algorytmy sortowania zewnętrznego. Algorytmy, do działania których nie jest potrzebna większa niż stała pamięć dodatkowa (elementy sortowane przechowywane są przez cały czas w tablicy wejściowej), nazywane są algorytmami działającymi w miejscu. Algorytmy sortujące, które dla elementów o tej samej wartości zachowują w tablicy końcowej kolejność tablicy wejściowej, nazywamy algorytmami stabilnymi. (pl) Sorteringsalgoritm är en algoritm avsedd att sortera data, till exempel för att sortera en lista med namn eller en mängd poster i en databas efter en önskad nyckel. Vanliga tillämpningar för sorteringsalgoritmer är användarvänlig presentation av data och som subrutin för att möjliggöra uppsnabbning eller förenkling av andra algoritmer. (sv) Algoritmo de ordenação em ciência da computação é um algoritmo, de manipulação de dados, que coloca os elementos de uma dada sequência em uma certa ordem -- em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica. Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente. (pt) Алгоритм сортировки — это алгоритм для упорядочивания элементов в массиве. В случае, когда элемент в массиве имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. (ru) 在計算機科學與數學中，一個排序算法（英語：Sorting algorithm）是一種能將一串資料依照特定排序方式排列的算法。最常用到的排序方式是數值順序以及字典順序。有效的排序算法在一些算法（例如搜尋算法與）中是重要的，如此這些算法才能得到正確解答。排序算法也用在處理文字資料以及產生人類可讀的輸出結果。基本上，排序算法的輸出必須遵守下列兩個原則： 1. * 輸出結果為遞增序列（遞增是針對所需的排序順序而言） 2. * 輸出結果是原輸入的一種排列、或是重組 雖然排序算法是一個簡單的問題，但是從計算機科學發展以來，在此問題上已經有大量的研究。舉例而言，泡沫排序在1956年就已經被研究。雖然大部分人認為這是一個已經被解決的問題，有用的新算法仍在不斷的被發明。（例子：圖書館排序在2004年被發表） (zh) Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Python_demo_-_sortvisu.png?width=300 |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20150303022622/http:/www.sorting-algorithms.com/ http://www.softpanorama.org/Algorithms/sorting.shtml http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm https://coderslegacy.com/comparison-of-sorting-algorithms/ https://archive.org/details/computationalpro00actu/page/101 https://oeis.org/A036604 https://www.youtube.com/watch%3Fv=d2d0r1bArUQ https://www.youtube.com/watch%3Fv=kPRA0W1kECg https://www.nist.gov/dads/ |
| dbo:wikiPageID | 28442 (xsd:integer) |
| dbo:wikiPageLength | 64462 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123561184 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Python_(programming_language) dbr:Quicksort dbr:Electoral_system dbr:Ranking_(information_retrieval) dbr:Byte_Magazine dbr:Bead_sort dbr:Betty_Holberton dbr:Binary_heap dbr:Binary_tree dbr:Block_sort dbr:Bogosort dbr:Algorithm dbr:Algorithmic_efficiency dbr:Best,_worst_and_average_case dbr:Patience_sorting dbr:Perl dbr:Permutation dbr:Upper_and_lower_bounds dbr:Decrease-and-conquer dbr:Insertion_sort dbr:Introsort dbr:Inversion_(discrete_mathematics) dbr:Library_sort dbr:.NET dbr:Comb_sort dbr:Median dbr:Elo_rating_system dbr:Gnome_sort dbr:Monotonic dbr:Android_(operating_system) dbr:Call_stack dbr:Smoothsort dbr:Big_omega_notation dbr:Standard_Template_Library dbr:Comparison_sort dbr:Computational_complexity_theory dbr:Computer_science dbr:Embedded_system dbr:Leonardo_number dbr:Pigeonhole_sort dbr:Spaghetti_sort dbr:Stooge_sort dbr:Median_of_medians dbr:Bubble_sort dbr:Burstsort dbr:Adaptive_sort dbc:Sorting_algorithms dbr:Central_Processing_Unit dbr:Time_complexity dbr:Timsort dbr:Total_order dbr:Tree_sort dbr:UNIVAC dbr:Data_set dbr:Data_structure dbr:Distributed_algorithm dbr:Divide-and-conquer_algorithm dbr:Cocktail_sort dbr:Heap_(data_structure) dbr:K-sorted_sequence dbr:Locality_of_reference dbr:Open_problem dbr:Quickselect dbr:JDK7 dbr:Samplesort dbr:Cubesort dbr:Cycle_sort dbr:ENIAC dbr:Flashsort dbr:Pancake_sorting dbr:Partial_sorting dbr:Pairwise_comparison dbr:Relational_database dbr:Heapsort dbr:Java_(programming_language) dbr:Java_version_history dbr:Counting_sort dbr:Hybrid_algorithm dbc:Tournament_systems dbr:Big_O_notation dbr:Bitonic_sorter dbr:Cocktail_shaker_sort dbr:Tournament_sort dbr:Donald_Shell dbc:Data_processing dbr:Sorting_algorithm dbr:Sorting_network dbr:Spreadsort dbr:Group_tournament_ranking_system dbr:In-place_algorithm dbr:Integer_sorting dbr:Merge_algorithm dbr:Merge_sort dbr:Bucket_sort dbr:Canonicalization dbr:Radix_sort dbr:Random-access_machine dbr:Randomized_algorithm dbr:Search_algorithm dbr:Selection_sort dbr:Longest_increasing_subsequence dbr:Most_significant_digit dbr:Selection_algorithm dbr:Shellsort dbr:Sort_(C++) dbr:Sorting dbr:Virtual_memory dbr:In-place_merge_sort dbr:Shuffling_algorithm dbr:External_sorting dbr:Least_significant_digit dbr:Odd–even_sort dbr:Fisher–Yates_shuffle dbr:Self-balancing_binary_search_tree dbr:Insertion_Sort dbr:Lexicographical_order dbr:Random_access dbr:Rank_correlation dbr:Sequential_access dbr:Slowsort dbr:Strand_sort dbr:Unstable_sort dbr:List_(computing) dbr:Floating_point_numbers dbr:Operating_system_kernel dbr:In-place dbr:Ford–Johnson_algorithm dbr:Numerical_order dbr:Postman_sort dbr:Computer_bus dbr:Google_Colab dbr:Memory_(computing) dbr:Time–space_tradeoff dbr:File:Shell_sorting_algorithm_color_bars.svg dbr:Ordered_array dbr:File:Bubblesort-edited-color.svg dbr:File:Python_demo_-_sortvisu.png dbr:File:Sorting_playing_cards_using_stable_sort.svg dbr:File:Sorting_stability_playing_cards.svg |
| dbp:date | 2015-03-03 (xsd:date) June 2021 (en) November 2015 (en) |
| dbp:reason | I thought I heard that Batcher made odd-even merge sort to supersede bitonic. (en) Sorting networks are highly practical; the "specialized hardware" required is a consumer-grade GPU. (en) |
| dbp:title | Sorting Algorithm Animations (en) |
| dbp:url | https://web.archive.org/web/20150303022622/http:/www.sorting-algorithms.com/ |
| dbp:wikiPageUsesTemplate | dbt:Annotated_link dbt:Citation dbt:Commons_category dbt:Disputed_inline dbt:Main dbt:Math dbt:Mvar dbt:N/A dbt:No dbt:Reflist dbt:See_also dbt:Short_description dbt:Snd dbt:Sort dbt:Tmath dbt:Webarchive dbt:Wikibooks dbt:Yes dbt:Varies dbt:Sorting dbt:Algorithmic_paradigms |
| dcterms:subject | dbc:Sorting_algorithms dbc:Data_processing |
| gold:hypernym | dbr:Algorithm |
| rdf:type | owl:Thing dbo:Software |
| rdfs:comment | في المعلوماتية أو الرياضيات، خوارزمية الترتيب هي خوارزمية تمكن من تنظيم مجموعة عناصر حسب ترتيب محدد. العناصر المراد ترتيبها توجد في مجموعة مزودة بعلاقة ترتيب. (ar) En informàtica i matemàtiques un algorisme d'ordenació és un algorisme que posa elements d'una seguint l'ordre donat per una relació d'ordre. Les relacions d'ordre més usades són l'ordre numèric i l'ordre lexicogràfic. Ordenar eficientment és important per a posteriorment usar en forma d'altres algorismes com els de , , (per exemple, per a la comparació de llistes), atès que per a aplicar certs algorismes és necessari que prèviament els elements es trobin ordenats. També és útil per a posar dades en forma canònica i per a generar resultats llegibles per a humans. (ca) Στην επιστήμη των υπολογιστών ο αλγόριθμος ταξινόμησης είναι ένας αλγόριθμος που μεταθέτει τα στοιχεία μίας ακολουθίας έτσι ώστε να έχουν μία συγκεκριμένη σειρά. Παραδείγματα τέτοιων σειρών αποτελούν η και η . Πιο συγκεκριμένα ένας αλγόριθμος ταξινόμησης είναι ένας αλγόριθμος που δοσμένης μίας ακολουθίας εισόδου και μίας συνάρτησης δίαταξης , παράγει μία ακολουθία εξόδου τέτοια ώστε: 1. * 2. * Η ακολουθία αποτελεί μετάθεση της Η συνάρτηση είναι αυτή που καθορίζει τη σειρά ταξινόμησης. Έτσι επιλέγοντας η σειρά ταξινόμησης είναι η φθίνουσα. (el) Un algoritmo di ordinamento ((EN) sorting algorithm) è un algoritmo che viene utilizzato per posizionare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di quello che lo segue. In assenza di altre specifiche, la relazione d'ordine viene sempre considerata totale (cioè tale da rendere sempre possibile il confronto tra due elementi dell'insieme): le relazioni d'ordine parziale danno origine agli algoritmi di ordinamento topologico. A seconda del verso della relazione considerato, un ordinamento può essere ascendente o discendente. (it) 컴퓨터 과학과 수학에서 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는 데 유용히 쓰인다. 버블 정렬은 1956년에 분석되었다. 수없이 많은 논의를 거쳐왔지만, 쓸만한 새로운 정렬 알고리즘들은 현재도 계속 발명되고 있다(예를 들어, 라이브러리 정렬은 2004년에 발표되었다). 정렬 알고리즘은 다양한 핵심 알고리즘 개념 — 점근 표기법, 분할 정복 알고리즘, 자료 구조, 최악의 경우, 평균적인 경우, 최선의 경우 등 — 을 소개하는 데 적당하기 때문에, 컴퓨터 과학 강의에서 입문 과정으로 유행하고 있다. (ko) ソート (英: sort) は、データの集合を一定の規則に従って並べること。日本語では整列（せいれつ）、並べ替え（ならべかえ）、分類（ぶんるい）などと訳される。 主に配列や連結リストのような、リストデータ構造に分類されるコレクション（コンテナ）に格納されている要素データを、全順序関係によって並べ替えることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、英: ascending order）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、英: descending order）という。 対象となるコレクションのデータ構造や必要とされる出力、また時間的コストと空間的コストの兼ね合いによって、ソートに使われるアルゴリズムは異なる。 (ja) Sorteringsalgoritm är en algoritm avsedd att sortera data, till exempel för att sortera en lista med namn eller en mängd poster i en databas efter en önskad nyckel. Vanliga tillämpningar för sorteringsalgoritmer är användarvänlig presentation av data och som subrutin för att möjliggöra uppsnabbning eller förenkling av andra algoritmer. (sv) Algoritmo de ordenação em ciência da computação é um algoritmo, de manipulação de dados, que coloca os elementos de uma dada sequência em uma certa ordem -- em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica. Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente. (pt) Алгоритм сортировки — это алгоритм для упорядочивания элементов в массиве. В случае, когда элемент в массиве имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. (ru) 在計算機科學與數學中，一個排序算法（英語：Sorting algorithm）是一種能將一串資料依照特定排序方式排列的算法。最常用到的排序方式是數值順序以及字典順序。有效的排序算法在一些算法（例如搜尋算法與）中是重要的，如此這些算法才能得到正確解答。排序算法也用在處理文字資料以及產生人類可讀的輸出結果。基本上，排序算法的輸出必須遵守下列兩個原則： 1. * 輸出結果為遞增序列（遞增是針對所需的排序順序而言） 2. * 輸出結果是原輸入的一種排列、或是重組 雖然排序算法是一個簡單的問題，但是從計算機科學發展以來，在此問題上已經有大量的研究。舉例而言，泡沫排序在1956年就已經被研究。雖然大部分人認為這是一個已經被解決的問題，有用的新算法仍在不斷的被發明。（例子：圖書館排序在2004年被發表） (zh) Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів. (uk) Řadicí nebo třídicí algoritmus je algoritmus zajišťující uspořádání dané sady (pole, seznamu, souboru) datových záznamů do požadovaného pořadí. Pro porovnávání se obvykle nepoužívá celý záznam, ale jeho jedna nebo více jeho položek nazývaných klíče. Tyto položky bývají zpravidla numerické, které se řadí podle hodnoty nebo řetězcové, které se řadí abecedně. Řazení je velmi častá úloha, která je také částí mnoha dalších algoritmů; vývoji co možná nejefektivnějších algoritmů řazení se proto věnuje velké úsilí. (cs) Unter einem Sortierverfahren versteht man in der Informatik einen Algorithmus, der dazu dient, ein Tupel (i. Allg. ein Array) zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist („kleiner-gleich“), z. B. die lexikographische Ordnung von Zeichenketten oder die numerische Ordnung von Zahlen. Manuelles Sortieren (etwa von Karteikarten) sowie elektro-mechanische Sortierverfahren (z. B. für Lochkarten) entsprechen meist einem der hier beschriebenen softwarebasierten Sortierverfahren, oder Mischtypen. (de) En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos. (es) Konputazioan eta matematiketan ordenazio algoritmoa zerrenda edo bektore baten elementuak ordena-erlazio batek emandako sekuentzia batean jartzen duen algoritmoa da, hau da, irteeraren emaitza sarrerako permutazio bat edo berrantolaketa izan behar da. Ordena erlazio erabilienak orden numerikoa eta orden lexikografikoa dira .Antolamendu eraginkorrak garrantzitsuak dira azkar exekutatzeko, zerrenda ordenatuak behar dituzten beste algoritmo batzuen (hala nola bilaketa- eta fusio-algoritmoen) erabilera optimizatzeko. Datuak kanonikoki jartzeko eta gizakiek irakurtzeko moduko emaitzak sortzeko ere balio du. (eu) Dalam Ilmu Komputer, Algoritme penyortiran merupakan algoritme yang menempatkan elemen pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerik dan urutan leksikografis. Penyortiran yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritme lain seperti algoritme pencarian dan yang membutuhkan data input di dalam daftar terurut, yang juga sering digunakan untuk menganonikalisasi data dan menghasilkan output yang dapat dibaca manusia. Untuk lebih lanjutnya, output harus melengkapi dua syarat ini: (in) In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output. Formally, the output of any sorting algorithm must satisfy two conditions: (en) Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur. (fr) Sortowanie – jeden z podstawowych problemów informatyki, polegający na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp. Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwienia stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka. Jeśli jest konieczne posortowanie zbioru większego niż wielkość dostępnej pamięci, stosuje się algorytmy sortowania zewnętrznego. (pl) Een sorteeralgoritme is een algoritme om elementen van een lijst in een bepaalde volgorde te zetten. In de geschiedenis van het programmeren zijn vele algoritmen voor deze taak bedacht die zich onderscheiden door verschillende snelheid, geheugengebruik en gedrag bij toename van het aantal te sorteren elementen. Het sorteren van bijvoorbeeld een pak speelkaarten stelt andere eisen dan het sorteren van het telefoonboek van New York. Donald Knuth heeft in zijn klassieke werk The art of computer programming een belangrijk deel aan sorteer- en zoekalgoritmen gewijd. (nl) |
| rdfs:label | خوارزمية ترتيب (ar) Algorisme d'ordenació (ca) Řadicí algoritmus (cs) Sortierverfahren (de) Αλγόριθμος ταξινόμησης (el) Algoritmo de ordenamiento (es) Ordenatze algoritmo (eu) Algoritma penyortiran (in) Algorithme de tri (fr) ソート (ja) Algoritmo di ordinamento (it) 정렬 알고리즘 (ko) Sorteeralgoritme (nl) Algoritmo de ordenação (pt) Sortowanie (pl) Sorting algorithm (en) Алгоритм сортировки (ru) Sorteringsalgoritm (sv) 排序算法 (zh) Алгоритм сортування (uk) |
| rdfs:seeAlso | dbr:External_sorting |
| owl:sameAs | dbpedia-no:Sorting algorithm freebase:Sorting algorithm wikidata:Sorting algorithm dbpedia-ar:Sorting algorithm dbpedia-az:Sorting algorithm dbpedia-bg:Sorting algorithm http://bn.dbpedia.org/resource/সর্টিং_অ্যালগোরিদম dbpedia-ca:Sorting algorithm dbpedia-cs:Sorting algorithm dbpedia-da:Sorting algorithm dbpedia-de:Sorting algorithm dbpedia-el:Sorting algorithm dbpedia-es:Sorting algorithm dbpedia-et:Sorting algorithm dbpedia-eu:Sorting algorithm dbpedia-fa:Sorting algorithm dbpedia-fi:Sorting algorithm dbpedia-fr:Sorting algorithm dbpedia-he:Sorting algorithm http://hi.dbpedia.org/resource/शाटन_की_कलनविधि dbpedia-hu:Sorting algorithm http://hy.dbpedia.org/resource/Տեսակավորման_ալգորիթմ dbpedia-id:Sorting algorithm dbpedia-is:Sorting algorithm dbpedia-it:Sorting algorithm dbpedia-ja:Sorting algorithm dbpedia-kk:Sorting algorithm dbpedia-ko:Sorting algorithm dbpedia-lb:Sorting algorithm dbpedia-lmo:Sorting algorithm http://lt.dbpedia.org/resource/Rikiavimo_algoritmas http://lv.dbpedia.org/resource/Datu_šķirošanas_algoritms dbpedia-nl:Sorting algorithm dbpedia-pl:Sorting algorithm dbpedia-pt:Sorting algorithm dbpedia-ru:Sorting algorithm dbpedia-simple:Sorting algorithm dbpedia-sk:Sorting algorithm dbpedia-sl:Sorting algorithm dbpedia-sr:Sorting algorithm dbpedia-sv:Sorting algorithm dbpedia-sw:Sorting algorithm http://ta.dbpedia.org/resource/வரிசையாக்கப்_படிமுறை dbpedia-th:Sorting algorithm dbpedia-tr:Sorting algorithm dbpedia-uk:Sorting algorithm http://uz.dbpedia.org/resource/Saralash_algoritmi dbpedia-vi:Sorting algorithm dbpedia-zh:Sorting algorithm https://global.dbpedia.org/id/m36B |
| prov:wasDerivedFrom | wikipedia-en:Sorting_algorithm?oldid=1123561184&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Bubblesort-edited-color.svg wiki-commons:Special:FilePath/Python_demo_-_sortvisu.png wiki-commons:Special:FilePath/Shell_sorting_algorithm_color_bars.svg wiki-commons:Special:FilePath/Sorting_playing_cards_using_stable_sort.svg wiki-commons:Special:FilePath/Sorting_stability_playing_cards.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Sorting_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Sort |
| is dbo:wikiPageRedirects of | dbr:Non-comparison_sort dbr:Non-comparison_sorting dbr:List_of_sorting_algorithms dbr:Stable_sort dbr:Sorting_Algorithm dbr:Comparison_of_sorting_algorithms dbr:Distribution_sort dbr:Unsorted_list dbr:Unstable_sort dbr:Sort_(computing) dbr:Sort_algorithm dbr:Sort_algorithms dbr:Sorted_list dbr:Sorting_(computer_science) dbr:Sorting_Algorithms dbr:Sorting_problem dbr:Sorting_algorithms dbr:Stable_sorting dbr:Stable_sorting_algorithm dbr:Exchange_sort dbr:Tag_sort |
| is dbo:wikiPageWikiLink of | dbr:Cache-oblivious_distribution_sort dbr:Program_synthesis dbr:Proportion_extend_sort dbr:Proxmap_sort dbr:Quicksort dbr:List_of_algorithm_general_topics dbr:Visibility_polygon dbr:Non-comparison_sort dbr:Non-comparison_sorting dbr:Bead_sort dbr:Binary_heap dbr:Binary_search_algorithm dbr:Binary_search_tree dbr:Binary_tree dbr:Block_sort dbr:Bogosort dbr:Book_embedding dbr:Algorithm dbr:Algorithmic_efficiency dbr:Algorithmic_technique dbr:Algorithms_+_Data_Structures_=_Programs dbr:Applications_of_randomness dbr:Best,_worst_and_average_case dbr:List_of_Dutch_inventions_and_innovations dbr:List_of_sorting_algorithms dbr:Patience_sorting dbr:Permutation dbr:Vaughan_Pratt dbr:David_Musser dbr:Dutch_national_flag_problem dbr:Incompressibility_method dbr:Insertion_sort dbr:Instruction_path_length dbr:Interface_(Java) dbr:Interpolation_search dbr:Introselect dbr:Introsort dbr:Lexicographic_breadth-first_search dbr:Library_sort dbr:List_of_permutation_topics dbr:Comb_sort dbr:Median dbr:Rectilinear_Steiner_tree dbr:Weighted_matroid dbr:Punched_card_sorter dbr:Quantum_sort dbr:Endianness dbr:Funnelsort dbr:Glossary_of_computer_science dbr:Gnome_sort dbr:Batcher_odd–even_mergesort dbr:Lexicographic_order dbr:MVS dbr:Smoothsort dbr:Stable_sort dbr:Collision_detection dbr:Comparison_sort dbr:Computational_complexity dbr:Árpád_Varecza dbr:Horizons:_Software_Starter_Pack dbr:Parallel_computing dbr:Pigeonhole_sort dbr:Pile_(abstract_data_type) dbr:Priority_queue dbr:Mainframe_sort_merge dbr:Spaghetti_sort dbr:Stooge_sort dbr:String_(computer_science) dbr:Suffix_tree dbr:Medcouple dbr:Median_cut dbr:Standard_library dbr:Stack-sortable_permutation dbr:8-bit_color dbr:Bubble_sort dbr:Burstsort dbr:Adaptive_heap_sort dbr:Adaptive_sort dbr:Time_complexity dbr:Timsort dbr:Tony_Hoare dbr:Tree_(data_structure) dbr:Tree_sort dbr:Two_Daughters dbr:Weak_heap dbr:Widest_path_problem dbr:Divide-and-conquer_algorithm dbr:Heap_(data_structure) dbr:Polyphase_merge_sort dbr:Samplesort dbr:ASCII dbr:Abstract_structure dbr:Cubesort dbr:Cycle_sort dbr:Alphabetical_order dbr:Flashsort dbr:Partial_sorting dbr:Graham_scan dbr:History_of_IBM_mainframe_operating_systems dbr:KOI_character_encodings dbr:Kaprekar's_routine dbr:User_exit dbr:Shmuel_Gal dbr:Relational_operator dbr:Heapsort dbr:Counting_sort dbr:Hybrid_algorithm dbr:Marvin_Stein_(computer_scientist) dbr:Job_Control_Language dbr:Binary_prioritization dbr:Bitonic_sorter dbr:Block_Range_Index dbr:Cocktail_shaker_sort dbr:Collation dbr:Tim_Peters_(software_engineer) dbr:Tournament_sort dbr:Reduction_operator dbr:Stable_algorithm dbr:Donald_Shell dbr:Mark_Davis_(Unicode) dbr:CPU_time dbr:Sorting_Algorithm dbr:Sorting_algorithm dbr:Sorting_network dbr:Spreadsort dbr:In-place_algorithm dbr:Integer_sorting dbr:Merge_algorithm dbr:Merge_sort dbr:Microsoft_Sort dbr:Browser_speed_test dbr:Bucket_sort dbr:Object–relational_impedance_mismatch dbr:Operating_system dbr:Order_statistic dbr:Cartesian_tree dbr:Radix_sort dbr:Selection_sort dbr:Kirkpatrick–Reisch_sort dbr:Sean_M._Burke dbr:Search_engine_indexing dbr:Marzullo's_algorithm dbr:Multiple_instruction,_single_data dbr:Texture_mapping dbr:Qsort dbr:Selection_algorithm dbr:Shellsort dbr:Sort dbr:Sort_(C++) dbr:Sorter dbr:Sorting dbr:Comparison_of_sorting_algorithms dbr:Distribution_sort dbr:IBM_101 dbr:Odd–even_sort dbr:The_Art_of_Computer_Programming dbr:Procedural_parameter dbr:ExOR_(wireless_network_protocol) dbr:First_Draft_of_a_Report_on_the_EDVAC dbr:Multi-key_quicksort dbr:Sorted_array dbr:Painter's_algorithm dbr:Pairwise_sorting_network dbr:Sampling_in_order dbr:Outline_of_computer_programming dbr:Parallel_algorithms_for_minimum_spanning_trees dbr:Spike_sorting dbr:Unit_record_equipment dbr:Super_column dbr:Shuffling dbr:Slowsort dbr:Systolic_array dbr:Random_number_generation dbr:Strand_sort dbr:Unicode_equivalence dbr:X_+_Y_sorting dbr:Unsorted_list dbr:Unstable_sort dbr:Sort_(computing) dbr:Sort_algorithm dbr:Sort_algorithms dbr:Sorted_list dbr:Sorting_(computer_science) dbr:Sorting_Algorithms dbr:Sorting_problem dbr:Sorting_algorithms dbr:Stable_sorting dbr:Stable_sorting_algorithm dbr:Exchange_sort dbr:Tag_sort |
| is dbp:class of | dbr:Proportion_extend_sort dbr:Proxmap_sort dbr:Quicksort dbr:Block_sort dbr:Patience_sorting dbr:Insertion_sort dbr:Introsort dbr:Library_sort dbr:Comb_sort dbr:Gnome_sort dbr:Batcher_odd–even_mergesort dbr:Smoothsort dbr:Pigeonhole_sort dbr:Stooge_sort dbr:Bubble_sort dbr:Burstsort dbr:Timsort dbr:Tree_sort dbr:Cubesort dbr:Cycle_sort dbr:Heapsort dbr:Bitonic_sorter dbr:Cocktail_shaker_sort dbr:Tournament_sort dbr:Merge_sort dbr:Bucket_sort dbr:Radix_sort dbr:Selection_sort dbr:Shellsort dbr:Odd–even_sort dbr:Pairwise_sorting_network |
| is dbp:stability of | dbr:Proportion_extend_sort dbr:Quicksort |
| is rdfs:seeAlso of | dbr:Best,_worst_and_average_case |
| is foaf:primaryTopic of | wikipedia-en:Sorting_algorithm |
