Internal sort (original) (raw)
An internal sort is any data sorting process that takes place entirely within the main memory of a computer. This is possible whenever the data to be sorted is small enough to all be held in the main memory. like a hard-disk. Any reading or writing of data to and from this slower media can slow the sortation process considerably. This issue has implications for different sort algorithms. Some common internal sorting algorithms include: 1. * Bubble Sort 2. * Insertion Sort 3. * Quick Sort 4. * Heap Sort 5. * Radix Sort 6. * Selection sort
| Property | Value |
|---|---|
| dbo:abstract | An internal sort is any data sorting process that takes place entirely within the main memory of a computer. This is possible whenever the data to be sorted is small enough to all be held in the main memory. like a hard-disk. Any reading or writing of data to and from this slower media can slow the sortation process considerably. This issue has implications for different sort algorithms. Some common internal sorting algorithms include: 1. * Bubble Sort 2. * Insertion Sort 3. * Quick Sort 4. * Heap Sort 5. * Radix Sort 6. * Selection sort Consider a Bubblesort, where adjacent records are swapped in order to get them into the right order, so that records appear to “bubble” up and down through the dataspace. If this has to be done in chunks, then when we have sorted all the records in chunk 1, we move on to chunk 2, but we find that some of the records in chunk 1 need to “bubble through” chunk 2, and vice versa (i.e., there are records in chunk 2 that belong in chunk 1, and records in chunk 1 that belong in chunk 2 or later chunks). This will cause the chunks to be read and written back to disk many times as records cross over the boundaries between them, resulting in a considerable degradation of performance. If the data can all be held in memory as one large chunk, then this performance hit is avoided. On the other hand, some algorithms handle external sorting rather better. A Merge sort breaks the data up into chunks, sorts the chunks by some other algorithm (maybe bubblesort or Quick sort) and then recombines the chunks two by two so that each recombined chunk is in order. This approach minimises the number or reads and writes of data-chunks from disk, and is a popular external sort method. (en) Внутренняя сортировка (англ. internal sort) — разновидность алгоритмов сортировки или их реализаций, при которой объема оперативной памяти достаточно для помещения в неё сортируемого массива данных с произвольным доступом к любой ячейке и, собственно, для выполнения алгоритма. В этом случае сортировка происходит максимально быстро, так как скорость доступа к оперативной памяти значительно выше, чем к периферийным устройствам (соответственно, время доступа значительно меньше). В зависимости от конкретного алгоритма и его реализации данные могут сортироваться в той же области памяти, либо использовать дополнительную оперативную память. Внутренняя сортировка является базовой для любого алгоритма внешней сортировки — отдельные части массива данных сортируются в оперативной памяти и с помощью специального алгоритма сцепляются в один массив, упорядоченный по ключу. В современных архитектурах компьютеров и системных архитектурах широко применяется подкачка и кэширование памяти. Поэтому в большинстве случаев имеется возможность использовать внутреннюю сортировку даже для задач, в которых объём данных несколько превышает выделяемую процессу оперативную память. Однако, в последнем случае алгоритм сортировки должен хорошо сочетаться с применяемыми операционной системой алгоритмами кэширования и подкачки. В противном случае необходимо использовать подходящий алгоритм внешней сортировки. (ru) |
| dbo:wikiPageID | 6497752 (xsd:integer) |
| dbo:wikiPageLength | 1987 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 922203166 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quick_sort dbr:Bubble_Sort dbr:Bubblesort dbc:Sorting_algorithms dbr:Merge_sort dbr:Selection_sort dbr:External_sorting dbr:Insertion_Sort dbr:Radix_Sort dbr:Sort_algorithms dbr:Heap_Sort dbr:Quick_Sort dbr:Main_memory |
| dct:subject | dbc:Sorting_algorithms |
| rdf:type | yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 |
| rdfs:comment | An internal sort is any data sorting process that takes place entirely within the main memory of a computer. This is possible whenever the data to be sorted is small enough to all be held in the main memory. like a hard-disk. Any reading or writing of data to and from this slower media can slow the sortation process considerably. This issue has implications for different sort algorithms. Some common internal sorting algorithms include: 1. * Bubble Sort 2. * Insertion Sort 3. * Quick Sort 4. * Heap Sort 5. * Radix Sort 6. * Selection sort (en) Внутренняя сортировка (англ. internal sort) — разновидность алгоритмов сортировки или их реализаций, при которой объема оперативной памяти достаточно для помещения в неё сортируемого массива данных с произвольным доступом к любой ячейке и, собственно, для выполнения алгоритма. В этом случае сортировка происходит максимально быстро, так как скорость доступа к оперативной памяти значительно выше, чем к периферийным устройствам (соответственно, время доступа значительно меньше). В зависимости от конкретного алгоритма и его реализации данные могут сортироваться в той же области памяти, либо использовать дополнительную оперативную память. Внутренняя сортировка является базовой для любого алгоритма внешней сортировки — отдельные части массива данных сортируются в оперативной памяти и с помощью с (ru) |
| rdfs:label | Internal sort (en) Внутренняя сортировка (ru) |
| owl:sameAs | freebase:Internal sort yago-res:Internal sort wikidata:Internal sort dbpedia-az:Internal sort dbpedia-fa:Internal sort dbpedia-ru:Internal sort dbpedia-sr:Internal sort https://global.dbpedia.org/id/3p3g3 |
| prov:wasDerivedFrom | wikipedia-en:Internal_sort?oldid=922203166&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Internal_sort |
| is dbo:wikiPageRedirects of | dbr:Internal_sorting |
| is dbo:wikiPageWikiLink of | dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:The_Art_of_Computer_Programming dbr:Internal_sorting |
| is foaf:primaryTopic of | wikipedia-en:Internal_sort |