Іріктеу сұрыптау алгоритмі: қарапайым, салыстыруға негізделген әдіс. Оның уақыт күрделігі O(n2), жад шектеулі жағдайларда тиімді. Бағдарламалау үшін пайдалы.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Сорталау алгоритмі
Sorting algorithm
Компьютерлік ғылымда, таңдау арқылы сұрыптау – деректерді орнында салыстыру арқылы сұрыптау алгоритмі. Оның уақыт күрделілігі O(n²), бұл оны үлкен тізімдерде тиімсіз етеді және көбінесе ұқсас енгізу арқылы сұрыптаудан нашар жұмыс істейді. Таңдау арқылы сұрыптау қарапайымдығымен ерекшеленеді және кейбір жағдайларда, әсіресе қосымша жад шектеулі болғанда, күрделі алгоритмдерге қарағанда артықшылықтарға ие. Алгоритм кіріс тізімін екі бөлікке бөледі: тізімнің басында (сол жақта) солдан оңға қарай құрылатын сұрыпталған кіші тізім және тізімнің қалған бөлігін құрайтын сұрыпталмаған элементтердің кіші тізімі. Бастапқыда сұрыпталған кіші тізім бос болады, ал сұрыпталмаған кіші тізім – кіріс тізімінің толық бөлігі. Алгоритм сұрыпталмаған кіші тізімдегі ең кіші (немесе ең үлкен, сұрыптау ретіне байланысты) элементті тауып, оны сұрыпталмаған бөліктің сол жақ шетіндегі элементпен алмастырып (орнымен ауыстырып), кіші тізімнің шекарасын бір элементке оңға жылжытады. Таңдау арқылы сұрыптаудың уақыт тиімділігі квадраттық, сондықтан таңдау арқылы сұрыптаудан жақсы уақыт күрделілігіне ие бірнеше сұрыптау техникалары бар.
In computer science, selection sort is an in place comparison sorting algorithm. It has an O(n2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited. The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right. The time efficiency of selection sort is quadratic, so there are a number of sorting techniques which have better time complexity than selection sort.
Басқа сұрыптау алгоритмдермен салыстыру
Квадраттық сұрыптау алгоритмдерінің арасында (орташа жағдайда Θ(n2) күрделігі бар сұрыптау алгоритмдері), таңдау сұрыптау көбінесе көпіршік сұрыптау және гном сұрыптау алгоритмдерінен жақсы нәтижелер көрсетеді. Қыстыру сұрыптау да өте ұқсас, себебі kth итерациядан кейін массивтегі алғашқы k элементі сұрыпталған болады. Қыстыру сұрыптаудың артықшылығы – st элементін орналастыру үшін қажетті элементтерді ғана қарау, ал таңдау сұрыптау st элементін табу үшін массивтегі қалған барлық элементтерді қарауы керек. Қарапайым есептеулер көрсеткендей, қыстыру сұрыптау таңдау сұрыптауға қарағанда шамамен екі есе аз салыстыру операциясын жасайды, бірақ бұл көрсеткіш массивдің бастапқы ретіне байланысты өзгеруі мүмкін. Кейбір нақты уақыт қолданулары үшін таңдау сұрыптаудың масситтің ретіне қарамастан, әрқашан бірдей жұмыс істеуі артықшылық болып есептелуі мүмкін, ал қыстыру сұрыптаудың орындалу уақыты айтарлықтай өзгеріп отыруы мүмкін. Дегенмен, бұл көбінесе қыстыру сұрыптау үшін артықшылық болып табылады, өйткені массив қазірдің өзінде сұрыпталған немесе "сұрыпталғанға жақын" болса, ол әлдеқайда тиімді жұмыс істейді. Жазулар саны бойынша таңдау сұрыптау қыстыру сұрыптаудан артықшылыққа ие (алмасуларға қарсы, әр алмасу екі жазу операциясынан тұрады), бұл циклдық сұрыптаумен қол жеткізілетін теориялық минимумнан екі есеге жуық, ол ең көп дегенде n жазу операциясын жасайды. Егер жазу операциялары оқу операцияларынан әлдеқайда қымбат болса (мысалы, EEPROM немесе Flash жадында, әр жазу жадтың қызмет ету мерзімін қысқартады), бұл маңызды болуы мүмкін. Таңдау сұрыптау CPU тармақтау болжаушыларының жұмысын жақсарту үшін, тармақталмайтын кодты қолданып ең төменгі элементті табу және содан кейін алмасуды шартсыз түрде орындау арқылы болжауға қиындық тудырмайтын етіп жүзеге асырылуы мүмкін. Соңында, үлкен массивтерде таңдау сұрыптау біріктіру сұрыптау сияқты "бөліп жеңу" алгоритмдерімен салыстырғанда нашар жұмыс істейді. Алайда, қыстыру сұрыптау немесе таңдау сұрыптау әдетте кіші массивтер үшін (яғни 10–20 элементтен аз) жылдам болады. Практикада рекурсивті алгоритмдер үшін пайдалы оңтайландыру – "жеткілікті кішкентай" кіші тізімдер үшін қыстыру сұрыптау немесе таңдау сұрыптауға ауысу.
Among quadratic sorting algorithms (sorting algorithms with a simple average case of Θ(n2)), selection sort almost always outperforms bubble sort and gnome sort. Insertion sort is very similar in that after the kth iteration, the first elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the st element, while selection sort must scan all remaining elements to find the st element. Simple calculation shows that insertion sort will therefore usually perform about half as many comparisons as selection sort, although it can perform just as many or far fewer depending on the order the array was in prior to sorting. It can be seen as an advantage for some real time applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably. However, this is more often an advantage for insertion sort in that it runs much more efficiently if the array is already sorted or "close to sorted." While selection sort is preferable to insertion sort in terms of number of writes ( swaps versus up to swaps, with each swap being two writes), this is roughly twice the theoretical minimum achieved by cycle sort, which performs at most n writes. This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory. Selection sort can be implemented without unpredictable branches for the benefit of CPU branch predictors, by finding the location of the minimum with branch free code and then performing the swap unconditionally. Finally, selection sort is greatly outperformed on larger arrays by divide and conquer algorithms such as mergesort. However, insertion sort or selection sort are both typically faster for small arrays (i. e. fewer than 10–20 elements). A useful optimization in practice for the recursive algorithms is to switch to insertion sort or selection sort for "small enough" sublists.