Кіріспе
Компьютерлік ғылымда салыстыру желілері – бұл белгілі бір сандағы "сымдардан" құралған абстрактілі құрылғылар, олар мәндерді тасымалдайды және сымдардың жұптарын қосып, егер мәндер қажетті ретпен болмаса, сымдардағы мәндерді ауыстыратын салыстыру модульдерін қамтиды. Мұндай желілер көбінесе белгілі бір сандағы мәндерді сұрыптау үшін жасалады, мұндай жағдайда олар сұрыптау желілері деп аталады. Сұрыптау желілері жалпы салыстыру алгоритмдерінен ерекшеленеді, олар кез келген көлемдегі кіріс мәндерін өңдей алмайды және олардың салыстыру тізбегі алдын ала белгіленеді, бұл алдыңғы салыстырулардың нәтижесіне тәуелсіз. Үлкен көлемдегі кіріс мәндерін сұрыптау үшін жаңа сұрыптау желілерін құру қажет. Салыстыру тізбегінің тәуелсіздігі параллель орындау үшін және аппараттық құрылымдарда іске асыру үшін пайдалы. Сұрыптау желілерінің қарапайымдылығына қарамастан, олардың теориясы өте терең және күрделі. Сұрыптау желілерін алғаш рет шамамен 1954 жылы Армстронг, Нельсон және О'Коннор зерттеген.
In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such networks are typically designed to perform sorting on fixed numbers of values, in which case they are called sorting networks. Sorting networks differ from general comparison sorts in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. In order to sort larger amounts of inputs, new sorting networks must be constructed. This independence of comparison sequences is useful for parallel execution and for implementation in hardware. Despite the simplicity of sorting nets, their theory is surprisingly deep and complex. Sorting networks were first studied circa 1954 by Armstrong, Nelson and O'Connor,
Sorting networks can be implemented either in hardware or in software. Donald Knuth describes how the comparators for binary integers can be implemented as simple, three state electronic devices. Since the 2000s, sorting nets (especially bitonic mergesort) are used by the GPGPU community for constructing sorting algorithms to run on graphics processing units.
Сұрыптау желілерін аппараттық немесе бағдарламалық қамтамасыз етуде іске асыруға болады. Дональд Кнут бинарлық бүтін сандар үшін салыстырғыштарды қарапайым, үш күйлі электрондық құрылғылар ретінде қалай іске асыруға болатынын сипаттайды. 2000 жылдардан бері сұрыптау желілері (әсіресе битоникалық біріктіру) GPGPU қауымдастығы графикалық процессорларда жұмыс істейтін сұрыптау алгоритмдерін құру үшін қолданылады.
In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such networks are typically designed to perform sorting on fixed numbers of values, in which case they are called sorting networks. Sorting networks differ from general comparison sorts in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. In order to sort larger amounts of inputs, new sorting networks must be constructed. This independence of comparison sequences is useful for parallel execution and for implementation in hardware. Despite the simplicity of sorting nets, their theory is surprisingly deep and complex. Sorting networks were first studied circa 1954 by Armstrong, Nelson and O'Connor,
Sorting networks can be implemented either in hardware or in software. Donald Knuth describes how the comparators for binary integers can be implemented as simple, three state electronic devices. Since the 2000s, sorting nets (especially bitonic mergesort) are used by the GPGPU community for constructing sorting algorithms to run on graphics processing units.
Кіріспе
Сорталау желісі екі түрден тұрады: салыстырғыштар мен сымдар. Сымдар солдан оңға қарай жүреді, олар желі арқылы бір мезгілде өтетін мәндерді (әр сымға бір мән) тасымалдайды. Әрбір салыстырғыш екі сымды байланыстырады. Егер екі мән, екі сым арқылы жүзіп келе жатса, олар салыстырғышқа тап болғанда, жоғарғы сымның мәні төменгі сымның мәнінен үлкен немесе тең болса ғана мәндер ауыстырылады. Формула бойынша, егер жоғарғы сым x мәнін, ал төменгі сым y мәнін тасыса, салыстырғыштан өткеннен кейін сымдар тиісінше және мәнін тасымалдайды, осылайша мәндер жұбы сұрыпталады. Барлық мүмкін кірістерді өсу ретімен дұрыс сұрыптайтын сымдар мен салыстырғыштар желісі сорлау желісі немесе Крускаль торабы деп аталады. Желіні кері бұру арқылы, барлық кірістерді кему ретімен сұрыптауға да болады. Қарапайым сорлау желісінің толық жұмысы төменде көрсетілген. Бұл сорлау желісі кірістерді дұрыс сұрыптайтыны анық көрінеді; бірінші төрт салыстырғыш ең үлкен мәнді төменге "батырып", ең кіші мәнді жоғарыға "көтереді" екенін ескеріңіз. Соңғы салыстырғыш ортадағы екі сымды реттейді.
Тереңдік пен тиімділік
Сорталау желісінің тиімділігі оның жалпы көлемімен, яғни желідегі салыстырғыштар санымен немесе оның тереңдігімен өлшенуі мүмкін, ол (бейресми түрде) кез келген кіріс мәнінің желі арқылы өтетін жолында кездесетін салыстырғыштардың ең үлкен саны ретінде анықталады. Сорталау желілері белгілі бір салыстыруларды параллель түрде орындай алатынын ескерсек (графикалық белгіде бір тік сызықта орналасқан салыстырғыштармен көрсетілген), және барлық салыстырулар бірлік уақыт алады деп есептесек, желінің тереңдігі оны орындауға қажетті уақыт қадамдарының санына тең болады. Маңызды теориялық жаңалық болғанымен, AKS желісінің практикалық қолданылуы өте шектеулі, себебі Үлкен О белгісімен жасырылған үлкен сызықтық тұрақты бар. Гудрич 2014 жылы O(n log n) көлемді цигзаг сұрыптау желісін жасады. Оның көлемі AKS желісіне қарағанда әлдеқайда кіші болғанымен, O(n log n) тереңдігі оны параллель түрде жүзеге асыруға қолайсыз етеді.