Module 5: Sorting Algorithms

Sorting Algorithm

An algorithm that puts elements of a list in a certain order, typically numerical or lexicographical.

Nondecreasing Order

An order of elements where each element is no smaller than the previous one according to total order.

Permutation

A reordering of elements that retains all original elements.

Time Complexity

The running time describing how many operations an algorithm must carry out to complete.

Space Complexity

The memory space required to run a particular algorithm.

Bubble Sort

A simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order.

Selection Sort

An in-place comparison-based algorithm that divides the list into sorted and unsorted parts and repeatedly selects the smallest element.

Insertion Sort

An in-place comparison-based algorithm that maintains a sorted sub-list and inserts unsorted elements into their correct position.

Shell Sort

An efficient sorting algorithm based on insertion sort with improved performance using gaps.

Merge Sort

A Divide and Conquer algorithm that divides the input array into two halves, sorts them, and then merges the sorted halves.

Heap Sort

A comparison-based sorting technique based on Binary Heap data structure that sorts elements by repeatedly finding the maximum.

Stable Sort

A sorting algorithm that maintains the relative order of equal elements in the sorted output.

Counting Sort

An integer sort algorithm that counts the number of occurrences of each unique element in the input.

Average Case Complexity

The expected running time of an algorithm averaged over all possible inputs.

Worst Case Complexity

The maximum running time of an algorithm under the worst possible scenario of inputs.

Interval (Gap)

The distance between elements compared in Shell sort, determining how far apart elements are.

Max Heap

A binary heap where the value of a parent node is greater than or equal to that of its children.

Min Heap

A binary heap where the value of a parent node is less than or equal to that of its children.

Complete Binary Tree

A binary tree where every level, except possibly the last, is completely filled.

Heuristic

A technique designed to solve a problem faster than classic methods, often by trading optimality, completeness, or precision for speed.

Canonicalizing Data

The process of converting data into a standard or canonical form.