Insertion Sort
Insertion sort is based around a key in the list. The key starts at the left end, moving one space after each iteration. The idea here is that items to the left of the key are already sorted. When the key moves an index, it takes the value at that index and places it at the appropriate place in the sorted list.
Quick Sort
Quick sort is the process of splitting a large list into smaller, manageable problems. We choose a randomized 'pivot' point. All items smaller than the pivot are placed in a new left list, and the items that are greater are placed in a new right list. We recursively call Quicksort on each of these smaller lists, and thus are left with a completely sorted list at the end.
Merge Sort
The idea of merge sort is to continually split a list in halves, calling merge sort on each halve. Once a list is turned into a product of single-item lists. Then these items are compared in the small halves are compared to each other, and concatenated into a large sorted list. This process continues on the growing lists, until all items are included. I'm presuming that wasn't very clear to some people, so here's a picture:
It is easier to think of in 2 stages: First, we recursively call merge sort to product single-item lists. Then, in each 'set' of single-item lists, we compare the values and produce a parent list. This continues until we have a sorted list containing all original items.
No comments:
Post a Comment