Wyo VB - Ch. 10 Notes

Objective #1: Use two-dimensional arrays

• ???

Objective #2: Understand and use the simple exchange sort.

• Sorting means to put data in order. The data could be text, which is usually placed into alphabetical order. Or, the data could be numbers which are usually placed into numerical order. Data can be sorted in an ascending or a descending order.
• Programmers use different sorting algorithms depending on the nature of the data that needs to be sorted. Some sorting algorithms work quickly for some sets of data but slowly for others. You must choose an algorithm carefully so that you pick one that is fast and efficient.
• The simple exchange sort is just that, simple. It is the slowest sorting algorithm, especially for large amounts of data.
• In a simple exchange sort, the first item is compared to the second. If they are out of order, they are swapped. Next, the first item is compared to the next item and swapped if necessary. Only after the first item has been compared with every item in the list is the second item compared to the next item after it. The process can be coded by using 2 nested For/Next loops with an If/Then statement inside them.
• Probably the only advantage to a simple exchange sort is that it is easy to program. However, if you only have a hundred items or so, then you may not notice that this type of sort takes any longer than more efficient sorting algorithms due to the speed of modern computers.
• The code below is an example of the often used "swap" routine that is used in most sorting algorithms:

  intTemp = A(intFront)
  A(intFront) = A(intBack)
  A(intBack) = intTemp

• One reason why the simple exchange sort is not efficient is that if the list is already sorted, it still compares each value to every other value taking a lot of time to do nothing!
• A selection sort is similar and only slightly faster than a simple exchange sort.

Objective #3: Understand and use the bubble sort.

• The bubble sort distinguishes itself from the simple exchange sort primarily because it notices when no individual swaps have occurred during a sweep of the list and stops sorting at that point. It uses a Boolean variable with a True or False value to indicate whether any swaps have been made on the current sweep of the list.   Also, the bubble sort compares adjacent items, swapping if necessary. It does not stick with the first element in the list to compare with the rest of the items. Instead of using For/Next loops like a simple exchange sort, the bubble sort uses a For/Next loop nested inside of a Do loop. The control expression of the Do loop is determined by the Boolean value and therefore can exit earlier than the outer loop in a simple exchange sort, saving time.
• In some cases, the bubble sort is not any faster than the simple exchange sort though. If the data is totally out of order, this sort will have to make the maximum number of comparisons and therefore work very slowly.
• Usually, though the bubble sort is quicker and more efficient than the simple exchange sort.

Objective #4: Understand and use the Shell sort.

• The Shell sort (aka comb sort) is more efficient than either the simple exchange sort and the bubble sort. It was only discovered and published in 1991 (Byte magazine) by D.L. Shell. Instead of comparing adjacent items like a bubble sort, it compares elements that are separated by a certain gap. Again a Do loop is used but the gap shrinks by a certain factor with each pass through the Do loop. Otherwise, elements are compared and swapped as they are in the bubble sort. It has been shown that by shrinking the gap on each pass of the loop by a factor of 1.3 will make the comb sort as efficient as possible! The gap is initially set to the number of items to be sorted divided by 1.3.

Objective #5: Use the LoadPicture function when necessary.

• The LoadPicture function can be used to load a graphic into a PictureBox or Image control during runtime.

Objective #6: Understand and use the sequential search algorithm (aka linear search).

• In computer science, algorithms that search for specific pieces of data within large sets are as important as sorting algorithms. There are different types of searches and some are more efficient and quicker than others.
• The easiest type of search to code is the sequential search. It is probably the slowest though. In a sequential search, you use an If/Then statement within a loop that compares the search item with every item in the list from the first to the last. Unfortunately, if the item that you are searching for happens to be located at the end of the list, this search takes a long time.
• One advantage of a sequential search is that it can be used on data that is unsorted. Some other search algorithms require that the data be sorted which takes time itself.
• On average, a sequential search must examine half of the elements in the list to find the search item.

Objective #7: Understand and use the binary search algorithm.

• The binary search is much more efficient than the sequential search. On average, this algorithm makes many times fewer comparisons to find the search item than the linear search.
• A disadvantage of a binary search is that the data must first be sorted.
• A binary search is performed by first checking the element in the middle of the sorted list. If that item happens to be the search item then the search is over. Otherwise, you discard half of the list depending on whether the middle item is less than or greater than the search item. Then you compare the search item to the middle item of the remaining half of the list and continue the same process.