WCRT, Runspace, Stability
Quiz yourself by thinking what should be in
each of the black spaces below before clicking
on it to display the answer.
Help!
|
|
||||
|---|---|---|---|---|---|
| Selection Sort | WCRT: Θ(n2)
Runspace: in place
Stable: no
Generic: Forward iterators
Comment: Improves to linear as input approaches sorted
🗑
|
||||
| Insertion Sort | WCRT: Θ(n2)
Runspace: in place
Stable: yes
Generic: Bidirectional
🗑
|
||||
| Heapsort | WCRT: Θ(n log n)
Runspace: in place
Stable: no
Generic: Random Access
Comments: Widely spaced Swaps may cause paging
🗑
|
||||
| Quicksort | WCRT: Θ(n2)
Runspace: + Θ(n)
Stable: no
Generic: Smart Bidirectional
Comments: AC = Θ(n log n)
🗑
|
||||
| Merge Sort (array) | WCRT: Θ(n log n)
Runspace: + Θ(n)
Stable: yes
Generic: Random Access
Comments: Extra space costly in time
🗑
|
||||
| Merge Sort (list) | WCRT: Θ(n log n)
Runspace: in place
Stable: yes
Generic: Member Function
Comments: in-place! But Lists are slow.
🗑
|
||||
| Counting Sort | WCRT: Θ(n + k)
Runspace: + Θ(k
Stable: yes
Comment: Function Object argument
🗑
|
||||
| Radix Sort | WCRT: Θ(d(n + k))
Runspace: + Θ(k)
Stable: yes
🗑
|
||||
| Bit Sort | WCRT: Θ(nb)
Runspace: + Θ(n)
Stable: yes
Comments: Use Bit function object in counting sort
🗑
|
||||
| Byte Sort | WCRT: Θ(nB)
Runspace: + Θ(n)
Stable: yes
Comments: Use Byte function object in counting sort
🗑
|
Review the information in the table. When you are ready to quiz yourself you can hide individual columns or the entire table. Then you can click on the empty cells to reveal the answer. Try to recall what will be displayed before clicking the empty cell.
To hide a column, click on the column name.
To hide the entire table, click on the "Hide All" button.
You may also shuffle the rows of the table by clicking on the "Shuffle" button.
Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.
To hide a column, click on the column name.
To hide the entire table, click on the "Hide All" button.
You may also shuffle the rows of the table by clicking on the "Shuffle" button.
Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
Created by:
deleted user
Popular Computers sets