C949 - Sorting Algorithms

Quick Sort Algorithm

Quick Sort Algorithm

def partition(numbers, i, k):
# Pick middle value as pivot
Midpoint = i + (k - i) // 2
Pivot = numbers[midpoint]

# Initialize variables
done = False
l = i
h = k
while not done:
# Increment l while numbers[l] < pivot
while numbers[l] < pivot:
l = l + 1
# Decrement h while pivot < numbers[h]
while pivot < numbers[h]:
h = h - 1
# If there are zero or one items remaining,
# all numbers are partitioned. Return h
if l >= h:
done = True
else:
# Swap numbers[l] and numbers[h],
# update l and h
temp = numbers[l]
numbers[l] = numbers[h]
numbers[h] = temp
l = l + 1
h = h - 1
return h

Selection Sort

a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.

Selection Sort Algorithm

for i in range(len(numbers) - 1):
# Find index of smallest remaining element
index_smallest = i
for j in range(i + 1, len(numbers)):
if numbers[j] < numbers[index_smallest]:
index_smallest = j

# Swap numbers[i] and numbers[index_smallest]
temp = numbers[i]
numbers[i] = numbers[index_smallest]
numbers[index_smallest] = temp

Insertion Sort

a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part.

Insertion Sort Algorithm

for i in range(1, len(numbers)):
j = i
# Insert numbers[i] into sorted part
# stopping once numbers[i] in correct position
while j > 0 and numbers[j] < numbers[j - 1]:
# Swap numbers[j] and numbers[j - 1]
temp = numbers[j]
numbers[j] = numbers[j - 1]
numbers[j - 1] = temp
j = j - 1

Quick Sort

a sorting algorithm that repeatedly partitions the input into low and high parts (each unsorted), and then recursively sorts each of those parts.

Merge Sort

a sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list.

Radix Sort

a sorting algorithm designed specifically for integers. The algorithm makes use of a concept called buckets and is a type of bucket sort.

Bubble Sort Algorithm

BubbleSort(numbers, numbersSize) {
for (i = 0; i < numbersSize - 1; i++) {
for (j = 0; j < numbersSize - i - 1; j++) {
if (numbers[j] > numbers[j+1]) {
temp = numbers[j]
numbers[j] = numbers[j + 1]
numbers[j + 1] = temp
}
}
}
}

Heap Sort Algorithm

Heapsort(numbers, numbersSize) {
// Heapify numbers array
for (i = numbersSize / 2 - 1; i >= 0; i--) {
MaxHeapPercolateDown(i, numbers, numbersSize)
}
for (i = numbersSize - 1; i > 0; i--) {
Swap numbers[0] and numbers[i]
MaxHeapPercolateDown(0, numbers, i)
}
}

Bucket Sort

a numerical sorting algorithm that distributes numbers into buckets, sorts each bucket with an additional sorting algorithm, and then concatenates buckets together to build the sorted result.

Pre-Order Traversal

In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
If a binary tree is traversed in this method, it can be used to duplicate the tree.

Bubble Sort, Selection Sort, Insertion Sort Time Complexity

Average = Θ(n^2 )
Big-O worst = O(n^2 )
Fast = No

Merge Sort Algorithm

def merge(numbers, i, j, k):
# Create temporary list merged_numbers
# Initialize position variables
# Add smallest element to merged numbers
while left_pos <= j and right_pos <= k:
if numbers[left_pos] <= numbers[right_pos]:
merged_numbers[merge_pos] = numbers[left_pos]
left_pos = left_pos + 1
else:
merged_numbers[merge_pos] = numbers[right_pos]
right_pos = right_pos + 1
merge_pos = merge_pos + 1
# If left partition not empty, add remaining elements
while left_pos <= j:
merged_numbers[merge_pos] = numbers[left_pos]
left_pos = left_pos + 1
merge_pos = merge_pos + 1
# If right partition not empty, add remaining elements
while right_pos <= k:
merged_numbers[merge_pos] = numbers[right_pos]
right_pos = right_pos + 1
merge_pos = merge_pos + 1
# Copy merge number back to numbers
for merge_pos in range(merged_size):
numbers[i + merge_pos] = merged_numbers[merge_pos]

Radix Sort Algorithm

RadixSort(array, arraySize) {
buckets = create array of 10 buckets
// Find the max length, in number of digits
maxDigits = RadixGetMaxLength(array, arraySize)

// Start with the least significant digit
pow10 = 1
for (digitIndex = 0; digitIndex < maxDigits; digitIndex++) {
for (i = 0; i < arraySize; i++) {
bucketIndex = abs(array[i] / pow10) % 10
Append array[i] to buckets[bucketIndex]
}
arrayIndex = 0
for (i = 0; i < 10; i++) {
for (j = 0; j < buckets[i]⇢size(); j++)
array[arrayIndex++] = buckets[i][j]
}
pow10 = 10 * pow10
Clear all buckets
}
}

Shell Sort

a sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm. Uses gap values to determine the number of interleaved lists.

Shell Sort Algorithm

def insertion_sort_interleaved(numbers, start_index, gap):
for i in range(start_index + gap, len(numbers), gap):
j = i
while (j - gap >= start_index) and (numbers[j] < numbers[j - gap]):
temp = numbers[j]
numbers[j] = numbers[j - gap]
numbers[j - gap] = temp
j = j - gap

Bubble Sort

a sorting algorithm that iterates through a list, comparing and swapping adjacent elements if the second element is less than the first element. Uses nested loops.

Quickselect

an algorithm that selects the k^th smallest element in a list. Ex: Running on the list (15, 73, 5, 88, 9) with k = 0, returns the smallest element in the list, or 5.

Quickselect algorithm

def quickselect(numbers, start_index, end_index, k):
if start_index >= end_index:
return numbers[start_index]
low_last_index = partition(numbers, start_index, end_index)
if k <= low_last_index:
return quickselect(numbers, start_index, low_last_index, k)

return quickselect(numbers, low_last_index + 1, end_index, k)

Heap Sort

a sorting algorithm that takes advantage of a max-heap's properties by repeatedly removing the max and building a sorted array in reverse order.

Bucket Sort Algorithm

BucketSort(numbers, numbersSize, bucketCount) {
if (numbersSize < 1)
return
buckets = Create list of bucketCount buckets
// Find the maximum value
maxValue = numbers[0]
for (i = 1; i < numbersSize; i++) {
if (numbers[i] > maxValue)
maxValue = numbers[i]
}
// Put each number in a bucket
for each (number in numbers) {
index = floor(number * bucketCount / (maxValue + 1))
Append number to buckets[index]
}
// Sort each bucket
for each (bucket in buckets)
Sort(bucket)
// Combine all buckets back into numbers list
result = Concatenate all buckets together
Copy result to numbers
}

Post-order Traversal

In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.
If a binary tree is traversed in this method, the tree can be deleted.

In-order Traversal

In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself.
If a binary tree is traversed in this method, the output will produce sorted key values in an ascending order.

Quick Sort Time Complexity

Average = Θ(n log(n))
Big-O worst = O(n^2 )
Fast = Yes

Bucket Sort Time Complexity

Average = Θ(n)
Big-O worst = O(n^2 )
Fast = Yes

Heap Sort, Merge Sort Time Complexity

Average = Θ(n log(n))
Big-O worst = O(n log(n))
Fast = Yes

Radix Sort Time Complexity

Average = Θ(n)
Big-O worst = O(n)
Fast = Yes