CS计算机代考程序代写 AI algorithm ECE209_sorting1.pptx

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