Lecture 7: Data Structures and Algorithms - Richard Buckland

[sunshine36989]

can any one tell me that if he gave any lecture on order of growth? if yes than whats the lec number.. plz/..

[sedoppio]

These videos are getting better and better exponentially :P

[icon0x1]

This guy is awesome.

[321noone]

9 sorted looks at a subset of 3 sorted?

So, it does 3 sort, with intervals between the numbers at 3. So, 2,3,5,6,4,1,7,9,8,0,15,17,19 and at 3 sorted we'll have 2, 4, 8, 19 as one group, 3,1,0 being the other group and so on. These are going to be 3 sorted. The 9 sorted looks at the numbers that are 9 apart. So, first group will consist of 2, 15. However, that j sort does not change that fact that its still k sorted. How can you say that, on the last pass, it wont do any swaps?

[321noone]

@321noone wait I got it. The 9 is a multiple of 3. So, since its 3 sorted already, it is automatically 9 sorted. And yeah, i got the number intervals wrong, bleh. i get it.

[gavaiken]

LOL at 8:06

[Shishberg]

Worth mentioning (so sayeth Wikipedia, anyway) that Pratt's sequence for Shell sort is O(n log²n), not O(n log n).

[UNSWelearning]

yes you are right, thanks! just briefly carried away by respect for pratt.

[Shishberg]

And fair enough too.

[AMDNiels]

@Shishberg n log²n ∈Θ(n log n), so that doesn't really matter.