Assignment 3
Correctness of Sorting Algorithms
Introduction
A sorting algorithm arranges elements in a specific order such as ascending or descending order. To prove
that a sorting algorithm works correctly, we use:
• Pre-condition
• Post-condition
• Loop Invariant
• Initialization
• Maintenance
• Termination
• Partial Correctness
• Full Correctness
1. Bubble Sort
Definition
Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.
Algorithm
for i = 0 to n-1
for j = 0 to n-i-2
if A[j] > A[j+1]
swap(A[j], A[j+1])
Pre-condition
• Array A contains n valid elements.
• n ≥ 0.
1
Post-condition
• Array A is sorted in ascending order.
• Same elements remain in the array after sorting.
Loop Invariant
At the start of each outer loop iteration, the last i elements are already sorted and are in their correct
positions.
Initialization
Before the first iteration (i = 0), no elements are guaranteed to be sorted. Therefore, the invariant is true.
Maintenance
During each pass of the inner loop, the largest unsorted element moves to its correct position at the end of
the array. Thus, after every iteration of the outer loop, one more element becomes correctly sorted. The
loop invariant remains true.
Termination
The loop terminates when i = n-1. At this point, all elements are sorted.
Partial Correctness
If the algorithm terminates, the array will be sorted correctly because the invariant guarantees that each
pass places the next largest element in its correct position.
Full Correctness
Bubble Sort is fully correct because: 1. It is partially correct. 2. The loops terminate after a finite number of
iterations.
2
---
2. Insertion Sort
Definition
Insertion Sort builds the sorted array one element at a time by inserting each element into its correct
position.
Algorithm
for i = 1 to n-1
key = A[i]
j = i - 1
while j >= 0 and A[j] > key
A[j+1] = A[j]
j = j - 1
A[j+1] = key
Pre-condition
• Array A contains n valid elements.
• n ≥ 0.
Post-condition
• Array A is sorted in ascending order.
Loop Invariant
At the start of each iteration of the outer loop, the subarray A[0 … i-1] is already sorted.
3
Initialization
Before the first iteration, A[0] alone is considered sorted. Therefore, the invariant holds.
Maintenance
The algorithm inserts A[i] into its proper position within the sorted subarray. After insertion, A[0 … i]
becomes sorted. Thus, the invariant remains true.
Termination
The algorithm stops when i = n. At this point, the whole array A[0 … n-1] is sorted.
Partial Correctness
If the algorithm terminates, the array is correctly sorted because each iteration maintains the sorted order
of the left portion of the array.
Full Correctness
Insertion Sort is fully correct because: 1. It correctly sorts the array. 2. The loop eventually terminates.
---
3. Selection Sort
Definition
Selection Sort repeatedly selects the minimum element from the unsorted part and places it at the
beginning.
Algorithm
for i = 0 to n-2
min = i
for j = i+1 to n-1
4
if A[j] < A[min]
min = j
swap(A[i], A[min])
Pre-condition
• Array A contains n valid elements.
• n ≥ 0.
Post-condition
• Array A is sorted in ascending order.
Loop Invariant
At the start of each iteration of the outer loop, the first i elements are sorted and contain the i smallest
elements.
Initialization
Before the first iteration, no elements are sorted. The invariant is true.
Maintenance
The algorithm finds the minimum element from the unsorted portion and places it at index i. Therefore,
after every iteration, one more smallest element is fixed in its correct position. The invariant remains valid.
Termination
The loop terminates when i = n-1. At this point, all elements are sorted.
5
Partial Correctness
If the algorithm terminates, the array is sorted because the invariant guarantees that the sorted part grows
correctly after each iteration.
Full Correctness
Selection Sort is fully correct because: 1. It satisfies partial correctness. 2. The algorithm terminates after a
finite number of iterations.
---
4. Merge Sort
Definition
Merge Sort uses divide and conquer strategy. It divides the array into halves, recursively sorts them, and
merges them.
Algorithm
MergeSort(A)
if size(A) > 1
divide A into left and right halves
MergeSort(left)
MergeSort(right)
Merge(left, right, A)
Pre-condition
• Array A contains n valid elements.
Post-condition
• Array A is sorted in ascending order.
6
Loop Invariant (Merge Procedure)
During merging, the temporary array contains the smallest elements from both subarrays in sorted order.
Initialization
Before merging begins, no elements are copied into the temporary array. The invariant holds.
Maintenance
At each step, the smaller element from the two subarrays is copied into the temporary array. Therefore, the
temporary array always remains sorted.
Termination
When all elements from both subarrays are copied, the merged array becomes completely sorted.
Partial Correctness
If Merge Sort terminates, the array is sorted because: 1. Recursive calls correctly sort subarrays. 2. Merge
operation combines them in sorted order.
Full Correctness
Merge Sort is fully correct because: 1. Recursive division eventually reaches arrays of size 1. 2. Merge
operation correctly combines sorted arrays. 3. Therefore, the algorithm always terminates and produces a
sorted array.
7
---
5. Quick Sort
Definition
Quick Sort selects a pivot element and partitions the array into two parts:
• Elements smaller than pivot
• Elements greater than pivot Then it recursively sorts both parts.
Algorithm
QuickSort(A, low, high)
if low < high
p = Partition(A, low, high)
QuickSort(A, low, p-1)
QuickSort(A, p+1, high)
Pre-condition
• Array A contains valid elements.
• low and high are valid indices.
Post-condition
• Array A is sorted in ascending order.
Loop Invariant (Partition Procedure)
Before each iteration:
• Elements before pivot index are smaller than or equal to pivot.
• Elements after pivot index are greater than pivot.
8
Initialization
Initially, no elements are partitioned. Therefore, the invariant holds.
Maintenance
Each comparison places elements into correct partition regions. Thus, the invariant remains true
throughout partitioning.
Termination
Partitioning ends when all elements are compared with the pivot. Recursive calls continue until subarrays
contain one or zero elements.
Partial Correctness
If Quick Sort terminates, the array becomes sorted because: 1. Partition places pivot in correct position. 2.
Recursive calls sort left and right partitions.
Full Correctness
Quick Sort is fully correct because: 1. Recursive calls reduce subarray size. 2. Eventually, recursion stops. 3.
The algorithm produces a correctly sorted array.
Conclusion
All sorting algorithms discussed above are correct because they satisfy:
• Proper pre-condition and post-condition
• Correct loop invariant
• Initialization
• Maintenance
• Termination
• Partial correctness
• Full correctness
These concepts help prove mathematically that the algorithms always work correctly.