D04.5. Pros and cons of Insertion sort?

[vldnik]

Pros and cons of Insertion sort? Переваги та недоліки Insertion sort?

Pros (advantages) -Fast? Cons (disadvantages) -Not stream out -Move the whole array

Переваги -Найшвидший з простих -Адаптивний -Менше пам’яті -Мало порівнянь -Стабільність Недоліки -Багато записів -Пересування -Повільний

[FairyFox5700]

Переваги майже лінійний для частково відсортованих вхідних масивів; Недоліки погано працює з невідсортованими масивами чи відсортованими в зворотньому порядку;

[Tia333]

"+":

• Основною перевагою типу вставки є її простота.
• Це також показує хорошу продуктивність при роботі з невеликим списком.
• Сортування вставкою є алгоритмом сортування на місці, тому вимоги до простору мінімальні.

"-":

• Недолік сортування вставкою полягає в тому, що вона не працює так само добре, як інші, більш ефективні алгоритми сортування.
• З n-квадратними кроками, необхідними для сортування кожного n елемента, сортування вставкою погано справляється з величезним списком.
• Сортування вставки особливо корисна тільки при сортуванні списку з кількох елементів.

[vkrasiy]

О сортировках (пузырьковой, быстрой, расческой...) https://habr.com/ru/post/357640/

[ghost]

Insertion sort provides several advantages:

Simple implementation.

Efficient for (quite) small data sets.

Adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions.

More efficient in practice than most other simple quadratic, i.e. O(n2) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n).

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.

Disadvantages of insertion sort:

It is less efficient on list containing more number of elements.

As the number of elements increases the performance of the program would be slow.

Insertion sort needs a large number of element shifts.

[PolinaLiashenko]

Легкий в понимании и реализации, самый эффективный, если сравнивать с другими простыми сортировками

Долгий сдвиг массива вправо Эффективнее в отсортированных массивах Неэффективен в случае, если массив отсортирован в порядке, противоположном нужному

[alexivashina]

http://qaru.site/questions/173110/is-there-ever-a-good-reason-to-use-insertion-sort

[WalrusPUNCH]

Insertion sort має низку переваг:

• простота у реалізації
• ефективний (зазвичай) на маленьких масивах
• ефективний при сортуванні масивів, дані в яких вже частково відсортовані.
• на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n^2))
• в найкращому випадку швидкість є лінійною
• є стабільним алгоритмом

Проте, недоліком Insertion sort є те, що він вимагає більше записів, ніж Selection sort. Взагалі, Insertion sort робить O(n^2) записів, тоді як Selection sort зробить лише O(n) операцій запису. З цієї причини Selection sort краще використовувати у тих випадках, коли записування в пам'ять значно дорожче, ніж читання.

[illix-it]

What are the advantages and disadvantages to an insertion sort? Originally it was implemented to merge an input tape into an existing tape where neither of the tapes fit into memory. Yes, I said tape as in large reels of magnetic tape. So it didn't matter that the inserts were going to be slow, it was just not going to happen without this technique.

The advantage is that it is possible to do with very little RAM ant random access streams. The disadvantage is that it is O (n*2) rather than the most efficient O(nlg (n)) for heap sort. It is also order preserving for identical sort elements. This is important if you sort by several different things and want the subsorts to still be in order.

[crowl1]

++ Використовує менше пам'яті ++ Надійний --- Повільний

[AleksAndriushyn]

Advantages: The main advantage of the insertion sort is its simplicity. It also exhibits a good performance when dealing with a small list. The insertion sort is an in-place sorting algorithm so the space requirement is minimal.

Disadvantages: The disadvantage of the insertion sort is that it does not perform as well as other, better sorting algorithms. With n-squared steps required for every n element to be sorted, the insertion sort does not deal well with a huge list. The insertion sort is particularly useful only when sorting a list of few items.

[NikitaViktorov]

++ Використовує менше пам'яті ++ Надійний --- Повільний

[invisy]

Крім вищесказаного:

Переваги:

• зручно застосовувати, коли дані частково (майже) відсортовані

Недоліки:

• занадто повільний при невідсортованих даних
• кількість записів в пам'ять ще більша ніж у Selection Sort
• неконстантний час

[galaxyair]

Основным преимуществом типа вставки является ее простота. Это также показывает хорошую производительность при работе с небольшим списком. Сортировка вставкой является алгоритмом сортировки на месте, поэтому требования к пространству минимальны. Недостаток сортировки вставкой заключается в том, что она не работает так же хорошо, как другие, более эффективные алгоритмы сортировки. С n-квадратными шагами, необходимыми для сортировки каждого n элемента, сортировка вставкой плохо справляется с огромным списком. Поэтому сортировка вставкой особенно полезна только при сортировке списка из нескольких элементов.

[BogdanDudnik]

Pros: ease of implementation effective (usually) on small arrays effective in sorting arrays, the data in which is already partially sorted. in practice, more efficient than most other quadratic algorithms (O (n ^ 2)) at best, the speed is linear is a stable algorithm

minus

However, the Insertion sort's disadvantage is that it requires more entries than Selection sort. In general, Insertion sort makes O (n ^ 2) records, whereas Selection sort will only record O (n) operations. For this reason, the Selection sort is best used in cases where recording in memory is much more expensive than reading.