Visual Basic 2008 Programming: Business Applications with a Design Perspective
Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9
Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Appendix A Appendix B Appendix C Home
Loading
Last change: February 13 2016 18:48:19.

 Chapter in PDF

Table of Contents

Appendix C: Sorting and Searching
Last change: February 13 2016 18:48:22.
<<PreviousNext>>

C.2 Straight Insertion Sort

Imagine that in the sorting process, an additional array is used for output purposes. Each element from the original (input) array is placed into the output array in sorted order. When all elements from the original array are moved to the output area, the sorting is complete. To ensure that a new element from the input array is placed in the output array in sorted order, it is compared with the elements already in the output array to determine its proper position. After this position is identified, this new element is inserted in that position. This algorithm can be illustrated as follows.
The first element is moved into the output area.
Position                       1          2          3          4          5
Input (Original)         38        51        23        56        34
Output                        38
The second element, 51, will then be moved to the output area. It is first compared with the existing element in output, 38. Because 51 is greater, it is placed at the end of the output area, resulting in the following:
Position                       1          2          3          4          5
Input (Original)         38        51        23        56        34
Output                        38        51
The third element will now be moved. When it is compared with the elements in the output area, you find that it should be inserted at position 1. The result will appear as follows:
Position                       1          2          3          4          5
Input (Original)         38        51        23        56        34
Output                        23        38        51
where 23 is inserted at position 1.
This process continues until all elements in the original array are moved into the output area.

In actual implementation, there is no need to set aside another array for output purposes. Recall that the number of output elements is equal to the number of elements already moved from the input array. Because all the elements in the output area are also the same as those already moved from the input array, the area in the input array can be used to hold the output.
The algorithm involves two major activities when an element is moved from the input area to output: determining the proper position of the new element and inserting the new element in its proper position. You can write a function (for example, FindPos) to find the proper position for the new element and a Sub procedure to perform the insertion.
The FindPos function will search the output area sequentially until the new element is less than the element in the output or the output area is exhausted. Either of these conditions identifies the new element’s proper position. For example, if the output area has 38 and 51, and the new element is 23, the function should return the first position, as shown next:

Function FindPos(ByVal X() As Integer, ByVal V As Integer, ByVal L As Integer) As Integer ' This function searches and returns the proper position ' for a value V in an array whose elements in the range of its ' lower bound and (L – 1)th position are sorted (L is imagined ' to be the extra position to accommodate an additional element ' to be inserted) Dim I As Integer For I = 0 To L - 1 If V < X(I) Then Return(I) End If Next I Return (L) End Function

Last change: February 13 2016 18:48:23.
  1. Comparing and Swapping
  2. The Number of Elements to Compare
  3. The Number of Rounds of Comparisons
  4. Computing the Number of Comparisons for Each Round
  5. The Bubble Sort Sub Procedure
  6. Testing the Procedure
  7. Expected Behavior of the Testing Project
  8. Declaring the Array
  9. Generating the Random Numbers
  10. Calling the Sorting Sub and Displaying the Results
  11. Computing Time Used
  12. A Remark on Sorting Efficiency
  13. Simple Selection Sort
  • C.2 Straight Insertion Sort
    1. The Insert Sub Procedure
    2. The Insertion Sort Procedure
    3. Insertion Sort Versus Bubble Sort
    4. Testing Insertion Sort
    5. Binary Insertion Sort
    6. <<PreviousNext>>