Algorithms

Algorithms

Sorting

Given: compare(a,b) to compare 2 numbers. Goal: Sort a list of numbers from smallest to largest.

\(\displaystyle O(n^2)\) Algorithms

Insertion Sort

Basic Idea:

• Maintain a subarray which is always sorted

Algorithm:

• Grab a number from the unsorted portion and insert it into the sorted portion
• Repeat until no more numbers are in the unsorted subarray

Selection Sort

Basic Idea:

• Maintain a subarray which is always sorted.
• Every number in the sorted subarray will be smaller than the smallest number in the unsorted subarray.

Algorithm:

• Find the smallest number in the unsorted portion and insert it into the sorted portion
• Repeat until no more numbers are in the unsorted subarray.

Quicksort

Basic Idea:

• Divide an conquer.
• Very fast. Average case O(nlogn).
• Good for multithreaded systems.

Algorithm:

Selection

Given: compare(a,b) to compare 2 numbers. A number k. Goal: Return the k'th largest number.