 |
Алгоритм сортировки записей исходного файла
|
|
|
|
Задача сортировки файла формулируется следующим образом. Имеется файл, состоящий из последовательности записей. Одно из полей в составе каждой записи является полем ключа. Файл целиком размещается во внутренней памяти. Требуется вывести файл на внешний носитель так, чтобы записи располагались в заданном порядке следования ключей.
Из возможного множества алгоритмов сортировки файлов более эффективными будут те, которые требуют меньше перестановок записей. В работе рассматривается такой алгоритм, который вообще не требует ни одной перестановки: после подготовительных процедур записи выводятся в файл в заданном порядке следования ключей.
Данное, которое находится в составе записи и значения, которого должны учитываться при сортировке, называется ключом.
Для сортировки записей по заданному ключевому полю удобнее использовать ЗАПИСИ:
1. Первые две строки файла – заголовок и «Шапка» в сортировке не участвуют.
2. Третья и последующие строки преобразуются в ЗАПИСИ типа param:
Type param
prop As String
vol(7) As Single
End Type
Например:
| ЗАПИСЬ: | Par.prop | Par.vol(0) | Par.vol(1) | Par.vol(2) | Par.vol(3) |
| Строка: | Аммиак NH3 | 15,0 | 28,0 | 15 | 79 |
Разделителем при преобразовании в ЗАПИСЬ является знак горизонтальной табуляции (HT)
Например:
Аммиак NH3HT15,0HT28,0HT15HT79
Подпрограмма разделения строк исходного файла на поля:
Sub seps(str As String, par As param, howpar As Integer)
Dim p As Integer, q As Integer, r As Integer
Dim dlina As Integer
Dim sp As String, smb As String
Dim HT As String * 1
HT = Chr(9)
dlina = Len(str)
If dlina = 0 Then
Exit Sub
End If
r = InStr(str, HT)
par.prop = Left(str, r - 1)
sp = Right(str, dlina - r) & HT
dlina = dlina - r + 1
p = 1: q = 0
Do While p < dlina
r = InStr(p, sp, HT)
smb = Mid(sp, p, r - p)
If smb = "-" Then
par.vol(q) = 0
Else:
par.vol(q) = CSng(smb)
End If
q = q + 1
p = r + 1
Loop
howpar = q
End Sub
|
|
|
Алгоритм сортировки
Решение задачи сортировки файла разбивается на два этапа.
На первом этапе создаётся вспомогательный вектор. На втором этапе формируется выходной файл: первой выводится запись, номер которой 0 затем выводится запись, номер которой 1 и т. д.
Первый этап. Описание алгоритма формирования вспомогательного вектора.
Исходные данные: volVector - массив записей, в составе каждой записи имеется поле ключа Vol(1). В массиве volVector содержится N элементов. доступ к ключу j-ого элемента обозначается так: volVector(j).Vol(1). Тип данного Vol(1) допускает сравнение на равно, больше и меньше. В результате выполнения алгоритма, определяются значения элементов вспомогательного вектора intMesto. В алгоритме используется вспомогательный логический вектор размером N. flag(j)=True обозначает, что элемент volVector(j) доступен для просмотра, но, если flag(j)=False, то элемент volVector(j) исключается из просмотра. В исходном состоянии все элементы вектора flag устанавливаются в значение True. Вспомогательная переменная voltemp хранит текущее минимальное значение Vol(1). Константа voltemp имеет тот же тип, что и ключ Vol(1), значение voltemp заведомо больше любого ключа Vol(1).
1. Для каждого i от 0 до N выполнять шаги 1....5. (Индекс i определяет место записи в выходном файле.)
2. Установить voltemp равным 99999 и перейти к шагу 3.
3. Для каждого j от 0 до N выполнять шаг 4. (В этом цикле отыскивается претендент на место i.)
4. Если flag(j)=True и volVector(j).Vol(1)<=voltemp, выполнить voltemp ← volVector(j).Vol(1); kl←j. (Если элемент volVector(j) доступен и его ключ volVector(j).Vol(1) меньше, чем текущий минимум voltemp, то заменить значение текущего минимума и запомнить его место. Доступность элемента volVector(j) определяется значением True элемента flag(j).
5. Выполнить intMesto(i)←kl; flag(kl)←False. (Минимальное значение из множества доступных ключей найдено в записи с индексом kl. Значение kl записывается в intMesto(i), kl-ый элемент вектора volVector помечается как недоступный, исключается из дальнейших действий.)
|
|
|
Второй этап сортировки файла - вывод в рабочий лист Excel и запись в файл на диске.
(mas-массив исходных записей, mm-вспомогательный массив, sk-массив исходных строк)
For q = 0 To h
Cells(q + 3, 1) = mas(mm(q)).prop
For i = 0 To hp - 1
Cells(q + 3, i + 2) = mas(mm(q)).vol(i)
Next i
Print #nf2, sk(mm(q) + 2)
Next q
Подпрограмма первого этапа сортировки (создание вспомогательного массива intMesto):
Sub sort(volVector() As param, intMesto() As Integer, h As Integer)
Dim i As Integer, j As Integer, kl As Integer
Dim highIndex As Integer, lj As Integer
Dim voltemp As Single
Dim flag() As Boolean
h = UBound(volVector)
ReDim intMesto(h)
highIndex = UBound(volVector)
ReDim flag(highIndex)
For i = 0 To highIndex
flag(i) = True
Next i
For i = 0 To highIndex
voltemp = 99999
For j = 0 To highIndex
If flag(j) Then
If volVector(j).vol(1) <= voltemp Then
'если volvector(j) будет меньше или равно voltemp
'то значение текущего минимума voltemp, будет
'заменено на элемент volvector(j)
voltemp = volVector(j).vol(1)
kl = j
End If
End If
Next j
intMesto(i) = kl
flag(kl) = False
Next i
End Sub
Подпрограмма второго этапа сортировки - вывод результата в рабочий лист Excel и запись в файл на диске:
Sub OutputData(name As String, sk() As String, mm() As Integer, h As Integer, hp As Integer, nf2 As Integer, str As String, mas() As param)
Dim i As Integer, q As Integer
Open name For Output As nf2
Print #nf2, sk(0)
Print #nf2, sk(1)
Cells(1, 1) = sk(0)
For i = 0 To hp
Cells(2, i + 1) = str(i)
Next i
For q = 0 To h
Cells(q + 3, 1) = mas(mm(q)).prop
For i = 0 To hp - 1
Cells(q + 3, i + 2) = mas(mm(q)).vol(i)
Next i
Print #nf2, sk(mm(q) + 2)
Next q
Close #nf2
End Sub
|
|
|
