• Answer to the quiz should be forthcoming Gary Coulam has it in electronic form

Simple Sorts

• Selection Sort
• for(i = 1; I < n; i++)
  • Find i-th smallest number and move it to position I.
• Bubble sort, Insertion sort give the same time requirement
• Page 577
• bottom = vSize-1
• while (bottom > 0)
• {
• lastswapindx = 0;
• for(i = 0; I < bottom; I++)
• if(vec[i] > vec[i+1])
• {
• swap(vec[i],vec[i+1]);
• lastSwapindx = i;
• }
• bottom = lastSwapindx;
• }
• Bubble sort is more efficient than selection sort, because it does not sort the array if it is already sorted
• But time requirement in the worst case still quadratic.
• Lower bound:
  • The minimum time requirement to solve a particular problem. Irrespective of the algorithm. The algorithm may or may not be known.
  • Any algorithm known or unknown will not take less time than the lower bound.
  • Searching in an ordered list: the lower bound is O(log n).
  • We have already found an algorithm, binary search which require O(log n) time to search.
  • If you know an algorithm that needs the same time as the lower bound, we can stop our quest for more efficient algorithm, because it doesn't exist.
• Matrix multiplication
  • The straightforward algorithm for matrix multiplication needs .
  • The highest known lower bound is
  • Mathematicians have developed algorithms that go as low as
  • Either find a higher lower bound or find an algorithm with lower time requirements.
  • -Sorting
  • Shell sort
    • Doesn't sort
    • Calls a sorting algorithm
    • This sorting algorithm should have a good best case time requirements
    • For example, if the list is already sorted the sorting algorithm should terminate O(n)
    • Bubble sort, Insertion sort can do this for you.
    • Shell sort feeds smaller lists to this sorting algorithm
    • Smaller items start moving to the top
    • It is difficult to calculate the time requirements, but you can see from the example that smaller items start moving to the top. Good sorting algorithm will use this fact to reduce the time requirements
    • Empirical studies have shown that on an average shell sort takes less than .
• But we still haven't reached the lower bound
• ) is the lower bound for sorting