# Sorting Algorithms – step by step videos

Leave a commentMay 18, 2016 by oneOokay

>>>Charmander<<<

- Quick Sort – step by step
- Recursive
- Pivot divides array into two parts (pivot usually is not the middle element)
- Pivot, left and right
- Swap pivot with left/right element until left == right
- nLogn
- no extra storage space
- 先整体有序，再局部有序

- Heap Sort – step by step
- MinHeap: ascending order
- MaxHeap: descending order

- Merge Sort – step by step
- Recursive
- Find middle element, divide array into HALF, until the sub array has only 1 element
- Sort sub arrays then merge them together
- Major work: Merging the sub arrarys
- 先局部有序，再整体有序
- extra storage memory: an extra temporary array of the same size as the input array for merging
- nlogn
- Merging algorithm
- https://www.youtube.com/watch?v=2ScKuAH2_vM&index=4&list=PLG6ePePp5vvYVEjRanyndt7ZSqTzillom

- Bubble Sort

- Insertion Sort
- If we have n elements, then it requires (n-1) pass to sort
- In each pass we have k comparisons, where k is the pass number
- N2

- Selection Sort
- Find the smallest element in each pass and place it in the appropriate position
- Requires n-1 pass to sort an array of n elements
- In each pass, we have (n-k) comparisons: k is the pass number
- 1st pass requires (n-1) comparisons; kth pass requires (n-k) comparisons; the last pass requires 1 comparison
- N2

WHOLE PLAYLIST:

Advertisements