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
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
