Sorting Algorithms

A sorting algorithm that repeatedly finds the smallest element in the unsorted portion of a list and swaps it with the first element in that portion.

A function that takes a list and a starting index as input and returns the index of the smallest element in the list from that starting index onwards.

A sorting algorithm that iterates through the list, inserting each element into its correct position within the already sorted portion.

The part of the list that has already been sorted.

The remaining portion of the list that hasn't been sorted yet.

The algorithm compares the current element with the elements to its left, swapping them until the current element is in the correct position.

The process of exchanging the positions of two elements in a list.

The ability to compare elements in a list and determine their order.

A function that inserts an element (key) at index i into a partially sorted list (xs), ensuring the elements from index 0 to i are sorted.

A recursive sorting algorithm that follows the divide-and-conquer strategy. It divides a list into two halves, sorts them independently, and then merges the sorted halves.

The process of combining two sorted lists into a single sorted list.

Two sorted sequences are combined into a single sorted sequence, resulting in a completely sorted list.

The list is divided into two sub-sequences of approximately equal size.

A metaphor used to illustrate the merge process where two sorted bunches of books are combined into a single sorted bookshelf.

The function merge takes two sorted lists (left and right) and merges them into a single sorted list stored in zs. It requires that the lengths of the left, right, and zs lists add up to the total length of the original list.

A method to combine two sorted lists into one sorted list by repeatedly comparing the first elements of each list and placing the smaller element into the merged output list.

A recursive sorting algorithm that splits the input list into two halves, sorts each half recursively, and then merges the sorted halves using a merge function.

A recursive sorting algorithm that selects a pivot element from the input list, partitions the list around the pivot (elements smaller than the pivot go to the left, elements larger go to the right), recursively sorts the sublists on either side of the pivot, and finally concatenates the sorted sublists with the pivot element in the correct order.

The element chosen to divide the input list during the quicksort algorithm. Elements smaller than the pivot are placed to the left, and larger elements to the right.

The process of dividing the input list into two sublists during the quicksort algorithm: one sublist containing elements smaller than the pivot and the other containing elements larger than the pivot.

The process of combining the sorted sublists and the pivot element in the correct order to create the final sorted list in the quicksort algorithm.

The process of repeatedly splitting a list into smaller lists in the mergesort algorithm, eventually leading to lists with only one element each.

The process of combining sorted sublists into larger sorted lists in the mergesort algorithm by repeatedly comparing elements and merging them into the output list.

The part of memory used for local variables. It provides fast access but has limited space.

The part of memory used for dynamic allocation. It has a larger space than the stack but access is slower. Most objects reside here.

The part of memory used for global variables. These variables exist throughout the program's lifetime.

The part of memory containing the compiled machine code of the program. Algorithms and instructions are stored here.

A technique where a function calls itself. It's useful for solving problems that can be broken down into smaller, self-similar subproblems.

A sorting algorithm that uses a pivot element to divide a list into two sub-lists, one containing elements less than the pivot and the other containing elements greater than or equal to the pivot. The sub-lists are then recursively sorted using quicksort.

The process of dividing a list into two sub-lists based on a pivot element. In quicksort, this is achieved by placing all elements less than the pivot to the left and all elements greater than or equal to the pivot to the right.

The recursive step in quicksort where the two sub-lists created after partitioning are sorted using quicksort. This process continues until the sub-lists are small enough to be directly sorted.

A property of sorting algorithms where the relative order of elements with equal values remains unchanged after sorting. For example, if a list contains two identical values, those values should maintain their original order after sorting.

A sorting algorithm where the order of equal-valued elements may change after sorting. For example, if a list contains two identical values, their positions may change after sorting.

A sorting algorithm that uses a recursive approach to repeatedly divide the list into sub-lists and sort each sub-list independently. The sorted sub-lists are then merged to produce a final sorted list. Examples include quicksort and mergesort.

A sorting algorithm is considered stable if elements with the same value maintain their original relative order in the sorted output. In other words, if two equal elements are present in the input, they will remain in the same sequence in the sorted output.

The Selection Sort algorithm is not stable because it repeatedly finds the minimum element and swaps it to the front. This process can disrupt the relative order of elements with the same value.

The Insertion Sort algorithm is stable because, when moving elements to the left, it only shifts them as long as they are strictly smaller than the element being inserted. This ensures elements with the same value stay in their original order.

The Merge Sort algorithm is stable because, during the merge process, when comparing two equal elements, it prioritizes the element from the left half. This ensures elements with the same value remain in their original order.

The Quick Sort algorithm is not stable because it involves swapping the pivot element, which can change the relative order of elements with the same value.

An in-place sorting algorithm uses a constant amount of additional memory regardless of the input size. This means the memory usage doesn't increase significantly with larger input lists.

An out-of-place sorting algorithm requires additional memory space that depends on the size of the input list. This means the memory usage increases as the input grows.

Recursive algorithms can appear to be in-place, but they often create additional memory overhead due to the function call stack. Each recursive call requires memory to store its parameters, local variables, and the call stack.