SORTING
ALGORITHM ANALYSIS
Sorting
Algorithms
• A sorting algorithm is an algorithm made up of a series
of instructions that takes a list as input, performs specific
operations, and outputs a sorted list.
• Sorting algorithms are taught in data structures classes
as they introduce key computer science topics like Big-O
notation, divide-and-conquer methods, binary trees, and
heaps.
Bubble Sort
• The algorithm repeatedly iterates through
the array, comparing adjacent elements.
• If the current element is greater than the
next element (i.e., they are out of order),
it swaps their positions.
• This process continues until the entire
array is sorted.
Algorithm BubbleSort(arr)
C n = len(arr)
N loop i = 0 to n
N-1 loop j = 0 to n-i-1
C if arr[j] > arr[j+1]
C arr[j], arr[j+1] = arr[j+1], arr[j]
Insertion Sort
• Start with the second element of the array
(since the first element is assumed to be
sorted).
• Compare the current element with the
ones before it in the sorted part.
• If the current element is smaller, swap it
with the preceding element until it’s in the
correct position.
• Repeat this process for each subsequent
element until the entire array is sorted.
Algorithm InsertionSort(arr)
N for i =1 to len(arr)
C key = arr[i]
C j = i-1
N while j >=0 and key < arr[j]
C arr[j+1] = arr[j]
C j -= 1
C arr[j+1] = key
Shell Sort
• Start by selecting a gap value (often called “h”).
• Divide the list into smaller sub-parts, each with
equal intervals of h.
• Sort these sub-lists using insertion sort.
• Gradually reduce the gap value (h) until it
becomes 1.
• Repeat the process until the entire list is sorted.
Algorithm ShellSort(arr)
C n = len(arr)
C gap = n/2
logN while gap > 0
logN loop i = gap to n
C temp = arr[i]
C j=i
N while j >= gap and arr[j-gap] >temp
C arr[j] = arr[j-gap]
C j -= gap
C arr[j] = temp
C gap /= 2
Partition Sort
• Maintain two pointers: left and right.
• Initialize left to the beginning of the array and right
to the end.
• While left is less than or equal to right:
• Move left to the right until we find an element
greater than the pivot.
• Move right to the left until we find an element less
than or equal to the pivot.
• Swap the elements at left and right.
• Repeat until left crosses right.
• Finally, swap the pivot with the element at left.
Amortized Analysis
These lines, from the Partition Sort algorithm are examples of
Amortized Analysis:
while array[left] < pivot
while array[right] > pivot
- Each element in the array is scanned at most once
- The total cost is O(N) but spread out oversteps and not nested.
- The amortized cost is linear, even if the individual steps vary
• Original Array: [ 8, 3, 7, 5, 2, 6, 4, 1 ]
• pivot = 8
• Iteration 1:
array[left] < pivot → advance left
array[right] < pivot → no change
• Iteration 2:
array[left] = 3 < pivot → advance
array[right] = 1 < pivot → no change
• Iteration N: Left and right gradually move toward each other
• Eventually: left ≥ right → exit loop, return right index
Algorithm Partition(array, left, right)
C pivot = array[left]
N while True
A while array[left] < pivot
C left += 1
A while array[right] > pivot
C right -= 1
C if left >= right
C return right
C array[left], array[right] = array[right], array[left]
