Chapter 5 - Searching & Sorting Flashcards
What does sorting also make it easier to do?
Search for the data you need. An unsorted list (often) takes much longer to search than a sorted list.
What is searching?
Looking through a file to see if a particular piece of data exists.
What is sorting?
Putting items/records of data into a particular order - alphabetical or numerical.
What are the stages of bubble sort?
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.
How many passes does bubble sort take?
the number of passes and 1 more to check
Code bubble sort part
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
What type of graph is a bubble sort graph
Exponential
What are the stages of insertion sort?
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
What is the difference between bubble and insertion sort?
Bubble keeps swapping elements until the list is sorted, whereas insertion sort takes each element and positions it in the best place for it.
What is the code for insertion sort?
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
How much faster is insertion sort compared to bubble sort for long lists
3x
What is the stages of merge sort?
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.
What is an advantage of Bubble sort?
Simplest to code
What is an advantage of insertion sort?
Simple to code
What is an advantage of merge sort?
Fastest of the 3 algorithm to sort long lists
What is a disadvantage of Bubble sort?
Slowest for long lists
What is a disadvantage of Insertion sort?
Twice as fast as bubble sort, but slower than merge sort for long lists
What is a disadvantage of merge sort?
Hardest to code out of the 3
What is Linear search?
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
What does linear search not require
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
What is binary search
Searches ordered lists only and is an average, much faster than linear search
What are the stages of binary search?
-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
