PLEASE HELP! Sorting, Searching, Indexing...

Greetings all,

I have two weeks to develop an application that will write records (RANDOM ACCESS) and sort them, and display the sorted records by the primary key. I cannot use an ADO.

Please please please... tell me of a book or a link where I can learn how to do this. I need a book with tutorials on sorting algorithms (slection sort, shell sort, etc.) I'm aware of how these sorts work but I'm not able to do them as of yet.

I need to be able to put the files into indexes (obviously for sorting purposes.)

Thank you,
Kmax

http://www.visualbasicforum.com/showthread.php?s=&threadid=47349

Try this thread... it talks about quick sorts, bubble sort.

What sort of algorithm did you have in mind??

http://www.mvps.org/vbnet/index.html?code/sort/qscompare.htm

Try this as well. it is a link to VBNet
It has the quick sort, bubble sort, selection sort, shell sort all compared

I appreciate this, but I need a source to LEARN HOW TO IMPLEMENT my particular project. Surly there is a book somewhere that explains indexing files and sorting/searching them.

I WOULD HAPPILY PAY AN EXPERT from this form in a gift certificate at Amazon.com to teach me what I need to know. You cannot do it for me because I must understand how to make changes..

Name your price or tell me how to get a book. I am desperate and need help now. Time is almost gone.

Kmax

I haven't attempted something like this since the very early 80's,
but I will try to explain what I remember.

With random access files, since you can't easily move records
around, the order of the records in the file becomes an assumned
record number, and hence, a record key/ID. So, when adding a
new record, it goes into the first empty record slot. At first this is
always at the end of the file, but when records are being deleted,
this opens up empty slots within the existing file. Usually, the file
contains a header record that has a place to designate the first
deleted record number and each deleted record contains the
record number of the next deleted record. So when adding a new
record to an empty slot, the pointer to the next deleted record is
copied back to the file header before overwriting it with the new
record. The last deleted record has something in it that indicates
there is no more delete records, and when that gets copied back
to the file header, the add routine knows to put any new records
at the end of the file.

Of course, all this adding and deleting leaves the file in totally
random order (hence the name). The thing that makes it usable
are indexes. Indexes are files that (usually) have two fields, one
the record numbers, and two, the field from the data file being
sorted on. This is kept in sorted order. This means that when a
new record is added or old record deleted to/from the data file,
this index file must be reorganized.

The index file is used with a binary search. The sortfield from the
record in the middle of the file is compared to the value being
looked for. If the search value is greater, the process is repeated
with the half of the index at the end of the file, otherwise it is
repeated with the first half. This process of comparing and then
splitting the remaining records in the index continues until either
a match is found, or the exact position where the new index
record needs to go is found. If the goal is to insert a new record,
all the index records from the found position to the end must be
moved down one and the new one inserted. If the goal is to
delete a record, all the index records from the one after the found
one must be moved back up one, overwritting the deleted one
and deleting the last one in the index file.

All this moving around can become quite slow if there are a lot of
records, which is why this method isn't used in any modern data-
base system. Now indexes are created using B-Trees (balanced
tree). This system breaks the index up into branches and leafs
and allows new records to be added and existing records to be
deleted with a minimum of disk activity. Writing a B-Tree index
is probably way beyond the scope of this project and certainly
there isn't enough time left to do it, but if you are interested in
how something like this can be implemented in VB, I have a
project in the Code Library that has the basics.
http://www.visualbasicforum.com/showthread.php?s=&threadid=31396

I tried doing a google search on isam "indexed sequential access
method" hoping there would be some good pages explaining the
details better, but while there are lots of definitions, and lots of
packages for sale, there isn't much in the way of tutorial. One
basic one is at http://www.twu.ca/rsbook/index.html?http://www.twu.ca/rsbook/Ch14/Ch14.6.html

Thanks Thinker,
I'll start by explaining my exact goals and what I have done thus far. Perhpas then you guys can give me suggestions in the right direction.

I have found no aid from any refference material or my professor. We have no text book :confused: ...

I need to create an application within 1 1/2 hours (VB 6.0, on finals week) that will do the following:

1. Input Name, Age, SSN, Zip though text boxes
2. Take the fields and write it to a random access file (no ado)
3. Sort the random access file using a binary sort with indicies
4. Allow the user to search based on a key in the index
5. I must use the key and position value to read the record from the random file.
6. If there is no particular key value a msg should display that record does not exist.


What he wants is for us to create this application in class under 1 1/2 hours. He informed us that it would be wise of us to write the application and pratice rewiting it under time constrains inorder to pratice for the exam. We are allowed to have a "cheat sheet" of common VB syntax that he will provide with us on test day.

So far I have completed a random access file (speical thanks to jayceepoo & morsnowski) that will:

1. Input name, age, SSN, zip through text boxes
2. write the files to a random access file with a unique record number



Private Sub cmdWrite_Click()
Dim recNum As Integer
Dim ff As Integer
Dim intSSN As Long, udtItemRec As itemStruc
ff = FreeFile
'intSSN = Val(txtSSN.Text)
udtItemRec.strName = txtName.Text
udtItemRec.intSSN = txtSSN.Text
udtItemRec.intAge = txtAge.Text
udtItemRec.intZip = txtZip.Text
Open "C:\painInMyAss.txt" _
For Random As #ff Len = Len(udtItemRec)
recNum = LOF(ff) / Len(udtItemRec) + 1
Put #ff, recNum, udtItemRec
Close #ff

End Sub




in the module:


Option Explicit

Type itemStruc
strName As String * 7
intSSN As Long
intAge As Integer
intZip As Long
End Type



What I need is a book explaining how to index and sort a freakin random access file. Everything I find is using a database through an ADO. I'm in the greatest need I can ever recall being in, specifically:

How do I index this file that is created?
Once indexed, how do I employ a Binary search? - selection sort? shell sort? - bubble sort...

Then I can start thinking about displaying the record.

THANK YOU ALL SO MUCH FOR ANY AND ALL ASSTENACE. This is finals week and I've got 6 exams non more important than this. I really appreciate anyones help.

One question. Does the index need to be in a separate file, or
can it just be in memory? If in memory, then it will just be a
matter of using an array, and having routines to insert and delete
elements from the array. The main routine will be a binary search
of the array. A good example of doing a binary search can be
seen here... http://www.visualbasicforum.com/showthread.php?s=&threadid=20603
Yes, it is working with a recordset, but there is no difference
between using Rs!SEARCHFIELD and searchindex(0). It will easily
port over to searching an array. I already explained the theory
of a binary search above, and there is another one in that other
thread. The theory is very simple. You keep narrowing down the
part of the index you are searching by dividing it in half. You can
only divide something in half so many times before you get to 1
(n times where number of items <= 2^n). The only requirement is
that the list of elements being searched must already be in sorted
order. This happens as you add and remove records. By using
the same binary search, you can find where an item would go
even if it isn't already in the index. Then you have to make room
for it by moving all the other items down one. This always keeps
the index in sorted order. To delete, move all the items after the
one being deleted back up slot. There is no need for sorting
routines this way. The index is always already sorted, and the
binary search always finds the closest match.

The index need does not need to be in a separate file; it can just be in memory. In fact, I believe this is how it is expected to be. There must be a book somewhere about how to employ something like this...

I'll study that post, but I fear that without resources availing me, I won't understand the code. But I shall fight until the end. Thanks..

A few questions based on current program...


1. Input Name, Age, SSN, Zip though text boxes - Done
2. Take the fields and write it to a random access file (no ado) - Done

Working on step three has me a little confused. I'm under the impression that the binary sort only works after the file has been indexed. Is this correct? And if it is, do I achieve this result using a sort such as a selection or incersion like:


' insert sort

Public Sub InsertSort(ByRef A() As Variant, ByVal Lb As Long, ByVal Ub As Long)
Dim t As Variant
Dim i As Long
Dim j As Long

' sort A[Lb..Ub]
For i = Lb + 1 To Ub
t = A(i)

' shift elements down until insertion point found
For j = i - 1 To Lb Step -1
If A(j) <= t Then Exit For
A(j + 1) = A(j)
Next j

' insert
A(j + 1) = t
Next i
End Sub



I realize this code needs to be changed to address my current project, but I just wondering if I'm on the right track.

3. Sort the random access file using a binary sort with indicies

Thank you

I don't know how to explain it any farther by describing the
concepts. I have no idea how you could have taken a number of
computer classes and not learned the concept of a binary search.
Anyway, I did this example showing how to build a key index in
memory using arrays. I will try to answer specific questions about
the code, but in general, if you can't figure out what is going on
here, you really shouldn't be passing your course anyway.

I have a question about the code that Thinker posted. In this part:
' First get number of elements between first and last
HalfPos = LastElem = FirstElem - 1
should the second "=" be "-" or am I missing something? It works as it is, but it doesn't seem to be working like the comments say it does, because the quoted line will always return 0 for HalfPos.

Oops! Yeah, it should be -. I was typing fast. I wonder why it is
working anyway? ;)

Went ahead and corrected it. It really doesn't seem to make any
difference but I don't have time to figure out why.

Get this attachment.

To finish this and because I do have time today:

It worked anyway because this line
HalfPos = (HalfPos + (HalfPos And 1)) \ 2 + FirstElem
makes HalfPos equal to FirstElem and in the code that follows
Select Case True
Case Key > IndexKeys(HalfPos)
FirstElem = HalfPos + 1 'In last half
Case Key < IndexKeys(HalfPos)
LastElem = HalfPos 'In first half
Case Else
Found = True
FindKeyPos = HalfPos 'Found key so stop!
Exit Function
End Select

you move FirstElem up by 1. It will only take longer because the second Case will only be true when the right key position is reached (so you check all positions that are lower than the correct one instead of halving the possiblities with each loop run).

Yeah, you're probably right "if you [I] can't figure out what is going on here, you [I] really shouldn't be passing your [my] course anyway"

Thanks for the time spent on a loss cause and the encouragement. No offense meant… I agree, how could I have had all the CS courses…


Later,

I should be more encouraging but if things in this class are as
bad as you describe (no textbooks, the teacher didn't teach this
material), I would seriously consider trying to get my tuition back.

Anyway, if you do understand the code, then you should still be
able to do it as I typed this sample in while trying to create it and
it took me an hour. It does sound more like a typing test than
a coding one.

Deadalus, thanks for catching the bug and figuring out why it still
worked. :)

Thanks Thinker,
This is required for my major I'm afraid. There is fight in me yet! However, I need to obtain a knowledge base ample enough to ask appropriate questions in this group. I'm not capable of deciphering your answers, so I will look else ware and return when I feel as though I have appropriate knowledge. The professor said he's pushing the test back to the last day of finals because no one (except Tom - freaking genius) is ready. I've got till Dec 6th now and I will be ready.

Thanks,

Originally posted by Kmax
However, I need to obtain a knowledge base ample enough to ask appropriate questions in this group. I'm not capable of deciphering your answers, so I will look else ware and return when I feel as though I have appropriate knowledge.
The problem isn't simply that you don't have enough knowledge, but only that you have asked such a broad question compared to your current skill level, that to answer it in detailed steps would take longer than any of us have to devote to it (especially as you yourself have a time limit). Perhaps it will help if you post more code as you progress, and ask questions about specific areas as you encounter problems.

Also, in Tutor's Corner there is a thread listing VB resources that you might find helpful.

Kmax, have you ever worked with the VB debugger? If you were
to put a breakpoint on the start of any of the subs/functions in
my sample, then start running the code, and try adding and
deleting keys, you could then single step through the function,
inspecting variable values along the way and just seeing how it
works. I have used this method many times to help me decipher
some code I can't understand.

I've got a much stronger sense of a how to perform a binary search. I'll be working on that soon (I hope). Thanks again Thinking for all your work in that example. I really appreciate it. Right now, I could use a strong shove in the right direction on how to sort this file.

Here is what I've got.

code Modules:


Option Explicit

Type itemStruc
strName As String * 50
intSSN As String * 20
intAge As String * 20
intZip As String * 45
End Type

Type newStruc
strSSN As String * 12
pointer As String
End Type



Writing to the File - a little different then before


Dim udtItemRec As itemStruc ' declaring my item Struc
Dim ff As Integer, recNum As Integer ' these will be used to keep the file number
udtItemRec.strName = txtName.Text
udtItemRec.intSSN = txtSSN.Text
udtItemRec.intAge = txtAge.Text
udtItemRec.intZip = txtZip.Text
ff = FreeFile
Open "C:\randomAccess.txt" _
For Random As #ff Len = Len(udtItemRec)
recNum = LOF(ff) / Len(udtItemRec) + 1
Put #ff, recNum, udtItemRec
Close #ff


And displaying my file in a label (better way?)



Private Sub cmdDisplay_Click()
Dim udtItemRec As itemStruc
Dim DArray(1 To 20) As itemStruc
Dim intfilepos As Integer
Dim sortArray(1 To 20) As newStruc
Dim I As Integer
Dim ff As Integer

ff = FreeFile
intfilepos = 1

Open "C:\randomAccess.txt" _
For Random As #ff Len = Len(udtItemRec)

For I = 1 To 20
Get #ff, I, udtItemRec
DArray(I).strName = udtItemRec.strName
DArray(I).intSSN = udtItemRec.intSSN
DArray(I).intAge = udtItemRec.intAge
DArray(I).intZip = udtItemRec.intZip

sortArray(I).strSSN = udtItemRec.intSSN
sortArray(I).pointer = I

lblResults.Caption = lblResults.Caption & _
DArray(I).strName & _
DArray(I).intSSN & _
DArray(I).intAge & _
DArray(I).intZip

I = I + 1
Next I


End Sub



Now here in the problem.. I'm trying to use my sort button. Here is my code:


Private Sub cmdSort_Click()
Dim smallVal As newStruc
Dim swapEm As newStruc
Dim As Integer
Dim I As Integer
Dim mxb As String

For I = 1 To 19
= I
smallVal.strSSN = sortArray(I).intSSN
For j = I + 1 To 20
If sortArray(j).intSSN < smallVal.intSSN Then
smallVal.intSSN = sortArray(j).intSSN
= j
End If
Next j
swapEm = sortArray(I)
sortArray(I) = sortArray( )
sortArray(post) = swanEm

Next I
For I = 1 To 20
mbx = mbx & sortArray(I).intSSN & sortArray(I).pointer
Next I

MsgBox mxb

End Sub


It does not recognize sortArray which makes sense because it's not declared in the module. How do I appropriately get these files sorted? Also, I'm pretty shaky on this program, so I appreciate any advice to just simply make it better would also be very welcomed.

But SPECIFICALLY, why isn’t my sort code working?

Thank you

I took some of your code, and merged it into the example above.
I added labels and textboxes, and showed how it could be done.
But there is no routine for sorting. The point of indexes is that
you shouldn't need to sort the data - the index keeps track of the
records sorted by whatever is the key. I used the SSN as the key
because it looks like that is what you were trying to do. It keeps
all records in memory until you save the data. I know it isn't
exactly what you need but it shows all the principles, and you
really need to figure it out and understand what is happening.

Observations:

(1. I've got tons to learn

(2. You can declare record structures(type) without a module? Why was I taught to use a module?

(3. I suspect you're separating everything into privet functions to keep homogenous code?

(4. A lot of your commands are new to me but I can decipher most of their meanings.. like:


Open App.Path & "\randomAccess.txt"


I'm trying to sort the records so I can display them in a particular order in a label caption. I was trying to sort them by their relative position in the index. In my sort code on pg.1 I’m attempting to pump the index through an array to sort the array positions and display the records in indexed position.

You really helped me by showing me how to do a binary search on these records. Actually, while knowing this code is a level above my abilities, I feel like I understand it for the most part. This also takes the pressure off; I’m going to start practicing writing this code under time constraints as soon as I get all the records displayed in a label or listbox..

My display button right now:


…
Open "C:\randomAccess.txt" _
For Random As #ff Len = Len(udtItemRec)

For I = 1 To 20
Get #ff, I, udtItemRec
DArray(I).strName = udtItemRec.strName
DArray(I).intSSN = udtItemRec.intSSN
DArray(I).intAge = udtItemRec.intAge
DArray(I).intZip = udtItemRec.intZip

sortArray(I).strSSN = udtItemRec.intSSN
sortArray(I).pointer = I

lblResults.Caption = lblResults.Caption & _
DArray(I).strName & _
DArray(I).intSSN & _
DArray(I).intAge & _
DArray(I).intZip

I = I + 1
Next I


This displays all the files in the randomAccess.txt. But not sorted. That’s what I was asking about in my original post. The fact that the binary search is working makes me incredibly happy, but I’m still stuck on how to display the “sorted by index number” records in a label. Any suggestions would be appreciated from my sort code in page 1.

With my example, all you have to do is loop though the index
records in IndexKeys...

For I = 1 To UBound(IndexKeys,1)
With DArray(IndexKeys(I).Pointer)
lblResults.Caption = .strName & " " & _
.intSSN & " " & _
.intAge & " " & _
.intZip
End With
Next I

But I don't get the point of this method of display. The records
will just fly by on the screen.

The code was just displaying the last entry so I adjusted it this part:


lblResults.Caption = lblResults.Caption & .strName & " " & _
.intSSN & " " & _
.intAge & " " & _
.intZip

Probably not the best way to fix it, but it works now.

Thinker,
I know saying, "Ignorance is the mother of admiration", but I am truly grateful for your help these past few days. I've learned so much. People say that when you first start out on something, like a new language or program, you tend to copy everyone’s style as I'm copying your style now. But as that artist develops he/she takes what is best in his/her opinion and eventually develops his/her own style. I will continue to develop as a programmer and if I become half the contributor you are, I will be delighted.

Thank you for taking the time to teach,