COMPSCI 1JC3 Lecture Notes - Lecture 10: Time Complexity, Bubble Sort, Merge Sort
15 Dec 2018
School
Department
Course
Professor
Document Summary
The first code ever written for a stored program computer was a program for efficient sorting. Email displays messages sorted by time of receipt. Social media sorts feed by proprietary measure. Sorting algorithms: bubble sort, insertion sort, merge sort. Can not compare in linear or constant time. Solving boolean expressions by trying all possibilities. Shuffle-til-it"s sorted, imagine attempting to shuffle cards to get a sorted deck. Repeatedly scans array, switching two entries if they"re not in order, until the entire array is in order. Requires n scans, n-1 comparisons = n * (n - 1) operations required = n 2 - n. Start at beginning of list, compare and sort numbers to the right, repeat until all numbers are sorted. Requires (n 2 - n) / 2 comparisons. A bit faster than bubble sort, but still quadratic time.
