Chapter 5 - Searching & Sorting

Question 1

What does sorting also make it easier to do?

Answer 1

Search for the data you need. An unsorted list (often) takes much longer to search than a sorted list.

Question 2

What is searching?

Answer 2

Looking through a file to see if a particular piece of data exists.

Question 2

What is sorting?

Answer 2

Putting items/records of data into a particular order - alphabetical or numerical.

Question 3

What are the stages of bubble sort?

Answer 3

1) Start at the beginning of the list
2)Compare the first & second values. Swap if necessary
3)Compare the second & third valves. Swap if necessary
4)Continue working up the list until the end
5)If any swaps were made, return to the beginning and repeat.

Question 4

How many passes does bubble sort take?

Answer 4

the number of passes and 1 more to check

Question 4

Code bubble sort part

Answer 4

swapInPass = True
while swapInPass == True:
swapInPass = False
for I in range(len(myList)-1):
if myList[i] > myList[I+1]:
temp = myList[I]
myList[I] = myList[I+1]
myList[I+1] = temp
swapInPass = True

Question 5

What type of graph is a bubble sort graph

Answer 5

Exponential

Question 6

What are the stages of insertion sort?

Answer 6

1)If there is only item in the list then stop.
2)Start with the second item and compare with the first. Swap if necessary.
3)Compare the third and second. Swap if necessary. Repeat step 2.
4)Compare the fourth and third. Swap if necessary. Repeat step 3
5)Continue until the last element

Question 7

What is the difference between bubble and insertion sort?

Answer 7

Bubble keeps swapping elements until the list is sorted, whereas insertion sort takes each element and positions it in the best place for it.

Question 8

What is the code for insertion sort?

Answer 8

for i in range(1,len(myList)):
for j in range(I, 0, -1):
if myList[j] < myList[j-1]:
temp = myList[j-1]:
myList[j-1] = myList[j]
myList[j] = temp

Question 9

How much faster is insertion sort compared to bubble sort for long lists

Answer 9

3x

Question 10

What is the stages of merge sort?

Answer 10

1) If there is only one element in the list then stop
2)Divide the list in half (or as close as you can)
3)Recursively decide each half until the size of each list is one.
4)Merge the lists, assembling the elements into the correct order.

Question 11

What is an advantage of Bubble sort?

Answer 11

Simplest to code

Question 12

What is an advantage of insertion sort?

Answer 12

Simple to code

Question 13

What is an advantage of merge sort?

Answer 13

Fastest of the 3 algorithm to sort long lists

Question 14

What is a disadvantage of Bubble sort?

Answer 14

Slowest for long lists

Question 15

What is a disadvantage of Insertion sort?

Answer 15

Twice as fast as bubble sort, but slower than merge sort for long lists

Question 16

What is a disadvantage of merge sort?

Answer 16

Hardest to code out of the 3

Question 17

What is Linear search?

Answer 17

A simple, sequential search. Start at the beginning of the list and move through the elements until you either find the search criteria or reach the end of the list

Question 18

What does linear search not require

Answer 18

Does not require the list to be sorted first. If just one search is needed, this can save a lot of time. However, linear sea

Question 19

What is binary search

Answer 19

Searches ordered lists only and is an average, much faster than linear search

Question 20

What are the stages of binary search?

Answer 20

-Select the middle element and compare to search criteria if it matches, stop
-If it is lower than search criteria, discard left half
-if it is higher than search criteria, discard right half
-Repeat until search criteria is found, or list length is one