Summary Programming Logic and Design Ch 8

Chapter 8
Explain the need for storing data
 Sequential order
 Placed in order based on the value of some field
 Alphabetical or numerical
 Ascending order (arranging records from A to Z or lowest to highest)
 Descending order (arranging records from Z to A or highest to lowest)
 The median value in a list is the value of the middle item when the values are listed in order
 not the same as the arithmetic average, or mean

 When computers sort data
 Always use numeric values when making comparisons between values
 Letters are translated into numbers using coding schemes such as ASCII, Unicode, or
EBCDIC
 “B” is numerically one greater than “A”
 “y” is numerically one less than “z”
 Whether “A” is represented by a number that is greater or smaller than the number
representing “a” depends on your system
 Professional programmers might never have to write a program that sorts data
 Organizations can purchase prewritten sorting programs
 Many popular language compilers come with built-in methods that can sort data for you
 Beneficial to understand the sorting process


Describe the bubble sort algorithm
 An algorithm is a list of instructions that accomplish a task, such as a sort
 Bubble sort
 Items in a list are compared with each other in pairs
 Items are then swapped based on which is larger or smaller
 Sometimes called a sinking sort
 Ascending sorts put the smaller item on top, so the largest item sinks to the bottom
 Descending sorts put the larger item on top, so the smallest item sinks to the bottom
 An algorithm contains instructions for swapping values
 To swap values stored in two variables:
 Exchange their values
 Set the first variable equal to the value of the second
 Set the second variable equal to the value of the first
 There is a trick to swapping any two values
 Example
 num score1 = 90
 num score2 = 85
 This is what could go wrong

,  If you first assign score1 to score2 using a statement such as score2 = score1
 Both score1 and score2 hold 90, and the value 85 is lost
 Must create a temporary variable to hold one of the scores
 temp = score2 (temp and score2 both contain 85)
 score2 = score1 (score2 contains 90)
 score1 = temp (score1 contains 85)


 Nested loops
 Inner loop swaps out-of-order pairs
 Outer loop goes through the list multiple times
 General rules
 Greatest number of pair comparisons is one less than the number of elements in the array
 Number of times you need to process the list of values is one less than the number of
elements in the array


Sort records on multiple field values
 Might not know how many array elements will hold valid values
 Keep track of the number of elements stored in an array
 Store number of elements
 Compute comparisons as number of elements – 1


 If you are performing an ascending sort
 After you have made one pass through the list, the largest value is guaranteed to be in its
correct final position

1. Compare every element pair in the list on every pass through the list
2. Comparing elements that are already guaranteed to be in their final correct position
3. On each pass through the array, stop your pair comparisons one element sooner
4. Create a new variable pairsToCompare
5. Set it equal to the value of numberOfEls – 1
6. On each subsequent pass through the list, reduce pairsToCompare by 1
7. Create a new variable didSwap
8. Set it equal to the value of “No”
9. Each time the swap () module executes, change the value to “Yes”

Class
 Sorting data stored in parallel arrays
 Each array must stay in sync StudentRecord

 Sorting records as a whole string name

 Create groups called record structures or classes num score

 Defining a class allows you to sort by either name or scoreendClass