Sorting Secret - Computerphile
Two different sorting algorithms are actually the same. Professor Graham Hutton explains.
Note from Professor Hutton: It's great to see all the discussions here! To clarify a point raised in some of the comments, the video shows that if you consider the essential underlying idea of selection sort and insertion sort, in terms of how they decompose the problem of sorting, then they perform the same operations but in different orders. Using the picture in the video, selection sort proceeds column at a time and insertion sort proceeds row at a time, but they both perform the same 'triangle' of operations in the end. A particular implementation of these sorting methods may optimise the process in some way, e.g. in a sequential implementation each row can stop comparing numbers once the point of insertion is found. But this is an implementation detail that is dependent on the computational model used, such as sequential versus parallel, or imperative versus functional, rather than part of the essential means by which the sorting methods work.
Slow Loris Attack: https://youtu.be/XiFkyR35v2Y
Cracking Windows by Atom Bombing: https://youtu.be/rRxuh9fp7QI
Quantum Computing: https://youtu.be/BYx04e35Xso
Babbage's Analytical Engine: https://youtu.be/5rtKoKFGFSM
Quicksort: https://youtu.be/XE4VP_8Y0BU
Getting Sorted: https://youtu.be/kgBjXUE_Nwc
http://www.facebook.com/computerphile
https://twitter.com/computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: http://bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at http://www.bradyharan.com
Видео Sorting Secret - Computerphile канала Computerphile
Note from Professor Hutton: It's great to see all the discussions here! To clarify a point raised in some of the comments, the video shows that if you consider the essential underlying idea of selection sort and insertion sort, in terms of how they decompose the problem of sorting, then they perform the same operations but in different orders. Using the picture in the video, selection sort proceeds column at a time and insertion sort proceeds row at a time, but they both perform the same 'triangle' of operations in the end. A particular implementation of these sorting methods may optimise the process in some way, e.g. in a sequential implementation each row can stop comparing numbers once the point of insertion is found. But this is an implementation detail that is dependent on the computational model used, such as sequential versus parallel, or imperative versus functional, rather than part of the essential means by which the sorting methods work.
Slow Loris Attack: https://youtu.be/XiFkyR35v2Y
Cracking Windows by Atom Bombing: https://youtu.be/rRxuh9fp7QI
Quantum Computing: https://youtu.be/BYx04e35Xso
Babbage's Analytical Engine: https://youtu.be/5rtKoKFGFSM
Quicksort: https://youtu.be/XE4VP_8Y0BU
Getting Sorted: https://youtu.be/kgBjXUE_Nwc
http://www.facebook.com/computerphile
https://twitter.com/computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: http://bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at http://www.bradyharan.com
Видео Sorting Secret - Computerphile канала Computerphile
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Arrays vs Linked Lists - ComputerphileGetting Sorted & Big O Notation - ComputerphileProgramming BASIC and Sorting - ComputerphileInfinite Data Structures: To Infinity & Beyond! - Computerphile7. Counting Sort, Radix Sort, Lower Bounds for SortingWhy My Teenage Code Was Terrible: Sorting Algorithms and Big O NotationMerge Sort vs Quick SortGame Physics (in Assembler) - ComputerphileThe True Power of the Matrix (Transformations in Graphics) - ComputerphileSorting Algorithms (Bubble Sort, Shell Sort, Quicksort)Lambda Calculus - Computerphile3. Insertion Sort, Merge Sort15 Sorting Algorithms in 6 MinutesProgramming Loops vs Recursion - Computerphile357686312646216567629137 - NumberphileWhat is a Monad? - ComputerphileQuick Sort - ComputerphileFunctional Programming & Haskell - ComputerphileInsertion Sort vs Bubble Sort + Some analysis