Сортировка кірістіру әдісі

Кіріспе

Сорталау алгоритмі – салыстыру арқылы бір-бірлеп элемент қосып, соңғы реттелген массивті (немесе тізімді) құратын қарапайым сұрыптау алгоритмі. Үлкен тізімдерде ол жылдам сұрыптау, үймелі сұрыптау немесе біріктіру сұрыптау сияқты жетілдірілген алгоритмдерге қарағанда әлдеқайда тиімсіз. Дегенмен, енгізу сұрыптау бірнеше артықшылықтар ұсынады:

Оңай іске асыру: Джон Бентли C/C++ тіліндегі үш жолдық нұсқасын көрсеткен, ол оңтайландырылғанда бес жолға дейін жетеді.

Басқа сұрыптау алгоритмдерімен байланыс

Сақтау сұрыптау таңдау сұрыптауға өте ұқсас. Таңдау сұрыптаудағыдай, массив бойынша k рет өтілгеннен кейін алғашқы k элемент сұрыпталған болады. Дегенмен, екі алгоритмнің басты айырмашылығы – сақтау сұрыптау ағымдағы кілттен артқа қарай іздейді, ал таңдау сұрыптау алға қарай іздейді. Бұл таңдау сұрыптауда алғашқы k элементтің сұрыпталмаған кірістің k ең кіші элементі ретінде анықтаса, сақтау сұрыптауда олар кірістің алғашқы k элементі болып табылады. Сақтау сұрыптаудың таңдау сұрыптаудан басты артықшылығы – таңдау сұрыптау тізімнің сұрыпталмаған бөлігіндегі ең кіші элементті табу үшін қалған барлық элементтерді міндетті түрде қарап шығаруы керек, ал сақтау сұрыптау (k+1)-ші элемент k-шы элементтен үлкен болған жағдайда тек бір салыстыруды қажет етеді. Бұл жиі орын алғанда (мысалы, кіріс массиві қазірдің өзінде сұрыпталған немесе жартылай сұрыпталған болса), сақтау сұрыптау таңдау сұрыптауға қарағанда айқын тиімдірек болады. Орташа есепте (k+1)-ші элементтің орны кездейсоқ деп есептегенде), сақтау сұрыптау алдыңғы k элементтің жартысын салыстырып, жылдыруды қажет етеді, яғни сақтау сұрыптау орташа есеппен таңдау сұрыптауға қарағанда шамамен жартысына жуық салыстыру жасайды. Сақтау сұрыптаудың ең нашар жағдайында (кіріс массиві кері сұрыпталғанда) сақтау сұрыптау таңдау сұрыптаумен бірдей мөлшерде салыстыру жасайды. Алайда, сақтау сұрыптаудың таңдау сұрыптауға қарағанда кемшілігі – әр итерацияда (k+1)-ші элементті массивтің сұрыпталған бөлігіне енгізу үшін көптеген элементтерді жылдыру қажет болғандықтан, көбірек жазу операцияларын қажет етеді, ал таңдау сұрыптаудың әр итерациясы үшін тек бір жылдыру жеткілікті. Жалпы, сақтау сұрыптау массивке O(n²) рет жазады, ал таңдау сұрыптау тек O(n) рет жазады. Осы себепті, EEPROM немесе флэш-жад сияқты жадқа жазу оқудан әлдеқайда қымбат болған жағдайларда таңдау сұрыптау артық болуы мүмкін. Жылдам сұрыптау және біріктіру сұрыптау сияқты кейбір «бөліп билеу» алгоритмдері үлкен массивтер үшін сақтау сұрыптаудан артық болса, сақтау сұрыптау немесе таңдау сұрыптау сияқты рекурсивті емес сұрыптау алгоритмдері әдетте өте кішкентай массивтер үшін (нақты мөлшері ортаға және іске асыруға байланысты, бірақ әдетте 7 мен 50 элемент арасында) жылдам болады. Сондықтан, осы алгоритмдерді іске асыруда пайдалы оңтайландыру – гибридтік тәсіл, массив кіші өлшемге бөлінген кезде қарапайым алгоритмді пайдалану. Егер салыстырудың құны жылдырудан жоғары болса (мысалы, сілтеме арқылы сақталған мәтіндік кілттер немесе адамның өзара әрекеттесуі, мысалы, қатар көрсетілген екі элементтен біреуін таңдау), онда екілік сақтау сұрыптауын пайдалану жақсы нәтиже беруі мүмкін. Екілік сақтау сұрыптау жаңа элементтерді енгізу үшін дұрыс орынды анықтау үшін екілік іздеуді қолданады, сондықтан ең нашар жағдайда log₂n салыстыру жасайды. Массивтегі әрбір элемент ізделіп, енгізілгенде бұл O(n log n) болады. Әрбір енгізу үшін бір-бірінен жылдыруды болдырмау үшін кіріс элементтерді байланысты тізімде сақтауға болады, бұл тізімге элементтерді орны белгілі болғанда тұрақты уақытта қосуға немесе одан шығаруға мүмкіндік береді. Алайда, байланысты тізімде іздеу үшін қажетті орынға сілтемелерді бірізді түрде орындау қажет: байланысты тізімде кездейсоқ қол жетімділік жоқ, сондықтан ол екілік іздеу сияқты жылдам әдісті қолдана алмайды. Сондықтан іздеу үшін қажетті уақыт O(n), ал сұрыптау уақыты O(n²) болады. Егер күрделірек дерек құрылымы (мысалы, үйінді немесе екілік ағаш) қолданылса, іздеу мен енгізу үшін қажетті уақыт айтарлықтай қысқаруы мүмкін; бұл үйінді сұрыптаудың және екілік ағаш сұрыптаудың мәні. 2006 жылы Бендер, Мартин Фарач Колтон және Мостеиро кітапхана сұрыптау немесе аралықты сақтау деп аталатын жаңа сұрыптау түрін жариялады, ол массивке таралған аз мөлшерде пайдаланылмаған кеңістік қалдырады. Пайдасы – енгізулер тек аралыққа жеткенше элементтерді жылдырып отыруды қажет етеді. Авторлар бұл сұрыптау алгоритмі жоғары ықтималдылықпен O(n log n) уақытында жұмыс істейтінін көрсетеді. Егер өткізіп тастау тізімі қолданылса, енгізу уақыты O(log n) дейін төмендейді, ал жылдырулар қажет емес, өйткені өткізіп тастау тізімі байланысты тізім құрылымында іске асырылады. Сақтаудың соңғы жұмыс уақыты O(n log n) болады.

Insertion sort is very similar to selection sort. As in selection sort, after k passes through the array, the first k elements are in sorted order. However, the fundamental difference between the two algorithms is that insertion sort scans backwards from the current key, while selection sort scans forwards. This results in selection sort making the first k elements the k smallest elements of the unsorted input, while in insertion sort they are simply the first k elements of the input. The primary advantage of insertion sort over selection sort is that selection sort must always scan all remaining elements to find the absolute smallest element in the unsorted portion of the list, while insertion sort requires only a single comparison when the (k + 1) st element is greater than the k th element; when this is frequently true (such as if the input array is already sorted or partially sorted), insertion sort is distinctly more efficient compared to selection sort. On average (assuming the rank of the (k + 1) st element rank is random), insertion sort will require comparing and shifting half of the previous k elements, meaning that insertion sort will perform about half as many comparisons as selection sort on average. In the worst case for insertion sort (when the input array is reverse sorted), insertion sort performs just as many comparisons as selection sort. However, a disadvantage of insertion sort over selection sort is that it requires more writes due to the fact that, on each iteration, inserting the (k + 1) st element into the sorted portion of the array requires many element swaps to shift all of the following elements, while only a single swap is required for each iteration of selection sort. In general, insertion sort will write to the array O(n2) times, whereas selection sort will write only O(n) times. For this reason selection sort may be preferable in cases where writing to memory is significantly more expensive than reading, such as with EEPROM or flash memory. While some divide and conquer algorithms such as quicksort and mergesort outperform insertion sort for larger arrays, non recursive sorting algorithms such as insertion sort or selection sort are generally faster for very small arrays (the exact size varies by environment and implementation, but is typically between 7 and 50 elements). Therefore, a useful optimization in the implementation of those algorithms is a hybrid approach, using the simpler algorithm when the array has been divided to a small size. If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side by side), then using binary insertion sort may yield better performance. Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2 n⌉ comparisons in the worst case. When each element in the array is searched for and inserted this is O(n log n). To avoid having to make a series of swaps for each insertion, the input could be stored in a linked list, which allows elements to be spliced into or out of the list in constant time when the position in the list is known. However, searching a linked list requires sequentially following the links to the desired position: a linked list does not have random access, so it cannot use a faster method such as binary search. Therefore, the running time required for searching is O(n), and the time for sorting is O(n2). If a more sophisticated data structure (e. g., heap or binary tree) is used, the time required for searching and insertion can be reduced significantly; this is the essence of heap sort and binary tree sort. In 2006 Bender, Martin Farach Colton, and Mosteiro published a new variant of insertion sort called library sort or gapped insertion sort that leaves a small number of unused spaces (i. e., "gaps") spread throughout the array. The benefit is that insertions need only shift elements over until a gap is reached. The authors show that this sorting algorithm runs with high probability in O(n log n) time. If a skip list is used, the insertion time is brought down to O(log n), and swaps are not needed because the skip list is implemented on a linked list structure. The final running time for insertion would be O(n log n).