Естественная сортировка слиянием с минимизацией объема дополнительной памяти
Предложен алгоритм, требующий объема дополнительной памяти O (logn), с трудоемкостью в худшем случае O (nlog2 n). Предложены также алгоритмы устойчивой нерекурсивной сортировки слиянием, позволяющие учитывать естественную упорядоченность исходного массива данных длиной n при уменьшении объема дополн...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2011 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/61791 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Естественная сортировка слиянием с минимизацией объема дополнительной памяти / С.Д. Винничук // Электронное моделирование. — 2011 — Т. 33, № 6. — С. 33-56. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862713830888439808 |
|---|---|
| author | Винничук, С.Д. |
| author_facet | Винничук, С.Д. |
| citation_txt | Естественная сортировка слиянием с минимизацией объема дополнительной памяти / С.Д. Винничук // Электронное моделирование. — 2011 — Т. 33, № 6. — С. 33-56. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Предложен алгоритм, требующий объема дополнительной памяти O (logn), с трудоемкостью в худшем случае O (nlog2 n). Предложены также алгоритмы устойчивой нерекурсивной сортировки слиянием, позволяющие учитывать естественную упорядоченность исходного массива данных длиной n при уменьшении объема дополнительной памяти до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) и трудоемкости в случае наихудшего расположения элементов порядка O (nlogn).
Запропоновано алгоритм, що потребує обсягу додаткової пам’яті O (logn), з трудомісткістю для гіршого випадку O (nlog2 n). Запропоновано також стійкі нерекурсивні алгоритми сортування злиттям, які дозволяють враховувати природню впорядкованість початкового масиву даних довжиною n при зменшенні обсягу додаткової пам’яті до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) з трудомісткістю для гіршого випадку O (nlogn).
An algorithm has been proposed, which requires additional memory of the order O (logn) with an estimate of the labour input in the worst case of order O (nlog2n). Variants of resistant nonrecursive merge sorting algorithms have been proposed that take into account the natural ordering of the original data array of length n, with a decrease in the volume of additional memory to the values of n/2 + O (1), n/4 + O (1), n/8 + O (1), and labour input in the worst case of elements location of the order O (nlogn).
|
| first_indexed | 2025-12-07T17:46:30Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-61791 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T17:46:30Z |
| publishDate | 2011 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Винничук, С.Д. 2014-05-11T15:06:25Z 2014-05-11T15:06:25Z 2011 Естественная сортировка слиянием с минимизацией объема дополнительной памяти / С.Д. Винничук // Электронное моделирование. — 2011 — Т. 33, № 6. — С. 33-56. — Бібліогр.: 3 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/61791 004.424.5 : 519.683.6 Предложен алгоритм, требующий объема дополнительной памяти O (logn), с трудоемкостью в худшем случае O (nlog2 n). Предложены также алгоритмы устойчивой нерекурсивной сортировки слиянием, позволяющие учитывать естественную упорядоченность исходного массива данных длиной n при уменьшении объема дополнительной памяти до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) и трудоемкости в случае наихудшего расположения элементов порядка O (nlogn). Запропоновано алгоритм, що потребує обсягу додаткової пам’яті O (logn), з трудомісткістю для гіршого випадку O (nlog2 n). Запропоновано також стійкі нерекурсивні алгоритми сортування злиттям, які дозволяють враховувати природню впорядкованість початкового масиву даних довжиною n при зменшенні обсягу додаткової пам’яті до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) з трудомісткістю для гіршого випадку O (nlogn). An algorithm has been proposed, which requires additional memory of the order O (logn) with an estimate of the labour input in the worst case of order O (nlog2n). Variants of resistant nonrecursive merge sorting algorithms have been proposed that take into account the natural ordering of the original data array of length n, with a decrease in the volume of additional memory to the values of n/2 + O (1), n/4 + O (1), n/8 + O (1), and labour input in the worst case of elements location of the order O (nlogn). ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Вычислительные процессы и системы Естественная сортировка слиянием с минимизацией объема дополнительной памяти Article published earlier |
| spellingShingle | Естественная сортировка слиянием с минимизацией объема дополнительной памяти Винничук, С.Д. Вычислительные процессы и системы |
| title | Естественная сортировка слиянием с минимизацией объема дополнительной памяти |
| title_full | Естественная сортировка слиянием с минимизацией объема дополнительной памяти |
| title_fullStr | Естественная сортировка слиянием с минимизацией объема дополнительной памяти |
| title_full_unstemmed | Естественная сортировка слиянием с минимизацией объема дополнительной памяти |
| title_short | Естественная сортировка слиянием с минимизацией объема дополнительной памяти |
| title_sort | естественная сортировка слиянием с минимизацией объема дополнительной памяти |
| topic | Вычислительные процессы и системы |
| topic_facet | Вычислительные процессы и системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/61791 |
| work_keys_str_mv | AT vinničuksd estestvennaâsortirovkasliâniemsminimizacieiobʺemadopolnitelʹnoipamâti |