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