Sorting Algorithms Overview

These flashcards cover key terms and concepts related to basic sorting algorithms, including bubble sort, selection sort, and insertion sort, as well as their efficiencies and characteristics.

Bubble Sort

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

Selection Sort

A sorting algorithm that divides the input into a sorted and an unsorted region, repeatedly selecting the smallest element from the unsorted region and moving it to the sorted region.

Insertion Sort

A sorting algorithm that builds a sorted array one element at a time, by comparing and inserting elements into their correct position.

O(N²) Time Complexity

A classification of algorithms whose performance will degrade quadratically with the increase in input size, typical of algorithms like bubble sort, selection sort.

Comparisons

The number of times two items in the sorting algorithms are compared to determine their order.

Swaps

The number of times two items in the sorting algorithms are exchanged to place them in the correct order.

Partially Sorted

A state where a portion of the data is sorted, as seen in insertion sort, where only the items to the left of a marker are sorted.

Big O Notation

A mathematical notation used to describe the upper bound of the running time of an algorithm, which helps classify algorithms based on their performance.

N-1 Comparisons

The maximum number of comparisons made during the first pass of sorting algorithms when processing N items.

Quicksort

An advanced sorting algorithm that uses divide-and-conquer principles to efficiently sort data.