MAT 2051 Unit 9 Discussion DQ1 Data Storage, Retrieval, Sorting Algorithms, Time Complexity

MAT 2051 Unit 9 Discussion DQ1 Data Storage, Retrieval, Sorting Algorithms, Time Complexity

In computer systems, the storage, retrieval, and communication of data occurs frequently and therefore must be optimized and fast. In some instances, it is best to store a list of numbers in some order (for example, in an increasing or decreasing order), to make the retrieval of some of the data very fast (for example, the maximum value).

In section 4.2 of your textbook, you read about the insertion sort algorithm (see Algorithm 4.2.3, page 180). This algorithm will sort a list of n numbers in non-decreasing order. However, in section 9.7, pages 477–483 of the text, you read about a faster sorting algorithm.

In order to fully understand this question, answer the following questions:

The name of the faster sorting algorithm is the tournament sort. How is this faster sorting algorithm achieved?

Given a list of n numbers, what is the worst case times for the insertion sort algorithm and the tournament sort algorithm?

In the insertion sort and the tournament sort algorithms, what discrete structures are used to store the data? Explain.

How does the use of the tree structure provide the framework for a tournament sort?

What is a divide-and-conquer algorithm? Is this a divide-and-conquer algorithm?

You may find the link in the resources section useful for this discussion. Review the Discussion Participation Scoring Guide prior to posting.

Response Guidelines

Read your peers’ posts and respond to two. Compare your post with your peer’s. Explain the similarities and differences.