Transcript selection_05

Selection sort
Presentation
Yixin Wang
The Algorithm
The big structure of selection sort is looping
In each loop, usually we should do two steps.
1. Find the smallest or biggest value in the list.
2. Interchange the smallest or biggest value
with the first or last element.
Than, loop thought the remaining list and do the
same thing.
Examples
•
•
•
•
•
61, 5 , 91, 60,45
5, 61, 91, 60, 45
5, 45, 91, 60, 61
5, 45 ,60, 91, 61
5, 45 ,60 ,61 ,91
Another example
•
•
•
•
•
•
17, 26, 9,50, 76
17, 26, 9 ,50 ,76
17, 26 ,9, 50, 76
17,9 ,26 ,50 ,76
9, 17, 26, 50 ,76
The first two steps don’t make any change but
it still loop thought the remaining list.
Time complexity
• If the number of element in the list is n, then we should
loop n-1 times to finish sort all the elements in the list.
• From the example we can see that even if the list is already
sorted, system still have to loop and do comparison.
• So the best case like list : 1 2 3 4 5 …….n-1, n
In first loop, it has to do n-1 times comparison. In the second
loop n-2 times , third loop n-3. so, the total time complexity is
(n-1)+(n-2)+(n-3)+……….+3+2+1 which is equal to (n+(n-1)+(n2)+……+2+1)-1 =n*(n+1)/2 -1
Apparently, the interchange complexity and of this best case
is 0
Time complexity cont.….
• The “ worst case” : n, n-1,n-2, ……..3,2,1
The time complexity of the comparison is still n*(n+1)/2 -1
But for interchange time complexity is different. If n is odd,
then it has to interchange (n-1)/2 times, if n is even, it has to
change n/2 times.
The worst case for change complexity : n,1,2,3,4,……n-2,n-1
Time complexity for comparison is n*(n+1)/2 -1
Time complexity for interchange complexity is n-1.(every loop
need to change one time)
Summary for time complexity
• Time complexity for comparison is always
n*(n+1)/2 -1
Time complexity for interchange depends.
for best case is 0, average is If n is odd, (n-1)/2
times, if n is even, it has to change n/2 times.
for worst case is n-1.
Extra memory
• As we know, each interchange procedure
needs one extra memory.
So for best case: 1,2,3,……n-1,n needs no extra
memory.(no interchange procedure)
Worst case : n, 1,2,……n-2,n-1, needs n-1 slot of
memory.(n-1 times interchange procedure)
• According to the algorithm, data structures
selection sort can use are arrays, binary trees,
and every kinds of lists.
• Stack and queue can not use this algorithm,
because these two structures can bot
interchange with two element directly.