Sorting Quiz

Selection Sort After k Iterations

smallest element from right subarray swapped into the front for k passes

Insertion Sort Idea

build sorted subarray on left, insert next element by comparing backward and swapping until correct spot

Bubble Sort Idea

repeatedly compare adjacent elements, swap if the left one is greater, "largest bubbles right" each pass

Merge Sort Idea

recursively split array into halves and merge them using temporary arrays

Heap Sort Idea

build a max heap, repeatedly swap root with last active element, shrink heap, then heapify root

Binary Search Tree (BST) Rule

left child < parent < right child

Inorder Traversal

Left → Root → Right, outputs BST values in increasing sorted order

Preorder Traversal

Root → Left → Right, shows insertion structure but not sorted

Postorder Traversal

Left → Right → Root, used for deletes/freeing but not sorted

Max Heap Rule

parent ≥ all children, largest element at root

Min Heap Rule

parent ≤ all children, smallest element at root

Heap Children Indexes

left = 2i+1, right = 2i+2

First Non-Leaf Index in Heap

floor(n/2) - 1

Stable Sort Definition

preserves the original relative order of equal-value elements

Unstable Sorts

Selection Sort, HeapSort, BST Sort

Stable Sorts

Insertion Sort, Bubble Sort, Merge Sort

In-Place Algorithm

modifies the input array directly using only a few extra variables

Out-Of-Place Definition

uses separate memory structure (extra array, tree, etc.) to output result

Merge Step Order Behavior

when equal, left half is chosen first (<=), ensuring stability

Selection Sort Swap Behavior

swaps smallest element found in scan into index i if smallest ≠ i

Worst Case Complexity (general comparison sorts)

O(n²) for simple nested-loop sorts, O(n log n) for divide/heap sorts, O(n²) for unbalanced BST chain

Time Complexity Definition

how runtime operations grow as input size n increases

Space Complexity Definition

how extra memory usage grows as input size n increases

Selection Sort Extra Space

O(1)

Merge Sort Extra Space

O(n)

Heap Sort Extraction Step

swap root with last active index, decrement heap size, heapify root to restore max-heap property

BST Sort Worst Case

O(n²) when inserted values are already sorted and tree becomes a chain