 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Then begin
|
Читайте также: |
e1:=M[i];
M[i]:=M[i+1];
M[i+1]:=e1;
flag:=true;
end;
end;
end;
Сортування із застосуванням індексів на базі методу «Бульбашка»
Сортування великих обсягів інформації потребує більших витрат машинного часу і ресурсів. Ефективніше індексування інформації. Індексування, як і сортування, забезпечує можливість доступу до елементів у порядку зростання або спадання, але, на відміну від сортування, не змінює фізичний порядок проходження елементів. У результаті індексування створюється додатковий масив, що служить довідником для роботи з вихідним масивом. Той самий масив може бути проіндексований за різними ознаками (ключами або зчепленими ключами), що дозволяє мати в розпорядженні кілька індексних масивів, що забезпечують гнучку роботу з основним. Індексне сортування широко використовується у роботі з базами даних. Наведемо приклад алгоритму індексного сортування за спаданням.
| АЛГ Індексне сортування (ціл N, дійсн таб A[1:N], ціл таб D[1:N]) АРГ N, A РЕЗD ПОЧ ціл і, j, i1, j1 дляі від1 до N пц D[i]:=i кц для і від N до 2 крок – 1 пц для j від 1 до і – 1 пц i1:=D[j]; i2:=D[j+1] якщо A[i1]<A[i2] то D[j]:=i2; D[j+1]=i1 все кц кц для і від 1 до N пц ДРУКУВАТИ A[D[i]] кц КІН | Мовою Паскаль процедура індексного сортування виглядає так: const n=300; var arr=array[1..n] of real; arr1=array[1..n] of word; Procedure Sort (A:arr; var index:arr1); var i, j:word; L:word; begin for i:=1 to n do index[i]:=i; for i:=N downto 2 do for j:=1 toi – 1 ifA[index[j]<A[index[j+1] then begin L:=index[j]; index[j]:=index[j+1]; index[j+1]:=L; end; end; |
У результаті роботи алгоритму створюється індексний масив D[1:N]. За його допомогою здійснюється робота з вихідним масивом A[1:N] як з упорядкованим за спаданням. Якщо ж в алгоритмі у команді «якщо» змінити знак порівняння на «>», то отриманий індексний масив дозволить працювати з вихідним масивом A[1:N] як з упорядкованим за зростанням.
Розглянемо цей спосіб на конкретному прикладі.
Хай є масив А, і його необхідно впорядкувати за спаданням:
Масив А
На основі масиву А формується індексний масив D, і при цьому організовуються два цикли:
1)перший цикл указує на те, скільки елементів масиву необхідно розглянути у внутрішньому циклі; розгляд елементів завжди починається з першого;
2)другий цикл виконує порівняння елементів масиву А на основі індексного масиву D, і при цьому здійснюється уточнення таблиці D.
Формування індексного масиву наведено в табл. 3.
Таблиця 3
Індексний масив D
| до сортування | ||||||
| 1-й прохід | ||||||
| 2-й прохід | ||||||
| 3-й прохід | ||||||
| 4-й прохід |
Поиск по сайту: