Research Paper: Bubble and Insertion Sorts

Research Paper: Bubble and Insertion Sorts

Sorting data is one of the most important, widely studied, and frequently used concepts in computer applications. Information is everywhere and with the use of computers, it can easily be stored, manipulated, and accessed. Just about every piece of information collected today is part of some type of list. These lists can range from census data for a given state to an alphabetical listing of all of the products sold at a particular supermarket. Sorting lists of data in an efficient manner is critical to many applications. From small companies to major corporations, most computer applications need to sort data as part of their basic functions. This paper will take an in-depth look at both the bubble sort and insertion sort algorithms. It will explain the efficiency of each sort, discuss which sort code is more difficult to understand, talk about conditions that may improve each sort algorithm, determine if the base sort code could be improved to increase efficiency, compare/contrast the similarities and differences of each sort, discuss the number of loops in each sort in relation to performance, and illustrate the behavior of each sort through step-by-step number tracing. The actual data used in the discussions comes from code used in the programming portion of the lab, specifically how the sorts perform using the random four-integer list. In C++ programming, a sort algorithm accepts an unordered list and outputs an ordered list, either as ascending or descending. In order to discuss the merits or disadvantages of a sort, the criteria for evaluation needs to be understood. In general, the most important consideration for a sort is its inherent efficiency or speed. Efficiency, in the context of sorts, refers to the number of times item comparisons are performed as well as the number of item swaps necessary to sort a given list. In his article, David Ring discusses three factors that affect speed: order, overhead, and consistency. Order describes the length of and time required to sort the list. Using Big-O notation, the performance of the bubble and insertion sorts can be shown as O(n²). This is directly proportional to the square of the size (n) of the list (Bell). The overhead factor is generated by how complex the code is, such as the number of loops and other logic. The consistency factor accounts for how much sorting the list requires: none, some, or all. This factor can be thought of in terms of “best” and “worst” case scenarios. The sort status of a list may not affect a sort’s speed, or it may speed up or slow down performance. “The best- and worst-case run times are important if you expect to encounter one of these situations frequently. Often a sort has a good average case but a terrible worst case” (Schildt 499). Ring notes other considerations for sort algorithms ‘versatility in handling various data types, consistency of performance, memory requirements, length and complexity of code, and the property of stability’. The two sorts discussed here are the bubble and insertion sorts. They are considered simple, swap-based algorithms. This type of code is not very complicated; it works by simply looping through the list, comparing two values, and then swapping the values if necessary. The bubble sort (also known as an exchange sort) is so-called as items float to the top of the list like a bubble in a carbonated beverage. Using a bubble sort, an array of size n, is sorted with n-1 iterations. Array [index] is compared with array [index +1]. If array [index] has a larger value, the two values are swapped. As this process continues, larger values gravitate to the bottom of the list and smaller values move to the top (Malik 1183). The following code is used for the bubble sort in the lab:
Bubble Sort Algorithm (Lab): int BubbleSort(int unsortedArray[], int length) { for (int iteration = 1; iteration < length; iteration++) { for (int index = 0;

Show More

Gp Essay Mainpoints

Managing Information Technology (7th Edition) Essay

Research Paper: Bubble and Insertion Sorts

Related Documents: Research Paper: Bubble and Insertion Sorts

Gp Essay Mainpoints

Managing Information Technology (7th Edition) Essay