Professor Kirs

Searching and Sorting: Sample Problems and Exercises

1.0010 What are the advantages and Disadvantages of unsorted lists? When should they be used?

SEE SOLUTION

1.0012 What are the advantages and disadvantages of sorted lists? When should they be used?

SEE SOLUTION

1.0030 Describe the differences between internal and external sorting methods? When should each be used?

SEE SOLUTION

1.0036 Define: Exchange Sorts, Selection Sorts, and Insertion Sorts.

SEE SOLUTION

1.0100 Given unsorted lists of 173, 3200, and 5600 names, what is the maximum number of comparisons will it take to find a name? The average number of comparisons?

SEE SOLUTION

1.0102 Given sorted lists of 173, 3200, and 5600 names, what is the maximum number of comparisons will it take to find an name using a binary search? The average number of comparisons?

SEE SOLUTION

1.0200 Given the sorted array: 12, 21, 29, 34, 35, 37, 42, 48, 50

Show, in detail, using a binary search, the steps needed to find the numbers:

a. 12 SEE SOLUTION

b. 48 SEE SOLUTION

c. 39 SEE SOLUTION

1.1040 Describe how a bubble sort (one-way, two-way, with and without sorted flags) works. When is a bubble sort appropriate?

SEE SOLUTION

1.1042 Given a list of 1,453 (unsorted) elements to be sorted using a bubble-sort, what is the maximum number of passes needed? The maximum number of comparisons?

SEE SOLUTION

1.1120 Given the unsorted list: Juan, Bill, Alice, Teresa, Victor, Fred, Donna

Show how the list would appear AFTER THE FIRST PASS using a BUBBLE-UP sort

1.1121 Given the unsorted list: Juan, Bill, Alice, Teresa, Victor, Fred, Donna

Show the complete process of sorting the list using a BUBBLE-UP sort without a flag

1.1122 Given the unsorted list: Juan, Bill, Alice, Teresa, Victor, Fred, Donna

Show the complete process of sorting the list using a BUBBLE-UP sort WITH a flag

1.1123 Given the unsorted list: Juan, Bill, Alice, Teresa, Victor, Fred, Donna

Show how the list would appear AFTER THE FIRST PASS using a BUBBLE-DOWN sort

1.1124 Given the unsorted list: Juan, Bill, Alice, Teresa, Victor, Fred, Donna

Show the complete process of sorting the list using a BUBBLE-DOWN sort WITHOUT a flag

SEE SOLUTION

1.1125 Given the unsorted list: Juan, Bill, Alice, Teresa, Victor, Fred, Donna

Show the complete process of sorting the list using a BUBBLE-DOWN sort WITH a flag

SEE SOLUTION

1.1126 Given the unsorted list: Juan, Bill, Alice, Teresa, Victor, Fred, Donna

Show the complete process of sorting the list using a BUBBLE-UP AND BUBBLE-DOWN sort WITHOUT a flag

1.1127 Given the unsorted list: Juan, Bill, Alice, Teresa, Victor, Fred, Donna

Show the complete process of sorting the list using a BUBBLE-UP AND BUBBLE-DOWN sort WITH a flag

2.0060 Explain, in general terms, how a quick sort works.

SEE SOLUTION

2.0062 Given a list of 41 elements, what is the maximum number of comparisons needed using a quicksort? How does this contrast with a bubble sort?

SEE SOLUTION

2.0070 What is a recursive function?

SEE SOLUTION