Sorting Linked Lists
Selection sort on linked lists
- L = original list, S = sorted list (initially empty)
- find largest value V in L; unlink it
- link V node at front of S
Bubble sort on linked lists
- traverse list: if current > next, swap node values
- repeat until no swaps required in one traversal
Selection sort on linked lists
- L = original list, S = sorted list (initially empty)
- scan list L from start to finish
- insert each item into S in order
|