Introduction to Programming: Starting Out with Programming Logic and Design: Chapter 9: Sorting and Searching Arrays

Starting Out with Programming Logic and Design (2nd Edition)

1. The Bubble Sort Algorithm

Sorting Algorithms

Often information in an array will need to be sorted in some way. It could be by number or alphabetical, and it could be ascending or descending order. One type of sort is the bubble sort. It is called the bubble sort because as you make passes thru it, values will bubble to the top (or bottom). So how does it work? Let's assume ascending order.

On the first pass thru, position 0 and 1 are compared. If 0 > 1 than they are swapped. Then 1 and 2 are compared and the same is done. This continues till all elements in the array are done. When this pass is done the last element should have the largest value in it. The next time thru, we do the same except we do it till the size of the array minus 1. We subtract 1 each time. Why? Because each pass thru will leave the largest value at the end.

Swapping Array Elements

We cannot just make the 0 element the 1 element and vice-versa. This is not possible so we must use temporary locations. We must assign element 0 to a temporary location, switch 1 into 0 and then move the temporary location into 1. This is the same for all elements that we compare and need to be swapped.

Designing the Bubble Sort Algorithm

Usually the bubble sort algorithm is a module that data is sent to. The details for its pseudocode are too complicated for these notes. They are in the book.

Sorting an Array of Strings

As noted in previous chapters, characters can be compared by each letters numeric equivalent. Just substitute a string for the number.

Sorting in Descending Order

To get descending order, change the greater than to a less than in the comparison.

2. The Selection Sort Algorithm

The bubble sort is simple, easy to understand but not efficient. A selection sort algorithm will take fewer steps to do. A scan is done of the array to find the lowest number. A pointer to it is stored in a temporary location. When the scan is done the swap is made between the lowest number and the first element. Then starting with the second element we scan again for the lowest number and swap it. We keep doing this cycle until we are at the last element.

3. The Insertion Sort Algorithm

The insertion sort algorithm swaps the first two elements and then looks at the third and inserts it where it needs to be in the list. This is done with all subsequent elements.

4. The Binary Search Algorithm

While the sequential search is simple it is not efficient. If we have a large array, let’s say 10,000, there is a possibility that we will have to go through 10,000 elements to find what we are looking for. By putting the elements is order first, if we search to the middle location we can determine if it is before or after that location. We have eliminated half the array. We can then keep halving things till we find what we are looking for.

Efficiency of a Binary Search

Because the binary search eliminates half the field each time it cuts the amount of time it will take to do a search. In fact a 1000 item array can be sorted in 10 tries at a maximum.

 

Sorting and Sort Systems (The Systems programming series)