Sorting - Flashcards

These flashcards cover key terms and definitions related to sorting algorithms, their characteristics, and their complexities.

Time Complexity

A measure of the amount of time an algorithm takes to complete as a function of the size of the input.

Internal Sort

A sorting method where all data to be sorted is stored in the computer’s main memory.

External Sort

A sorting method where some data to be sorted may be stored in external, slower storage.

In Place Sort

A sorting method that requires a constant amount of extra space regardless of the input size.

Insertion Sort

A sorting algorithm that builds a sorted sequence incrementally by removing one element at a time and inserting it into the correct position.

Loop Invariant

A condition that holds true at the beginning and end of each iteration of a loop, serving as a key feature in the proof of correctness for an algorithm.

Best Case Analysis

The least amount of time required by an algorithm to complete when the input is in the most favorable state.

Worst Case Analysis

The maximum amount of time required by an algorithm to complete when the input is in the least favorable state.

Bubble Sort

A simple sorting algorithm that repeatedly passes through the list, compares adjacent elements and swaps them if they are in the wrong order.

Selection Sort

A sorting algorithm that sorts an array by repeatedly finding the minimum element and moving it to the front.

Merge Sort

A divide-and-conquer algorithm that splits the array into smaller subarrays, sorts them, and then merges them back together.

Quicksort

A divide-and-conquer algorithm that sorts an array by partitioning it into two subarrays based on a pivot, where elements less than the pivot are on one side and those greater are on the other.

Partitioning

The process of dividing the array into two parts during the quicksort algorithm, based on a chosen pivot.

Comparisons and Exchanges

Operations in sorting algorithms that relate to comparing elements to determine their order and swapping or exchanging elements to place them in order.