sorting + searching Flashcards
bubble sort: what is the best runtime?
O(n)
bubble sort: what is the worst runtime?
O(n^2)
bubble sort: what is the average runtime?
O(n^2)
what sort method has the same runtime for all cases (average, best, worst) and what is the runtime?
O(n^2) for selection sort
insertion sort: what is the best runtime?
O(n)
insertion sort: what is the average runtime?
O(n^2)
insertion sort: what is the worst runtime?
O(n^2)
disadvantages of the selection sort?
it will not exit the sort if it sorts the array at an earlier point than O(n^2)
structure of a bubble sort?
for loop
structure of a selection sort?
for loop within a for loop
structure of an insertion sort?
for loop with nested while loop
quick sort: best runtime
O(n log (n))
quick sort: average runtime
O(nlog(n))
quick sort: worst runtime
O(n^2)
structure of quicksort
a while loop with two nested while loops and one nested if statement
what array type is used for quick sort?
primitive types
what is the runtime for all cases of Merge sort?
O(nlog(n))
structure of merge sort
three unnested while loops, the first while loop has an if/else nested
best runtime for binary search
O(1)
worst and average runtime for binary search
O(log(n))
best runtime for linear/sequential search
O(1)
worst and average runtime for linear and sequential search
O(n)
prerequisite for binary search
the array must be in order
what does binary search do?
outputs the index of the item your are searching for in the array. If it is not in the array, it outputs -1.
