Transcript Sorting

Algorithm
• An algorithm is a step-by-step set of operations to be performed.
• Real-life example: a recipe
• Computer science example: determining the mode in an array
Sorting
• Sorting is the process of arranging the elements in
an array in a particular order
• The sorting process is based on specific values –
examples:
• sorting a list of test scores in ascending numeric
order
• sorting a list of people alphabetically by last
name
• There are many algorithms for sorting an array
• These algorithms vary in efficiency & speed
Big-O Notation
• The efficiency/performance or “time complexity” of a sorting algorithm is
measured in “Big O” notation
• For example: if an algorithm has O(n^3) efficiency, that means that the
maximum number of “touches” of the elements of the array necessary to
sort it equals the cube of the number of elements in the array.
• So, for example, if an array holds 5 numbers, then in the worst-case
scenario, it would take this particular sorting algorithm 125 different
comparisons or moves of those numbers in order to sort it.
• If a sorting algorithm has efficiency O(n), this is called “linear time,”
meaning that the algortithm’s efficiency is directly proportional to the size
of the array.
You need to know the basics of these 4
sorting algorithms:
1) Selection Sort
2) Insertion Sort
3) Merge Sort
4) Quick Sort
Selection Sort
1.
2.
3.
4.
5.
find the smallest element in the array
swap it with the first element
find the next-smallest element in the array
swap it with the second element
repeat until all values are in their proper places
Efficiency: O(n^2)
Example:
original
smallest
smallest
smallest
smallest
array:
is 1:
is 2:
is 3:
is 6:
3
1
1
1
1
9
9
2
2
2
6
6
6
3
3
1
3
3
6
6
2
2
9
9
9
Insertion Sort
1) pick an item and insert it into its proper place in a
sorted sublist
2) repeat until all items have been inserted
Efficiency: O(n)
An example:
original:
insert 3:
insert 6:
insert 1:
insert 2:
9
3
3
1
1
3
9
6
3
2
6
6
9
6
3
1
1
1
9
6
2
2
2
2
9
Merge Sort
• Divides a list in half, recursively sorts each half, and then combines
the two lists
• At the deepest level of recursion, one-element lists are reached
• A one-element list is already sorted
• The work of the sort comes in when the sorted sublists are merged
together
• Efficiency: O(n log n)
Quick Sort
• Chooses a pivot value, then partitions the list into two
sublists, (one list contains everything smaller than the pivot,
the other contains everything larger), then recursively sorts
each sublist
• Unlike a merge sort, a quick sort does most of its work when
it divides the list
• It doesn’t need to combine sublists after the recursive steps;
the list is already sorted at that point
• Also, unlike a merge sort, the 2 sublists do not have to be
the same size
• Efficiency: O(n log n)
Review
1. Selection Sort: Swaps numbers in a list until the list is sorted
2. Insertion Sort: Sorts the first 2 #s in the list, then the first 3, then
the first 4, etc…
3. Merge Sort: cuts list in half, sorts them, then combines the 2 lists
4. Quick Sort: cuts list in half using a pivot value; sorts each sublist,
no need to combine the lists at the end since they are already
sorted
Assignments
• Finish Battleship, Connect3, etc…
• AP Exam takers: work on practice test