Деректерді реттеу әдістерін зерделеу және сипаттау Реттеу алгоритмдерінің бағдарламалық құралдарын талдау
жүктеу/скачать 0,51 Mb.
|
| Жылдам реттеу. Жылдам реттеу әдісін Ч.Ф.Р.Хоаром ойлап тапқан және ол оған осы атауды берген болатын. Қазіргі кезде реттеудің бұл әдісі ең жақсы деп саналады. Ол реттеудің алмастыру әдісін қолдануға негізделген. Егер алмастырып реттеудің қарапайым нұсқасын көрсететін көпіршік әдісімен реттеудің жылдамдығы өте аз екендігін ескеретін болсақ, бұл тіпті таңқаларлық нәрсе.
Жылдам реттеу негізінде бөлшектеу принципі жатыр. Алдымен "негіз" ретіндегі бір мән таңдап алынады және содан кейін бүкіл массив екі бөлікке бөлінеді. Бір бөлігін барлық "негіз" –ден үлкен немесе тең элементтер құрайды, ал екінші бөлігін бөлшектеу бойынша барлық кіші элементтер құрайды. Бұл процесс қалған бөліктер үшін бүкіл массив реттелгенге шейін жалғасады. Мысалы, жылдам реттеуді орындау кезінде "fedacb" массиві үшін "d" бөлу мәні ретінде қолдану кезінде келесі айналымдар алынатын болады: Бастапқы күйі: f e d a c b; Бірінші айналым: b c a d e f; Екінші айналым: a b c d e f. Бұл процесс әрбір "abc" және "def" бөліктері үшін жалғасады. Бұл процесс рекурсивті жаратылысқа ие. Және шынында да, көптеген жылдам реттеулер рекурсивті алгоритм көмегімен іске асырылады. Бөлу мәнін таңдауды екі тәсілмен жасауға болады. Бұл мәнді кездейсоқ түрде таңдауға болады немесе массивтен таңдап алынған мәннің үлкен санын орташалау жолымен алуға болады. Үйлесімді реттеу үшін барлық элементтердің тура ортасында орналасқан мәнді таңдау талап етіледі. Бірақ, көптеген деректер жынтығы үшін бұны жасау оңайға түспейді. Дегенмен, нашар жағдайда болса да, егер экстремальді мәндердің бірі таңдап алынса жылдам реттеу айтарлықтай жақсы жұмыс істейді. Жылдам реттеудің төменде келтірілген алгоритмінде бөлу мәні ретінде орта мән қолданылады. Мұндай тәсіл үнемі ең жақсы бола бермесе де, ол айтарлықтай қарапайым және дұрыс орындалатын болады. { жылдам реттеу } procedure QuickSort(var item: DataArray; count:integer); procedure qs(l, r: integer; var it: DataArray); var
i, j: integer; x, y: DataItem; begin i:=l; j:=r; x:=it[(l+r) div 2]; repeat
while it[i] if y<=j then begin
y := it[i]; it[i] := it[j]; it[j] := y; i := i+1; j := j-1; end; until i>j; if l if l end;
begin
Бұл мысалы, жылдам реттеу әдісімен жүздеген элементті реттеу кезінде орта есеппен 100*2, яғни 200 салыстыру операциясы талап етілетіндігін білдіреді, сондай -ақ log 100 2 –ге тең болады. Бұл мән көпіршік әдісімен реттеу үшін 990 мәнімен салыстырғанда өте жақсы болып табылады. Дегенмен, жылдам реттеудің бір жағымсыз жағы болуы тиіс. Егер бөлу үшін таңдап алынған мән үлкен (максимал) мәнмен сәйкес келетін болса, онда жылдам реттеу n орындау уақытымен ең баяу әдіске айналады. Бірақ, іс жүзінде бұл жағдай кездеспейді. Бөлу мәнін анықтау әдісін мұқият таңдау қажет. Бұл мән реттелетін нақты берілгендер бойынша анықталады. Пошталық жіберулердің үлкен тізімі үшін, реттеу пошталық индекстер коды бойынша жасалады, бөлуге арналған мәнді таңдау қиын емес, пошталық индекстердің кодтары айтарлықтай біркелкі бөлінген және талап етілген мәнді қарапайым алгебралық процедура көмегімен анықтауға болады. Бірақ, анықталған деректер базасы өте жақын мәні бар реттеудің кілтін иеленген болуы мүмкін және сондықтан ең жақсы әдіс үнемі мәнді кездейсоқ таңдау болып табылады. Әйгілі және айтарлықтай тиімді әдіс сәйкес аймақтардан үш элементті таңдаумен аяқталады және олардың орташа мәнін есептеу керек. жүктеу/скачать 0,51 Mb. Достарыңызбен бөлісу:
|