CodeChum: Sorting Algorithms

Bubble sort

______ is a simple comparison-based sorting algorithm that repeatedly steps through the list of elements to be sorted

Bubble Sort

It compares adjacent elements and swaps them if they are in the wrong order.

smaller, bubble

The algorithm gets its name because ______ elements "______" to the top of the list with each iteration.

not, large

Despite its simplicity, bubble sort is ____ very efficient for _____ lists and is mainly used for educational purposes or when dealing with very small datasets

O(n^2), number of elements

The time complexity of Bubble Sort is ______, where n is the _______ in the list.

Bubble Sort

______ is not recommended for large lists as its performance degrades quickly

O(1)

Bubble sort has a space complexity of ____ since it only requires a constant amount of additional space for temporary variables

Insertion sort

______ is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time

Insertion Sort

It takes elements from the unsorted portion of the array and inserts them into their correct positions within the sorted portion of the array

insertion sort, adaptive

Despite its simplicity, _____ is also not very efficient for large lists, but it can be more efficient than bubble sort in some cases due to its _____ nature

O(n^2)

The time complexity of Insertion Sort is _____, similar to Bubble Sort, for the worst and average cases

small, partially

Insertion sort can be more efficient than Bubble Sort in practice, especially for ____ or _____ sorted lists, due to its adaptive nature.

O(1)

Insertion sort also has a space complexity of ____ since it only requires a constant amount of additional space for temporary variables

Selection sort

_______ is a simple comparison-based sorting algorithm that divides the array into two portions: a sorted portion and an unsorted portion

Selection sort

It repeatedly finds the smallest (or largest) element from the unsorted portion and swaps it with the leftmost element of the unsorted portion

O(n^2), minimum (or maximum)

The time complexity of Selection Sort is ______, where n is the number of elements in the array. This is because, in each iteration, it needs to find the ________ element from the unsorted portion

Bubble Sort, Insertion Sort,

Similar to _______ and ________, Selection Sort is not recommended for large datasets due to its performance characteristics

Counting sort

________ is an efficient, non-comparative sorting algorithm that works by determining the number of occurrences of each distinct element in the input array

Counting sort

It creates a count array to store the frequency of each element and then uses this count information to determine the correct position of each element in the sorted output array

range of input values, number of elements

Counting sort is particularly useful when the ______ is small compared to the ________ being sorted

count array

The counting sort algorithm works by counting the occurrences of each element in the input array, storing this frequency information in a _______ and then using the _______ to determine the correct position of each element in the sorted output array

O(n+k), elements, range

The time complexity of counting sort is _______, where n is the number of ______ in the input array and k is the ______ of input values

linear

Counting sort has a _____ time complexity because it performs a constant number of operations for each element in the input array

O(k)

The space complexity of counting sort is _____ since it requires a count array of size k+1 to store the frequencies of each element

non-negative, small

Counting sort is well-suited for sorting ______ integers with a _____ range

Quick sort

______ is a highly efficient comparison-based sorting algorithm that uses a divide-and-conquer approach to sort elements

pivot

Quick sort selects a _____ element from the array and partitions the other elements into two sub-arrays, one with elements less than the pivot and the other with elements greater than the pivot

O(n log n), large

The average and best-case time complexity of Quick Sort is ______, making it highly efficient for ______ datasets

O(n^2)

The worst-case time complexity of Quick Sort can be _____ when an inefficient pivot selection occurs

O(log n)

Quick Sort has a space complexity of ______ for the recursive call stack

Merge sort

_____ is a divide-and-conquer algorithm that works by recursively dividing the input list into smaller halves, sorting them independently, and then merging the sorted halves to produce the final sorted list

Merge sort

It is an efficient sorting algorithm known for its stable sorting property and consistent performance.

O(n log n), large

The time complexity of merge sort is ______, where n is the number of elements in the input list. Merge sort has a consistent performance and is highly efficient for sorting _____ lists.

O(n)

The space complexity of merge sort is ____ since it requires additional memory to store the temporary sublists during the merging process

stable

Merge sort is a _____ sorting algorithm, meaning it preserves the relative order of equal elements

recursively, iteratively

Merge sort can be implemented _____, or ______ using a bottom-up approach

iterative

The ______ merge sort avoids the overhead of recursive function calls and can be implemented using a loop and an additional list to store the intermediate results

Merge sort

It is widely used in various applications that require efficient and stable sorting