Sorting Algorithms Overview

A sorting algorithm that repeatedly finds the largest (or smallest) element in the unsorted subarray and swaps it with the last element of the subarray, gradually building up the sorted portion.

In Selection Sort, it involves iterating through the unsorted portion of the array to find the element with the largest (or smallest) value.

Selection Sort repeatedly narrows down the unsorted subarray by one element after each iteration, effectively building the sorted portion from the end to the beginning.

Sorting algorithms fall into two main categories: comparison-based and non-comparison-based. Comparison-based algorithms determine the order of elements by comparing them to each other.

Sorting algorithms can be either iterative or recursive. Iterative algorithms use loops to process data step by step, while recursive algorithms break down problems into smaller subproblems, solving them and combining the results.

A recursive sorting algorithm that divides the input array into two halves, sorts them recursively, and then merges the sorted halves into a single sorted array.

A powerful problem-solving technique that involves breaking down a problem into smaller subproblems, recursively solving them, and then combining the solutions to solve the original problem.

In Merge Sort, this step involves recursively sorting the two halves of the array that have been created in the Divide step.

This step in Merge Sort involves combining the two sorted halves of the array into a single sorted array.

This step in Merge Sort involves dividing the input array into two equal halves, creating two smaller subproblems.

A sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order, eventually placing the largest element at the end of the list.

In bubble sort, each pass through the list moves the largest unsorted element to its correct position. The number of passes required is one less than the size of the array.

The process of finding the largest (or smallest) element in a list. In selection sort, this involves iterating through the unsorted portion and comparing each element to the current 'maximum' (or 'minimum').

In selection sort, after finding the maximum element in the unsorted portion of the list, it is swapped with the element at the end of the unsorted portion.

The inner loop of the selection sort algorithm repeatedly compares elements to find the maximum (or minimum) value. It runs for one fewer iteration than the size of the unsorted portion.

The total time complexity of selection sort is O(n^2), where n is the size of the array. This means that the number of operations grows quadratically with the size of the input.

The process of comparing adjacent elements in the list and swapping them if they are out of order. This is the core operation in bubble sort.

A variation of Bubble Sort that introduces a flag to check if any swaps have occurred in an iteration of the inner loop. If no swaps occur, the array is sorted, and the algorithm terminates early.

The number of times adjacent elements are compared and swapped in an iteration of the inner loop of Bubble Sort, representing the cost of sorting.

The complexity of a sorting algorithm, indicating how the runtime grows with the input size. For Bubble Sort, it's O(n^2), meaning the time increases quadratically relative to the number of elements in the array.

The outer loop in Bubble Sort iterates through the unsorted portion of the array, processing elements one at a time. Each iteration of the outer loop decreases the size of the unsorted subarray.

Part of the Bubble Sort algorithm, the inner loop compares and swaps adjacent elements within a section of the array. It repeatedly moves the largest (or smallest) element to the end of the unsorted subarray.

A measure of how efficient an algorithm is in terms of the number of operations required. A high time complexity indicates the algorithm takes longer to complete, especially for larger input sizes.

A method used to analyze the growth rate of an algorithm's runtime as the input size increases. Big O notation provides a general understanding of an algorithm's efficiency.

The base case in merge sort, indicating an array with zero or one element is already sorted, thus no further sorting is needed.

The process of combining two sorted subarrays into a single sorted array in merge sort.

A temporary array used to store the result of merging two sorted subarrays in merge sort, ensuring that the original array remains intact during the merging process.

A process that repeatedly splits the input array into halves until each subarray contains only one element (the base case), then merges the sorted subarrays until the entire array is sorted.

The core logic of merge sort where the recursive calls to mergeSort() for the left and right halves of the array, followed by the merge() operation to combine the sorted halves, resulting in a completely sorted array.

The time complexity of merge sort, indicating its efficiency in sorting regardless of the input array's initial order.

The space complexity of merge sort, reflecting the amount of memory used during sorting, which depends on the temporary array used for merging.