Кіріспе
Элементтер жұбын салыстыру арқылы жұмыс істейтін сұрыптау алгоритмінің түрі. Салыстыру сұрыптау – бұл тек бір абстрактілік салыстыру операциясы (көбінесе "кем немесе тең" операторы немесе үш жолды салыстыру) арқылы тізім элементтерін оқитын сұрыптау алгоритмінің түрі, ол соңғы сұрыпталған тізімде екі элементтің қайсысының бірінші болуы керектігін анықтайды. Жалғыз талап – оператордың деректер бойынша толық алдын ала реттілік құруы: егер a ≤ b және b ≤ c болса, онда a ≤ c (транзитивтілік); барлық a және b үшін, a ≤ b немесе b ≤ a (байланыстылық). a ≤ b және b ≤ a болуы мүмкін; бұл жағдайда сұрыпталған тізімде бірінші орынға кез келгені шығуы мүмкін. Тұрақты сұрыптауда кіріс реті осы жағдайда сұрыпталған ретті анықтайды. Әдебиетте зерттелетін салыстыру түрлері "салыстыруға негізделген". a және b элементтерін алмастыру немесе басқаша қайта орналастыру алгоритмімен тек осы элементтердің арасындағы реті алдыңғы салыстырулардың нәтижесі негізінде белгіленген кезде ғана жүзеге асырылады. Бұл a және b арасындағы реттілікті осы алдыңғы салыстыру нәтижелерінің транзитивті жабылуы арқылы алуға болатын жағдайда. Салыстыруға негізделген сұрыптаулар үшін салыстырудан басқа негізгі операцияларды орындау шешімі салыстырулардың нәтижесіне негізделеді. Сондықтан уақыт талдау кезінде орындалған салыстырулардың саны алмастыру немесе тағайындау сияқты орындалған негізгі операциялардың санының жоғарғы шегін анықтау үшін қолданылады, бұл сызықтық-логарифмдік уақыт деп аталады. Бұл тек салыстыру арқылы ғана қол жетімді шектеулі ақпараттың салдарынан, немесе басқаша айтқанда, толық реттелген жиынтықтардың тұйық алгебралық құрылымынан туындайды. Осы мағынада, біріктіру, үймелеу және интросортировка олар орындауы тиіс салыстырулардың саны жағынан асимптотикалық түрде оптималды, дегенмен бұл метрика басқа операцияларды ескермейді. Салыстыруға жатпайтын сұрыптаулар (мысалы, төменде қарастырылған мысалдар) салыстырудан басқа операцияларды қолдану арқылы O(n) өнімділікке қол жеткізе алады, бұл төменгі шекті айналып өтуге мүмкіндік береді (элементтердің мөлшері тұрақты деп есептесек). Салыстыру сұрыптаулары кейбір тізімдерде жылдам жұмыс істеуі мүмкін; көптеген бейімделуші сұрыптаулар, мысалы, енгізу сұрыптаулары, қазірдің өзінде сұрыпталған немесе жақында сұрыпталған тізімде O(n) уақытында жұмыс істейді. Ω(n log n) төменгі шек тек кіріс тізімі кез келген мүмкін ретпен болуы мүмкін жағдайда қолданылады. Нақты әлемдегі сұрыптау жылдамдығын өлшеу кейбір алгоритмдердің салыстырмалы түрде жылдам кэштелген компьютер жадын оңтайлы пайдалану қабілетін ескеруі қажет, немесе қолданба сұрыпталған деректер пайдаланушыға тез пайда бола бастайтын сұрыптау әдістерінен пайда болуы мүмкін (содан кейін пайдаланушының оқу жылдамдығы шектейтін фактор болады), бұл бүкіл тізім сұрыпталғанға дейін ешқандай нәтиже бермейтін сұрыптау әдістеріне қарсы. Осы шектеулерге қарамастан, салыстыру сұрыптаулары салыстыру функциясын басқару көптеген әртүрлі деректер түрлерін сұрыптауға және тізімді қалай сұрыптауды жақсы бақылауға мүмкіндік беретін маңызды практикалық артықшылықты ұсынады. Мысалы, салыстыру функциясының нәтижесін кері қайтару тізімді кері реттеп алуға мүмкіндік береді; ал түпкілік тәртіппен тізімді сұрыптау үшін әр бөлігін ретпен салыстыратын салыстыру функциясын жасауға болады:
function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc)) {
if (lefta ≠ righta)
return compare(lefta, righta);
else if (leftb ≠ rightb)
return compare(leftb, rightb);
else
return compare(leftc, rightc);
}
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with:
if a ≤ b and b ≤ c then a ≤ c (transitivity)
for all a and b, a ≤ b or b ≤ a (connexity). It is possible that both a ≤ b and b ≤ a; in this case either may come first in the sorted list. In a stable sort, the input order determines the sorted order in this case. Comparison sorts studied in the literature are "comparison based". Elements a and b can be swapped or otherwise re arranged by the algorithm only when the order between these elements has been established based on the outcomes of prior comparisons. This is the case when the order between a and b can be derived via the transitive closure of these prior comparison outcomes. For comparison based sorts the decision to execute basic operations other than comparisons is based on the outcome of comparisons. Hence in a time analysis the number of executed comparisons is used to determine upper bound estimates for the number of executed basic operations such as swaps or assignments. which is known as linearithmic time. This is a consequence of the limited information available through comparisons alone — or, to put it differently, of the vague algebraic structure of totally ordered sets. In this sense, mergesort, heapsort, and introsort are asymptotically optimal in terms of the number of comparisons they must perform, although this metric neglects other operations. Non comparison sorts (such as the examples discussed below) can achieve O(n) performance by using operations other than comparisons, allowing them to sidestep this lower bound (assuming elements are constant sized). Comparison sorts may run faster on some lists; many adaptive sorts such as insertion sort run in O(n) time on an already sorted or nearly sorted list. The Ω(n log n) lower bound applies only to the case in which the input list can be in any possible order. Real world measures of sorting speed may need to take into account the ability of some algorithms to optimally use relatively fast cached computer memory, or the application may benefit from sorting methods where sorted data begins to appear to the user quickly (and then user's speed of reading will be the limiting factor) as opposed to sorting methods where no output is available until the whole list is sorted. Despite these limitations, comparison sorts offer the notable practical advantage that control over the comparison function allows sorting of many different datatypes and fine control over how the list is sorted. For example, reversing the result of the comparison function allows the list to be sorted in reverse; and one can sort a list of tuples in lexicographic order by just creating a comparison function that compares each part in sequence:
function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
if lefta ≠ righta
return compare(lefta, righta)
else if leftb ≠ rightb
return compare(leftb, rightb)
else
return compare(leftc, rightc)
Comparison sorts generally adapt more easily to complex orders such as the order of floating point numbers. Additionally, once a comparison function is written, any comparison sort can be used without modification; non comparison sorts typically require specialized versions for each datatype. This flexibility, together with the efficiency of the above comparison sorting algorithms on modern computers, has led to widespread preference for comparison sorts in most practical work.
Салыстыру сұрыптаулары күрделі реттерге, мысалы, қалқыма нүктелі сандардың ретіне оңай бейімделеді. Сонымен қатар, салыстыру функциясы жазылғаннан кейін кез келген салыстыру сұрыптауын өзгертусіз қолдануға болады; салыстыру емес сұрыптаулар әдетте әрбір дерек түрі үшін арнайы нұсқаларды қажет етеді. Бұл икемділік, жоғарыда аталған салыстыру сұрыптау алгоритмдерінің тиімділігімен бірге, қазіргі заманғы компьютерлерде салыстыру сұрыптауларын көптеген практикалық жұмыстарда кеңінен таңдауға әкелді.
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with:
if a ≤ b and b ≤ c then a ≤ c (transitivity)
for all a and b, a ≤ b or b ≤ a (connexity). It is possible that both a ≤ b and b ≤ a; in this case either may come first in the sorted list. In a stable sort, the input order determines the sorted order in this case. Comparison sorts studied in the literature are "comparison based". Elements a and b can be swapped or otherwise re arranged by the algorithm only when the order between these elements has been established based on the outcomes of prior comparisons. This is the case when the order between a and b can be derived via the transitive closure of these prior comparison outcomes. For comparison based sorts the decision to execute basic operations other than comparisons is based on the outcome of comparisons. Hence in a time analysis the number of executed comparisons is used to determine upper bound estimates for the number of executed basic operations such as swaps or assignments. which is known as linearithmic time. This is a consequence of the limited information available through comparisons alone — or, to put it differently, of the vague algebraic structure of totally ordered sets. In this sense, mergesort, heapsort, and introsort are asymptotically optimal in terms of the number of comparisons they must perform, although this metric neglects other operations. Non comparison sorts (such as the examples discussed below) can achieve O(n) performance by using operations other than comparisons, allowing them to sidestep this lower bound (assuming elements are constant sized). Comparison sorts may run faster on some lists; many adaptive sorts such as insertion sort run in O(n) time on an already sorted or nearly sorted list. The Ω(n log n) lower bound applies only to the case in which the input list can be in any possible order. Real world measures of sorting speed may need to take into account the ability of some algorithms to optimally use relatively fast cached computer memory, or the application may benefit from sorting methods where sorted data begins to appear to the user quickly (and then user's speed of reading will be the limiting factor) as opposed to sorting methods where no output is available until the whole list is sorted. Despite these limitations, comparison sorts offer the notable practical advantage that control over the comparison function allows sorting of many different datatypes and fine control over how the list is sorted. For example, reversing the result of the comparison function allows the list to be sorted in reverse; and one can sort a list of tuples in lexicographic order by just creating a comparison function that compares each part in sequence:
function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
if lefta ≠ righta
return compare(lefta, righta)
else if leftb ≠ rightb
return compare(leftb, rightb)
else
return compare(leftc, rightc)
Comparison sorts generally adapt more easily to complex orders such as the order of floating point numbers. Additionally, once a comparison function is written, any comparison sort can be used without modification; non comparison sorts typically require specialized versions for each datatype. This flexibility, together with the efficiency of the above comparison sorting algorithms on modern computers, has led to widespread preference for comparison sorts in most practical work.
Баламалар
Кейбір сұрыптау мәселелері салыстыру арқылы сұрыптау үшін Ω(n log n) шегінен қатаң жылдам шешімге ие, оны салыстырусыз сұрыптау арқылы қолдануға болады; мысалы, бүтін сандарды сұрыптау, онда барлық кілттер бүтін сандар болып табылады. Кілттердің диапазоны n-мен салыстырғанда шағын болғанда, санау сұрыптау сызықтық уақытта жұмыс істейтін алгоритмнің мысалы болып табылады. Радикстік сұрыптау сияқты басқа бүтін сандарды сұрыптау алгоритмдері салыстыру арқылы сұрыптаудан асимптотикалық тұрғыдан жылдам болмаса да, практикада жылдам болуы мүмкін. Сандар жұбын олардың қосындысы бойынша сұрыптау мәселесі де Ω(n² log n) шегіне бағынбауға болады (жұптастырудан туындаған квадрат); ең жақсы белгілі алгоритм әлі де O(n² log n) уақыт алады, бірақ тек O(n²) салыстыруды қажет етеді.