Studying Sorting Algorithms.
Why Sorting is Important
Financially, the most im[portant aspect of computing is the use of databases. In its simplest incarnation a datbase is a collection of 'records', and a record is a collectiopn of data
about something in a more or less fixed format. So companies have records containing your details as a customer. Your record, at a hospital might contain your name, healthcare number,
family doctor, address, phone number, date of birth, as well to links to files containing your treatments and medical information. As you know finding things by binary searching is
efficient and by sequential search is innefficient. So if the records are sorted by healthcare number we can quickly find your record if you know your health care number. But what if we only know your
name and phone number? Ther solution is to maintain 'keys'. Keys are sets of records that contain only two fields of data. A key record of phone numbers would contain just a phone number and the location
of the (main patient) record that goes with it. So if you sort the phone keys and you want to know who has a phone number 987-65432 you can then do a binary search of the key which will show you where to look for the full
patient record.
Sort Animations: Parts of Lab experience 4
- Go to p27 in the lab manual and using the sort animator do the following.
- Selection sort. Do 4.1, 4.2 4.3 4.4
- We will talk about bubble Sort then do 4.5, 4.6 4.7, 4.8.
- We will briefly talk about how quicksort works (p28) but not do the analysis. Instead:
- Go into the sort timer. I want you to time each of the Sort algorithms for 16,32,64 and 128 points.
- Make a table of the results and plot on squared paper
- For each Sorting method answer the question: doubling the number of points causes the sorting time to increase by a factor of roughly .....
- Go to lab experience 5 and do 5:10 (binary Search).
- Finally I am hoping to give you each the chance to wire up a logic gate and determine its truth table.
Home Page of RDScience