Insertion sort (original) (raw)
Řazení vkládáním, známý jako insertion sort, je jednoduchý řadicí algoritmus založený na porovnávání. Algoritmus řazení vkládáním pracuje tak, že prochází prvky postupně a každý další nesetříděný prvek zařadí na správné místo do již setříděné posloupnosti. Je to jeden z nejrychlejších algoritmů s kvadratickou časovou složitostí. Je asymptoticky pomalejší než pokročilé algoritmy jako třeba rychlé řazení nebo řazení slučováním, ale má jiné výhody.
| Property | Value |
|---|---|
| dbo:abstract | الترتيب بالإدراج (بالإنجليزية: Insertion Sort) هي خوارزمية ترتيب بسيطة مبدأها مشابه لما يستعملهُ أغلب الناس عند ترتيب أوراقهم أو ملفاتهم. وتعمل الخوارزمية بالمرور على البيانات وإدراج كل مدخل في مكانه أولا بأول، ولا تعدّ هذه الطريقة الأفضل بالنسبة للقوائم الكبيرة حيث من يُفضل استخدام خوارزميات متطورة أكثر مثل الترتيب السريع أو الترتيب الدمجي، ولكن للترتيب بالإدراج عدة نقاط إيجابية: * خوارزمية بسيطة: قام عالم الحاسوب جون بنتلي بتطبيق الخوارزمية في ثلاثة سطور بلغة سي ونسخة محسنة في 5 سطور. * أكثر كفاءة للمصفوفات الصغيرة جداً كغيرها من الخوارزمات الرباعية. * كفاءة أعلى عند التطبيق من أغلب خوارزمات الترتيب التربيعية البسيطة مثل أو . * متأقلمة الأداء: إذ تتحسن كفاءتها كلما كانت المصفوفة مرتبة أكثر، وينخفض التعقيد الزمني للترتيب إلى O(nk) في مصفوفة لا يبعد أي مدخل أكثر من k خانة عن مكانها المرتب. * الثبات: لا يغير الترتيب النسبي للمدخلات ذات مفاتيح متساوية. * في المكان: يحتاج فقط إلى O(1) ذاكرة اضافية. * فورية: أي أنها تستطيع ترتيب المعلومات أثناء تلقيها بدل الانتظار حتى تلقي المصفوفة الكاملة. وبرمجياً، تتطلب الخوارزمية عدد مقارنات من الرتبة ، ومعدل تبديلات من الرتبة ، وتعقيد زمني برتبة . (ar) Řazení vkládáním, známý jako insertion sort, je jednoduchý řadicí algoritmus založený na porovnávání. Algoritmus řazení vkládáním pracuje tak, že prochází prvky postupně a každý další nesetříděný prvek zařadí na správné místo do již setříděné posloupnosti. Je to jeden z nejrychlejších algoritmů s kvadratickou časovou složitostí. Je asymptoticky pomalejší než pokročilé algoritmy jako třeba rychlé řazení nebo řazení slučováním, ale má jiné výhody. (cs) Η ταξινόμηση με εισαγωγή είναι ένας απλός αλγόριθμος ταξινόμησης που δημιουργεί τον τελικό ταξινομημένο πίνακα (ή λίστα) αλλάζοντας ένα στοιχείο κάθε φορά. Είναι λιγότερο αποτελεσματική σε μεγάλες λίστες σε αντίθεση με άλλους αλγορίθμους όπως είναι η γρήγορη ταξινόμηση (quicksort), η (heapsort), ή η ταξινόμηση με συγχώνευση (merge sort). Ωστόσο, η ταξινόμηση με εισαγωγή παρέχει πολλά πλεονεκτήματα: * Είναι απλή στην εφαρμογή της. * Αποτελεσματική για (πολύ) μικρά σύνολα δεδομένων. * Αποδοτική για σύνολα δεδομένων που είναι ήδη ταξινομημένα με χρονική πολυπλοκότητα O(n + d), όπου d είναι ο αριθμός των αναστροφών. * Πιο αποτελεσματική στην πράξη από άλλους απλούς τετραγωνικούς (όπως, O(n2)) αλγορίθμους όπως είναι η ταξινόμηση με επιλογή (selection sort) ή η ταξινόμηση φυσαλίδας (bubble sort), όπου στην καλύτερη περίπτωση (σχεδόν ταξινομημένα τα στοιχεία κατά την είσοδο) ο χρόνος εκτέλεσης είναι Ο(n). * Ευσταθής, δηλαδή, δεν αλλάζει τη σχετική σειρά των στοιχείων που έχουν ίσα κλειδιά. * Σε χώρο, καθώς απαιτεί μόνο σταθερό μέγεθος, δηλαδή Ο(1), επιπλέον μνήμης. * Σε απευθείας σύνδεση, καθώς μπορεί να ταξινομήσει μια λίστα καθώς τη λαμβάνει. Όταν οι άνθρωποι ταξινομούν κάτι με μη αυτόματο τρόπο (χειροκίνητα), όπως είναι, για παράδειγμα, μία τράπουλα, οι περισσότεροι χρησιμοποιούν μία μέθοδο παρόμοια με αυτή της ταξινόμησης με εισαγωγή. (el) Insertionsort (auch Einfügesortierenmethode oder Sortieren durch Einfügen, englisch insertion ‚Einfügung‘ und englisch sort ‚sortieren‘) ist ein einfaches stabiles Sortierverfahren (d. h. die Reihenfolge von Elementen mit gleichem Schlüsselwert bleibt unverändert). Es ist leicht zu implementieren, effizient bei kleinen oder bereits teilweise sortierten Eingabemengen. Außerdem benötigt Insertionsort keinen zusätzlichen Speicherplatz, da der Algorithmus in-place arbeitet. Ein weiterer Vorteil besteht darin, dass Insertionsort als Online-Algorithmus eingesetzt werden kann. Der Insertionsort entnimmt der unsortierten Eingabefolge ein beliebiges Element und fügt es an richtiger Stelle in die (anfangs leere) Ausgabefolge ein. Geht man hierbei in der Reihenfolge der ursprünglichen Folge vor, so ist das Verfahren stabil. Wird auf einem Array gearbeitet, so müssen die Elemente hinter dem neu eingefügten Element verschoben werden. Dies ist die eigentlich aufwendige Operation des Insertionsorts. Das Auffinden der richtigen Einfügeposition kann über eine binäre Suche vergleichsweise effizient erfolgen. Grundsätzlich gilt aber, dass Insertionsort weit weniger effizient arbeitet als andere anspruchsvollere Sortierverfahren. (de) Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: * Simple implementation: Jon Bentley shows a three-line C/C++ version that is five lines when optimized. * Efficient for (quite) small data sets, much like other quadratic (i.e., O(n2)) sorting algorithms * More efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort * Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position * Stable; i.e., does not change the relative order of elements with equal keys * In-place; i.e., only requires a constant amount O(1) of additional memory space * Online; i.e., can sort a list as it receives it When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort. (en) El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere operaciones para ordenar una lista de elementos. Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay elementos ordenados de menor a mayor, se toma el elemento y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento debiendo desplazarse los demás elementos. (es) En informatique, le tri par insertion est un algorithme de tri classique. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer. En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide (ou quicksort) et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique. Le tri par insertion est cependant considéré comme l'algorithme le plus efficace sur des entrées de petite taille. Il est aussi efficace lorsque les données sont déjà presque triées. Pour ces raisons, il est utilisé en pratique en combinaison avec d'autres méthodes comme le tri rapide. En programmation informatique, on applique le plus souvent ce tri à des tableaux. La description et l'étude de l'algorithme qui suivent se restreignent à cette version, tandis que l'adaptation à des listes est considérée plus loin. (fr) L'Insertion sort, in italiano ordinamento a inserimento, è un algoritmo relativamente semplice per ordinare un array. Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. Esso è un algoritmo in place, cioè ordina l'array senza doverne creare una copia, risparmiando memoria. Pur essendo molto meno efficiente di algoritmi più avanzati, può avere alcuni vantaggi: ad esempio, è semplice da implementare ed è efficiente per insiemi di partenza che sono quasi ordinati. (it) 挿入ソート（そうにゅうソート、英: insertion sort）あるいは基本挿入法は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。 時間計算量は平均・最悪ケースでともに Ο(n2) であり、クイックソートやマージソートなどと比べれば遅い。しかし、 * アルゴリズムが単純で実装が容易 * 小さな配列に対しては高速 * 安定 * in-placeアルゴリズム * オンラインアルゴリズム などの特徴から利用されることがある。 挿入ソートを高速化したソート法として、シェルソートが知られている。 (ja) 삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다. 각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다. 그러므로 다음과 같은 결과가 된다. 배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다. 선택 정렬이나 거품 정렬과 같은 O(n2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다. (ko) Insertion sort is een sorteeralgoritme. (nl) Sortowanie przez wstawianie (ang. Insert Sort, Insertion Sort) – jeden z najprostszych algorytmów sortowania, którego zasada działania odzwierciedla sposób w jaki ludzie ustawiają karty – kolejne elementy wejściowe są ustawiane na odpowiednie miejsca docelowe. Jest efektywny dla niewielkiej liczby elementów, jego złożoność wynosi O(n2). Pomimo tego, że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort, posiada pewne zalety: * liczba wykonanych porównań jest zależna od liczby inwersji w permutacji, dlatego algorytm jest wydajny dla danych wstępnie posortowanych, * jest wydajny dla zbiorów o niewielkiej liczebności, * jest stabilny. Istnieje modyfikacja algorytmu, pozwalająca zmniejszyć liczbę porównań. Zamiast za każdym razem iterować po już posortowanym fragmencie (etap wstawiania elementu), można posłużyć się wyszukiwaniem binarnym. Pozwala to zmniejszyć liczbę porównań do O(nlogn), nie zmienia się jednak złożoność algorytmu, ponieważ liczba przesunięć elementów to nadal O(n2). (pl) Insertion Sort, ou ordenação por inserção, é um algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação. Podemos fazer uma comparação do Insertion Sort com o modo como algumas pessoas organizam um baralho num jogo de cartas. Imagine que você está jogando ás cartas. Você está com as cartas na mão e elas estão ordenadas. Você recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma a que as cartas obedeçam à ordenação. A cada nova carta adicionada à sua mão de cartas, a nova carta pode ser menor que algumas das cartas que você já tem na mão ou maior, e assim, você começa a comparar a nova carta com todas as cartas na sua mão até encontrar sua posição correta. Você insere a nova carta na posição correta, e, novamente, a sua mão é composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo procedimento. Então outra carta, e outra, e assim em diante, até não receber mais cartas. Esta é a ideia por trás da ordenação por inserção. Percorra as posições do array, começando com o índice 1 (um). Cada nova posição é como a nova carta que você recebeu, e você precisa inseri-la no lugar correto no subarray ordenado à esquerda daquela posição. (pt) Insättningssortering, eller instickssortering, är en av de enklare sorteringsalgoritmer som finns tillgängliga inom datalogi. I praktiken använder man ofta snabbare sorteringsalgoritmer, men om listan redan är delvis sorterad kan den dock vara effektiv. Komplexiteten för insättningssortering är i allmänhet , där n är antalet element, om listan redan är någorlunda sorterad från början är dock insättningssortering en av de snabbare algoritmerna. (sv) Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов. Вычислительная сложность — . (ru) 插入排序（英語：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 (zh) Сортування включенням або сортування вставлянням — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг: * простота у реалізації * ефективний (зазвичай) на маленьких масивах * ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій * на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною * є стабільним алгоритмом Наприклад, більшість людей при сортуванні колоди гральних карт, використовують метод, схожий на алгоритм сортування включенням. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Insertion_sort.gif?width=300 |
| dbo:wikiPageExternalLink | http://www.pathcom.com/~vadco/binary.html https://literateprograms.org/insertion_sort__c_.html http://corewar.co.uk/assembly/insertion.htm https://web.archive.org/web/20150308232109/http:/www.sorting-algorithms.com/insertion-sort |
| dbo:wikiPageID | 15205 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-no:Sorteringsalgoritme |
| dbo:wikiPageLength | 22527 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121840955 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Program_optimization dbr:Quicksort dbr:Binary_search_algorithm dbr:Binary_tree dbr:Binary_tree_sort dbr:Jon_Bentley_(computer_scientist) dbc:Online_sorts dbr:United_Kingdom dbr:Invariant_(computer_science) dbr:Library_sort dbr:Short-circuit_evaluation dbr:Contract_bridge dbr:Online_algorithm dbr:Bounds_checking dbr:Martin_Farach-Colton dbr:Stable_sort dbr:Comparison_sort dbr:Zero-based_numbering dbc:Articles_with_example_pseudocode dbr:Bubble_sort dbr:C++_(programming_language) dbr:C_(programming_language) dbr:Adaptive_sort dbc:Comparison_sorts dbc:Sorting_algorithms dbr:Time_complexity dbr:Data_structure dbr:Divide-and-conquer_algorithm dbr:Heap_(data_structure) dbr:Linked_list dbr:EEPROM dbr:Flash_memory dbr:Iteration dbr:Heapsort dbr:Array_data_structure dbr:Big_O_notation dbc:Stable_sorts dbr:Donald_Shell dbr:Sorting_algorithm dbr:In-place_algorithm dbr:Merge_sort dbr:Mergesort dbr:Selection_sort dbr:Shellsort dbr:The_Art_of_Computer_Programming dbr:Pseudocode dbr:Sorted_array dbr:Skip_list dbr:Heap_sort dbr:File:Insertion-sort-example-300px.gif dbr:File:Insertion_sort.gif dbr:File:Insertionsort-after.png dbr:File:Insertionsort-before.png |
| dbp:averageTime | comparisons and swaps (en) |
| dbp:bestTime | comparisons, swaps (en) |
| dbp:caption | Animation of insertion sort (en) |
| dbp:class | dbr:Sorting_algorithm |
| dbp:data | dbr:Array_data_structure |
| dbp:date | 2015-03-08 (xsd:date) |
| dbp:optimal | No (en) |
| dbp:space | total, auxiliary (en) |
| dbp:time | comparisons and swaps (en) |
| dbp:title | Animated Sorting Algorithms: Insertion Sort (en) |
| dbp:url | https://web.archive.org/web/20150308232109/http:/www.sorting-algorithms.com/insertion-sort |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Code dbt:Commons_category dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Webarchive dbt:Wikibooks dbt:Infobox_Algorithm dbt:Sorting |
| dct:subject | dbc:Online_sorts dbc:Articles_with_example_pseudocode dbc:Comparison_sorts dbc:Sorting_algorithms dbc:Stable_sorts |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatComparisonSorts yago:WikicatOnlineSorts yago:WikicatSortingAlgorithms yago:WikicatStableSorts 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:WikicatAdaptiveSorts yago:WikicatAlgorithms |
| rdfs:comment | Řazení vkládáním, známý jako insertion sort, je jednoduchý řadicí algoritmus založený na porovnávání. Algoritmus řazení vkládáním pracuje tak, že prochází prvky postupně a každý další nesetříděný prvek zařadí na správné místo do již setříděné posloupnosti. Je to jeden z nejrychlejších algoritmů s kvadratickou časovou složitostí. Je asymptoticky pomalejší než pokročilé algoritmy jako třeba rychlé řazení nebo řazení slučováním, ale má jiné výhody. (cs) L'Insertion sort, in italiano ordinamento a inserimento, è un algoritmo relativamente semplice per ordinare un array. Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. Esso è un algoritmo in place, cioè ordina l'array senza doverne creare una copia, risparmiando memoria. Pur essendo molto meno efficiente di algoritmi più avanzati, può avere alcuni vantaggi: ad esempio, è semplice da implementare ed è efficiente per insiemi di partenza che sono quasi ordinati. (it) 挿入ソート（そうにゅうソート、英: insertion sort）あるいは基本挿入法は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。 時間計算量は平均・最悪ケースでともに Ο(n2) であり、クイックソートやマージソートなどと比べれば遅い。しかし、 * アルゴリズムが単純で実装が容易 * 小さな配列に対しては高速 * 安定 * in-placeアルゴリズム * オンラインアルゴリズム などの特徴から利用されることがある。 挿入ソートを高速化したソート法として、シェルソートが知られている。 (ja) 삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다. 각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다. 그러므로 다음과 같은 결과가 된다. 배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다. 선택 정렬이나 거품 정렬과 같은 O(n2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다. (ko) Insertion sort is een sorteeralgoritme. (nl) Insättningssortering, eller instickssortering, är en av de enklare sorteringsalgoritmer som finns tillgängliga inom datalogi. I praktiken använder man ofta snabbare sorteringsalgoritmer, men om listan redan är delvis sorterad kan den dock vara effektiv. Komplexiteten för insättningssortering är i allmänhet , där n är antalet element, om listan redan är någorlunda sorterad från början är dock insättningssortering en av de snabbare algoritmerna. (sv) Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов. Вычислительная сложность — . (ru) 插入排序（英語：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 (zh) الترتيب بالإدراج (بالإنجليزية: Insertion Sort) هي خوارزمية ترتيب بسيطة مبدأها مشابه لما يستعملهُ أغلب الناس عند ترتيب أوراقهم أو ملفاتهم. وتعمل الخوارزمية بالمرور على البيانات وإدراج كل مدخل في مكانه أولا بأول، ولا تعدّ هذه الطريقة الأفضل بالنسبة للقوائم الكبيرة حيث من يُفضل استخدام خوارزميات متطورة أكثر مثل الترتيب السريع أو الترتيب الدمجي، ولكن للترتيب بالإدراج عدة نقاط إيجابية: وبرمجياً، تتطلب الخوارزمية عدد مقارنات من الرتبة ، ومعدل تبديلات من الرتبة ، وتعقيد زمني برتبة . (ar) Insertionsort (auch Einfügesortierenmethode oder Sortieren durch Einfügen, englisch insertion ‚Einfügung‘ und englisch sort ‚sortieren‘) ist ein einfaches stabiles Sortierverfahren (d. h. die Reihenfolge von Elementen mit gleichem Schlüsselwert bleibt unverändert). Es ist leicht zu implementieren, effizient bei kleinen oder bereits teilweise sortierten Eingabemengen. Außerdem benötigt Insertionsort keinen zusätzlichen Speicherplatz, da der Algorithmus in-place arbeitet. Ein weiterer Vorteil besteht darin, dass Insertionsort als Online-Algorithmus eingesetzt werden kann. (de) Η ταξινόμηση με εισαγωγή είναι ένας απλός αλγόριθμος ταξινόμησης που δημιουργεί τον τελικό ταξινομημένο πίνακα (ή λίστα) αλλάζοντας ένα στοιχείο κάθε φορά. Είναι λιγότερο αποτελεσματική σε μεγάλες λίστες σε αντίθεση με άλλους αλγορίθμους όπως είναι η γρήγορη ταξινόμηση (quicksort), η (heapsort), ή η ταξινόμηση με συγχώνευση (merge sort). Ωστόσο, η ταξινόμηση με εισαγωγή παρέχει πολλά πλεονεκτήματα: (el) Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort. (en) En informatique, le tri par insertion est un algorithme de tri classique. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer. En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide (ou quicksort) et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique. (fr) El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere operaciones para ordenar una lista de elementos. (es) Sortowanie przez wstawianie (ang. Insert Sort, Insertion Sort) – jeden z najprostszych algorytmów sortowania, którego zasada działania odzwierciedla sposób w jaki ludzie ustawiają karty – kolejne elementy wejściowe są ustawiane na odpowiednie miejsca docelowe. Jest efektywny dla niewielkiej liczby elementów, jego złożoność wynosi O(n2). Pomimo tego, że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort, posiada pewne zalety: (pl) Insertion Sort, ou ordenação por inserção, é um algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação. (pt) Сортування включенням або сортування вставлянням — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг: Наприклад, більшість людей при сортуванні колоди гральних карт, використовують метод, схожий на алгоритм сортування включенням. (uk) |
| rdfs:label | ترتيب بالإدراج (ar) Řazení vkládáním (cs) Insertionsort (de) Ταξινόμηση με εισαγωγή (el) Ordenamiento por inserción (es) Tri par insertion (fr) Insertion sort (en) Insertion sort (it) 挿入ソート (ja) 삽입 정렬 (ko) Sortowanie przez wstawianie (pl) Insertion sort (nl) Insertion sort (pt) Сортировка вставками (ru) Insättningssortering (sv) Сортування включенням (uk) 插入排序 (zh) |
| owl:sameAs | freebase:Insertion sort yago-res:Insertion sort wikidata:Insertion sort dbpedia-ar:Insertion sort dbpedia-az:Insertion sort dbpedia-bg:Insertion sort http://bn.dbpedia.org/resource/সন্নিবেশ_বাছাই dbpedia-cs:Insertion sort dbpedia-da:Insertion sort dbpedia-de:Insertion sort dbpedia-el:Insertion sort dbpedia-es:Insertion sort dbpedia-et:Insertion sort dbpedia-fa:Insertion sort dbpedia-fi:Insertion sort dbpedia-fr:Insertion sort dbpedia-he:Insertion sort dbpedia-hu:Insertion sort http://hy.dbpedia.org/resource/Ներդրմամբ_տեսակավորում dbpedia-is:Insertion sort dbpedia-it:Insertion sort dbpedia-ja:Insertion sort dbpedia-ka:Insertion sort dbpedia-ko:Insertion sort dbpedia-lmo:Insertion sort http://lt.dbpedia.org/resource/Įterpimo_rikiavimo_algoritmas http://ml.dbpedia.org/resource/ഇൻസർഷൻ_സോർട്ട് dbpedia-nl:Insertion sort dbpedia-no:Insertion sort dbpedia-pl:Insertion sort dbpedia-pt:Insertion sort dbpedia-ru:Insertion sort dbpedia-simple:Insertion sort dbpedia-sk:Insertion sort dbpedia-sl:Insertion sort dbpedia-sr:Insertion sort dbpedia-sv:Insertion sort dbpedia-th:Insertion sort dbpedia-tr:Insertion sort dbpedia-uk:Insertion sort dbpedia-vi:Insertion sort dbpedia-zh:Insertion sort https://global.dbpedia.org/id/E2NJ |
| prov:wasDerivedFrom | wikipedia-en:Insertion_sort?oldid=1121840955&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Insertion-sort-example-300px.gif wiki-commons:Special:FilePath/Insertion_sort.gif wiki-commons:Special:FilePath/Insertionsort-after.png wiki-commons:Special:FilePath/Insertionsort-before.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Insertion_sort |
| is dbo:wikiPageDisambiguates of | dbr:Insertion |
| is dbo:wikiPageRedirects of | dbr:Insertion_Sort dbr:Linear_insertion_sort dbr:List_insertion dbr:Insert_sort dbr:Insertionsort dbr:Insertsort dbr:Binary_insertion_sort |
| is dbo:wikiPageWikiLink of | dbr:Proportion_extend_sort dbr:Proxmap_sort dbr:Quicksort dbr:List_of_algorithms dbr:Merge-insertion_sort dbr:Block_sort dbr:Algorithmic_efficiency dbr:Best,_worst_and_average_case dbr:Permutation dbr:Input_enhancement_(computer_science) dbr:Introsort dbr:Library_sort dbr:Insertion dbr:Worst-case_complexity dbr:Comb_sort dbr:Analysis_of_algorithms dbr:Online_algorithm dbr:Quadratic_growth dbr:Glossary_of_computer_science dbr:Gnome_sort dbr:Comment_(computer_programming) dbr:Comparison_sort dbr:Priority_queue dbr:Median_of_medians dbr:Bubble_sort dbr:Time_complexity dbr:Timsort dbr:Divide-and-conquer_algorithm dbr:Layered_permutation dbr:Flashsort dbr:Big_O_notation dbr:Sorting_algorithm dbr:Sorting_network dbr:In-place_algorithm dbr:Merge_sort dbr:Bucket_sort dbr:Radix_sort dbr:Recursion_(computer_science) dbr:Selection_sort dbr:Shellsort dbr:Sort_(C++) dbr:Sorting dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Sweep_and_prune dbr:Procedural_parameter dbr:First-class_function dbr:Multi-key_quicksort dbr:Sorted_array dbr:Sorting_number dbr:Insertion_Sort dbr:Soft_heap dbr:Splaysort dbr:Linear_insertion_sort dbr:List_insertion dbr:Insert_sort dbr:Insertionsort dbr:Insertsort dbr:Binary_insertion_sort |
| is foaf:primaryTopic of | wikipedia-en:Insertion_sort |
