Razryadli saralaw, tez saralaw algoritmlari

RAZRYADLI SARALAW, TEZ SARALAW ALGORITMLARI
Radix sort birinshi ret matematikalıq hám filosof Charlz Sanders Peirce tárepinen 1887 jılda kiritilgen. Ol sózlikte sózlerdi saralaw usılınan paydalanǵan. Keyinirek, 1954 jılda Garold Syuard perfokartalarni saralaw texnikasın qollaǵan halda algoritmdı islep shıǵıwǵa úles qosdı. Radix sort túsinigi áyyemgi Indiyada buddist xristian monaxlar tárepinen kiritilgen Radix sanaq sistemasına tiykarlanǵan. Olar arifmetik esap -kitaplardı ámelge asırıw ushın esaplaw taxtası sistemasınan paydalanıwadı. Olar toǵızta nomerdi ańlatıw ushın 1 den 9 ǵa shekem bolǵan nomerlerden paydalanıwadı hám keyin cikldı tákirarlap, cikl nomerin kórsetiw ushın hár bir nomerdiń ústine sızıq qoyıwadı. Bul elementlerdi jaylasıw bahaları tiykarında tártiplew arqalı Radix saralaw usılına uqsaydı. Sondan berli cifrlı maǵlıwmatlardı elementler ortasında salıstırıwlawǵa hájet qaldırmasdan nátiyjeli saralaw ushın Radiks menen tártiplew kompyuter páninde keń qollanila baslandı. Ol maǵlıwmatlardı analiz qılıw, tábiyiy tildi qayta islew hám suwretti qayta islew sıyaqlı hár qıylı qosımshalarda qollanılǵan. Ulıwma alǵanda, waqıt ótiwi menen Radix sortning engiziliwi hám rawajlanıwlashtirilishi informatika daǵı nátiyjeli tártiplew algoritmların talap etetuǵın kóplegen mashqalalardi sheshiwge járdem berdi
1. Radix Sort ne?
Razryadlı saralaw (Radix sort) algoritmı, dızbekti sanlar ruyxatini saralaw ushın isletiledi. Bul algoritm, korrektor kestelerdi islewde hám basqa bir neshe zárúrli ámeliyatlarda da paydalanıladı. Radix sort, hár bir nomerge qaray kesteni saralaydı. Yaǵnıy, birinshi nomerden baslap aqırǵı nomerge shekem bolǵan nomerlerdi óz ishine aladı hám hár bir nomer ushın " radix" ni jaratadı. Hár bir radixda saralanǵan elementler, keyingi radikslar boyınsha qayta tártiplengen halda saqlanadı. Bul algoritmdıń tiykarǵı qádemalaridan biri, elementlerdi olardıń aqırǵı nomerlerine qaray saralamas bolıp tabıladı. Keyin onı olardıń aqırǵı tórtlıqlarına qaray saralamastán ótkeriw kerek. Jámi sol kóriniste, algoritm aqırǵı nomerler boyınsha analiz etip, keyingi radikslarga keltirilgen elementlerdi saralaydı. Radix sortning avtomatikalıq túrde tártiplew menen baylanıslı máseleler tuwıladı. Mısalı, " 10" sanın " 2" den aldınǵa jazıw menen baylanıslı másele bar. Bunday jaǵdaylarda Radix sort jumısqa túsirilmaydi. Sonıń menen birge, bul algoritmdıń saralaw procesi mudamı tuwrı hám tolıq bolıwı kerek. Radix sort - bul birdey zárúrli pozitsiya hám mániske iye bolǵan nomerlerdi gruppalaw arqalı pútkil san giltleri menen maǵlıwmatlardı saralaytuǵın salıstırıwiy bolmaǵan pútkil sanlardı saralaw algoritmı. Bul sızıqlı waqıtlı quramalılıq algoritmı bolıp, úlken maǵlıwmatlar jıynaqları ushın tez saralaw, birlestiriw yamasa jıynama tártiplew sıyaqlı salıstırıwlawǵa tiykarlanǵan saralaw algoritmlarına qaraǵanda tezirek. Algoritm tártiplengen giltlerdiń hár bir nomerin oń tárepten shepke tákirarlaw arqalı isleydi. Hár bir iteratsiyada tuymeler sol orındaǵı nomerge qaray tártiplenedi. Bul process tuymeshelerdegi hár bir zárúrli nomer ushın tákirarlanadı. Radiksli tártiplew hár qanday radiks bazası menen maǵlıwmatlardı saralaw ushın ámelge asırılıwı múmkin, lekin ol ádetde ekilik, onlıq yamasa on altılıq nomerler menen isletiledi. Radix tártiplew O (kn) waqıt quramalılıǵına iye, bul erda k - eń úlken giltdagi nomerler sanı hám n - tártiplengen giltler sanı. Shıǵıw hám aralıq dızbeklerdi saqlaw ushın qosımsha yad talap etiledi hám eger tuymelerdegi nomerler sanı júdá kóp bolsa, onıń islewi jamanlasıwı múmkin.
Sheklewlerge qaramay, radix sort úlken maǵlıwmatlar jıynaqların pútkil sanlı giltler menen saralaw ushın paydalı algoritm bolıp, ol tez-tez informatika hám maǵlıwmatlardı analiz qılıw, suwretti qayta islew hám kompyuter grafikası sıyaqlı injenerlik programmalarında qollanıladı. Radix Sort - bul algoritm bolıp tabıladı, rasında, nomerler sıyaqlı belgilengen bir túrge iye maǵlıwmatlardı saralaw ushın isletiledi. Bul algoritmdı basqa saralaw túrleri menen salıstırıp kórsek, Radix Sort eń jaqsı hám tezirek isleytuǵın algoritmlardan biri esaplanadı.
2. Radix Sort qanday isleydi?
Radix Sort qanday isleydi?
Radix sortning tiykarǵı ózgeriwshileri tómendegiler bolıp tabıladı:
• Sáne uzınlıǵı
• Maǵlıwmat sanın ańlatiwshı radix Algoritmnning tiykarǵı qádemari tómendegishe:
1. Maǵlıwmatlardı awdarmalaw : Maǵlıwmatlar awdarma etiliwi hám olardı saralaw ushın paydalanıw múmkin bolǵan formatqa ótkeriliwi kerek. Mısal ushın, sanlar decimal formatında bolsa hám 3 cifrlı bolsa, hár bir nomerdi ózi menen saralaw múmkin.
2. Radix boyınsha alıw : Maǵlıwmatlar radix boyınsha ajratıladı. Bul ya sáne uzınlıǵı yamasa maǵlıwmatlardıń arnawlı bir ózgesheligi (mısalı, sanlar ushın 10 ) bolıwı múmkin.
3. Hesh qanday saralamaǵan halda elementlerdi saralaw : Bul qádemde biz maǵlıwmatlardı bir tártipte birlestiriwdi istamaymiz. Esaptan tısqarı jaǵdaylarda, bir radixdan paydalanıw joqarı dárejedegi hár bir radixdan paydalanıw menen támiyinlenedi.
4. Radix boyınsha saralaw : Bul qádemde, maǵlıwmatlar ózleriniń ózinde saralgan hám olarǵa tiykarlanǵan tártipte saraliladi.
5. Bahalar boyınsha saralaw : Eger eki yamasa odan kóp element birdey mániske iye bolsa, olardı ápiwayı tárzde saralamaslik múmkin. Sol sebepli, olardı basqa bir algoritm arqalı saralaw kerek.
Radix Sortning abzallıqları :
• O'nlab elementli listalar ushın júdá tez islesedi.
• Barlıq baha túrleri ushın paydalı bolıp tabıladı.
• Haqıyqıy hám nátiyjeli algoritm bolıp tabıladı.
• Radix Sortning aqırǵı qádeminde elementlerdi basqa algoritmlar járdeminde sanaq nusqalandi múmkin.
Radix Sortning kemshilikleri:
• Algoritmda úlken maǵlıwmatlar ushın yad kópligi zárúr.
• Maǵlıwmatlar kompleksiniń awdarması kerek boladı.
• Maǵlıwmatlardı ajıratıw kerek, bul qanshellilik zárúrligini názerde tutingizga baylanıslı.
Radix Sort - bul tártiplew algoritmı bolıp, maǵlıwmatlardı bólek nomerler yamasa cifrlardıń strukturalıq bólimlerin gruppalaw hám olardıń ma`nisine qaray tártiplew arqalı tártipleydi. Ol ádetde qatarlardı, maǵlıwmatlar bazaların hám kóplegen komponentlerge iye bolǵan basqa maǵlıwmatlar túrlerin saralaw ushın isletiledi. Algoritm maǵlıwmatlardı eń zárúrli nomerge, keyininen keyingi eń zárúrli nomerge hám soǵan uqsas eń zárúrli nomerge yetguncha saralaw arqalı isleydi. Bul process maǵlıwmatlar tolıq saralanmaguncha tákirarlanadı. Radix tártiplew O (nk) waqıt quramalılıǵına iye, bul erda n - saralanatuǵın elementler sanı hám k - hár qanday element degi cifrlardıń maksimal sanı. Kóbinese saralanıp atırǵan maǵlıwmatlar kóp sanlı komponentlerge iye bolsa, olardıń islewin jaqsılaw ushın tez saralaw yamasa birlestiriw sıyaqlı basqa tártiplew algoritmları menen birgelikte isletiledi.
Ulıwma alǵanda, radix sort úlken kólem degi maǵlıwmatlardı tez hám nátiyjeli saralaw ushın paydalı algoritm bolıp tabıladı, ásirese maǵlıwmatlar bólek komponentlerge ańsatlıq penen bólinetuǵın formatda bolsa.
Mısallar :
Mısal ushın, tómendegi sanlardı tártiplewdi kóremiz:
170, 45, 75, 90, 802, 24, 2, 66
1-qádem: Birinshi xana daǵı belgilerge tiykarlanǵan halda tártiplew
170, 90, 802, 2, 24, 45, 75, 66
2-qádem: Ekinshi xana daǵı belgilerge tiykarlanǵan halda tártiplew
802, 2, 24, 45, 66, 170, 75, 90
Nátiyjede eń úlken san anıqlawshı birinshi bólme sonda da taǵı qalǵan barlıq sanlar ushın ekinshi bólme ústine jumıs atqarıladı. Bunday kompleksler aqırına keliwedi hám nátiyjede ámelge asırılǵan tártip menen juwmaqlawshı dizim payda etinadi.
Bul erda eń kem áhmiyetli nomerden baslanatuǵın radix tártiplew mısalı keltirilgen:
Tártiplenbegen pútkil sanlar dızbekin kórip shıǵıń [170, 45, 75, 90, 802, 2, 24, 66]. Birinshi qádem elementlerdi olardıń ma`nisi boyınsha eń kem zárúrli nomerge, yaǵnıy birlikler nomerine qaray tártiplew bolıp tabıladı. Saralanǵan dizim tómendegishe boladı :
[170, 90, 802, 2, 24, 45, 75, 66]Keyingi, algoritm elementlerdi ma`nisine qaray keyingi eń zárúrli nomerge, yaǵnıy onlıq nomerine saralaydı. Saralanǵan dizim tómendegishe boladı :[802, 2, 24, 45, 66, 170, 75, 90]
Process qalǵan nomerler ushın tákirarlanadı, nátiyjede juwmaqlawshı tártiplengen dizim payda boladı :
[2, 24, 45, 66, 75, 90, 170, 802]
Kórip turǵanıńız siyaqlı, dızbek endi radix sort járdeminde ósiw tártibinde tártiplengen. Radix sortning abzallıqlarınan biri sonda, ol túrli uzınlıqtaǵı pútkil sanlardı saralaw ushın isletiliwi múmkin. Mısal ushın, joqarıdaǵı radix tártiplew mısalında ush nomerge shekem bolǵan pútkil sanlar bar. Radiksli tártiplew ekilik yamasa on altılıq sıyaqlı hár qıylı radikallar menen de isletiliwi múmkin. Ekilik radiksli saralawda saralaw elementlerdiń bıytları tiykarında ámelge asıriladı, on altılıq radiksli saralawda bolsa elementlerdiń on altılıq nomerlerine tiykarlanadı.
Radix Sort bir qansha artıqmashılıqlarǵa iye, bul bolsa onı arnawlı bir jaǵdaylar ushın paydalı tártiplew algoritmına aylantıradı :
1. Ol úlken maǵlıwmatlar jıynaqları ushın nátiyjeli: Radix Sort sızıqlı waqıt quramalılıǵına iye O (d (n+k)), yaǵnıy onıń waqıt quramalılıǵı tek eń úlken sandaǵı nomerler sanına proportsional bolıp tabıladı. saralanatuǵın elementler hám kirisiw nomerleri diapazonı. Bul cifrlardıń úlkenlew maǵlıwmatlar kompleksin saralawda nátiyjeli boladı.
2. Bul turaqlı tártiplew algoritmı : Radix Sort birdey gilt ma`nisine iye bolǵan elementlerdiń rejimin ózgertirmeydi, bul ózgeshelik turaqlılıq dep ataladı. Radix Sort-dıń bul ózgesheligi, ásirese, birdey gilt ma`nisine iye bolǵan elementlerdiń túp rejimin saqlaw zárúrli bolǵan bir neshe maydanlarǵa iye jazıwlar sıyaqlı málim túrdegi maǵlıwmatlardı saralawda paydalı bolıp tabıladı.
3. Radix Sort málim bir baza daǵı nomerlerdi tártiplew ushın isletiliwi múmkin: Radix Sort, ásirese, ekilik, segizlik yamasa on altılıq sıyaqlı málim bir baza daǵı nomerlerdi tártiplashda paydalı bolıp tabıladı. Óytkeni, Radix Sort nomerlerdi nomerleri boyınsha ajratadı, yaǵnıy odan nomerlerdi bir neshe tiykarda tártiplew ushın paydalanıw múmkin.
4. Bul basqa salıstırıwlawǵa tiykarlanǵan saralaw algoritmlarına qaraǵanda tezirek bolıwı múmkin: Nomerlerdi saralawda Radix Sort basqa salıstırıwǵa tiykarlanǵan saralaw algoritmlarına qaraǵanda tezirek bolıwı múmkin, mısalı, operativ saralaw yamasa arnawlı bir jaǵdaylarda birlestiriw. Óytkeni sonda, ol elementler ortasında hesh qanday salıstırıwlawdı óz ishine almaydı, tek elementlerdi nomerlerine qaray esaplaw hám bólistiriwdi óz ishine aladı.
Ulıwma alǵanda, Radix Sort arnawlı bir jaǵdaylar ushın qımbatlı algoritm bolıp tabıladı. Bul, ásirese, cifrlardıń úlken maǵlıwmatlar kompleksin saralawda, nomerlerdi málim bazada tártiplashda, birdey gilt ma`nisine iye bolǵan elementler rejimin saqlawda paydalı bolıp tabıladı hám arnawlı bir jaǵdaylar ushın salıstırıwlawǵa tiykarlanǵan tártiplew algoritmlarına qaraǵanda tezirek bolıwı múmkin.
Radix Saralaw
• Basqa saralaw usıllarınan ayrıqsha bolıp esaplanıw, radix saralaw
giltlerdiń dúzilisin kórip shıǵadı
• Giltler M tayanshda kórsetilgen dep shama menen oylaıń
sanaq sisteması (M = radix), yaǵnıy M = 2 bolsa,
giltler ekilik sistemada ańlatıladı