ECE209_sorting1.pptx
ECE 209 Fall 2014 Sorting
1″
Sor&ng:”Part”1″
• Fundamentals”of”sor&ng”
• Selec&on”sort”
• Algorithm”analysis”(just”a”li=le)”
ECE 209 Fall 2014 Sorting
2″
Why sorting?
Now that we have collections of data (arrays),
it’s often useful to arrange that data
in a particular order (sorting).
Sorting strings:
students in gradebook
songs in a music library/playlist
Sorting data:
allows binary search
find median, mode, …
find top-N, closest pair, …
ECE 209 Fall 2014 Sorting
3″
Fundamentals
What can we sort?
Any collection of items for which we can construct
a total/partial order
Sometimes, only part of the item is used for sorting.
E.g., only use the first letter of a string.
The data used for sorting is called the key.
For now, we’ll assume integer keys.
ECE 209 Fall 2014 Sorting
4″
What do we need to know?
What order do we want?
increasing, decreasing, something else?
How do we compare two items?
need to know which is greater than/less than
Other properties:
stability? distinct keys? in-place?
already partially sorted (vs. random)?
For now, let’s assume:
• increasing order (smallest to largest)
• integer keys (simple < comparison)
• unstable, in-place, random, may have duplicate keys
ECE 209 Fall 2014 Sorting
5"
Sorting Algorithms
Algorithm ≠ Code
Step-by-step directions for solving a problem;
can be implemented in many different languages.
• Selection sort
• Bubble sort
• Quicksort
There are many others -- why so many?
ECE 209 Fall 2014 Sorting
6"
Selection Sort: Big Picture
Find the smallest element,
exchange it with the first element in the array.
Find the 2nd smallest element,
exchange it with the 2nd element in the array.
Find the 3rd smallest element,
exchange it with the 3rd element in the array.
Etc., etc.
ECE 209 Fall 2014 Sorting
7"
Selection Sort: Algorithm
Given: a sequence, A, of n items (A1 to An)
For i from 1 to n-1
Let min = index of smallest item from Ai to An
Swap Ai with Amin
Why does it work?
After step i, items 1 through i are sorted AND in the correct positions.
(We never have to touch them again.)
Therefore, after n-1 steps, items 1 through n-1 are in the correct
positions. And, since item n is greater than all of them, it must be in
the correct position, also.
Therefore, after n-1 steps, the items are guaranteed to be sorted.
ECE 209 Fall 2014 Sorting
8"
Selection Sort: Code
void selectSort(int a[], int n) {
/* a is an n-element array of integers */
int i, j, min, tmp;
/* for i from 0 to n-2...*/
for (i=0; i