What have we learned

Summary

We learned about efficient and inefficient ways to sort, and search. Some bad sorting algorithms were insertion sort, bubble sort, and selection sort. Some good ones were merge sort, and quick sort. If you are a serious programmer, you also learned about radix sort heap sort, Dijikstra's and A*. We also learned about searching, with simple search, binary search, BFS, and DFS.

You should remember that bubble sort, insertion sort, and merge sort all work in O(N^2), quick sort and merge sort work in (n log n, but it is slightly trickier than this), and that binary search works in log n time. You should know that BFS and DFS search graphs, with BFS focusing at the top, and DFS focusing on the bottom (heh, bottom).

Questions

• If someone says sorted array, which algorithm should you think of first?
• What does an unstable sort mean? Which sorting algorithm do we know that is unstable?
• If data is at the bottom of a graph, which search should we use?
• What makes quick sort better than merge sort?

Answers