|
|
|
| Proofs – best case correct sorting |
||
| by
comparison |
||
|
|
|
|
|
|
|
|
|
|
| • | List
is x1,…,x8 |
||||||||
| • | Edge
is comparison |
||||||||
| • | <7
edges |
||||||||
| à graph not connected |
|||||||||
| • | Connected
components |
||||||||
| could
be on either side. |
|||||||||
| How
would the algorithm |
|||||||||
| know? |
|||||||||