Wyo C++ Ch. 19 Notes

Computer Science Using C++

Ch. 19 Notes

Objective #1: Understand the basics of sorting.

When you rearrange data and put it into a certain kind of order, you are sorting the data. You can sort data alphabeticall, numerically, and in other ways. Often you need to sort data before you use searching algorithms to find a particular piece of data.
There are a number of different sorting algorithms that are widely used by programmers. Each algorithm has its own advantages and disadvantages. The sorting algorithms include the sequential sort, the insertion sort, the bubble sort, the Shell sort, the quick sort, and the merge sort.
The key field is the field upon which the data is sorted.
A key value is a specific value that is stored within the key field.
The input size is the number of elements in a list that will eventually be sorted.
There are two basic approaches to sorting data, the incremental approach and the divide and conquer approach. Using the incremental approach, one sorts the whole list at once using loops usually. The divide and conquer approach splits the list up into parts and sorts each part separately. Then this approach manages to join the sorted parts together into a large sorted list.

Objective #2: Understand the selection sort.

The selection sort is an incremental one.
Every key value is examined starting at the beginning of the list. Assuming that you are sorting the list in ascending order, you use a temporary variable to "remember" the position of the largest key value. By the time you have examined every key value, you swap the key value that was the largest with the last key value in the list. Next, you repeat the process again from the beginning of the list, however, you will not need to compare anything to the new last key value in the list since you know it is the largest.
This algorithm uses nested loops and is easy to code. However, it is quite inefficient since it continues processing even if the list is already sorted. Whether the original data is close to being sorted or not, this algorithm takes quite awhile since a lot of loop iterations and comparisons must be made.

Objective #3: Understand the insertion sort.

The insertion sort is incremental in nature.
Two lists are used throughout this algorithm. One list is sorted and the other is unsorted. The sorted list begins with one key value. Successively, one key value from the unsorted list is placed into the proper order with the smaller, sorted list. As more key values are placed into the sorted list, that list becomes larger.
This is similar to the way a person usually organizes a hand of playing cards.
The insertion sort is relatively quick for small lists that are close to being sorted.

Objective #4: Understand the bubble sort.

The bubble sort is an incremental sort which is usually faster than the insertion and selection sorts.
A bubble sort works similarly to the release of CO₂ in carbonated soda.
Beginning at one end of a list, adjacent key values are compared. Assuming that you are sorting the list into ascending order, these two key values would be swapped if the first was larger than the second. Next you compare the larger of the two to the next adjacent key value in the list, swapping if necessary. By the time that you compare the last two key values in the list, you know that the largest key value from the whole list will be in the last position. Using a loop, this process is continued (comparing adjacent key values) from the beginning of the list. However, you will not need to compare anything to the last key value in the list since you know it is the largest.
A Boolean variable is used in a bubble sort to "remember" if any swaps are made on a particular sweep of the list. If a swap is made the variable might be set to TRUE. At the beginning of each successive sweep, the variable is set to FALSE. When a complete sweep of the loop has been made without any swaps, the variable will still be FALSE.
The use of the Boolean variable causes this sort to only sweep the list one extra time after it has been fully sorted. This makes the bubble sort more efficient than a number of other incremental sorts.

Objective #5: Understand the Shell sort.

The Shell sort is an incremental sort which was named after it's inventor, D. L. Shell. It is sometimes called the comb sort.
This sorting algorithm is similar to the bubble sort but instead of comparing and swapping adjacent elements, elements that are a certain distance away from each other are compared and swapped. The certain distance can be called the gap size and might initially be set to half the input size.
After each sweep, the gap is decreased until eventually adjacent elements are compared. A Boolean variable is used as it is in the bubble sort to add efficiency.
The Shell sort is much faster than other incremental sorts since very large and very small key values are quickly moved to the appropriate end of the list.

Objective #6: Understand the quicksort.

The quicksort is a divide and conquer algorithm and is more efficient than incremental sorts. It can be difficult to code though since it uses recursion or stacks.
The original list is partitioned into two lists. One of the lists contains elements that are greater than the first original element. The second list contains elements that are less than or equal to the first original element. Then, each of these two partitions are partitioned using the same algorithm. Eventually, partitions will have only one element each. When this happens, that single-item partition is considered to be sorted and only partitions with multiple-items are partitioned. When every partition consists of only a one element, the partitions are placed into order to make a fully sorted list.

Objective #7: Understand the merge sort.

The merge sort is a divide and conquer algorithm.
The whole list is divided into lists that consist of one element a piece. Then, every two adjacent lists are merged into one larger sorted list. The process continues until one sorted list remains.