Sorting — Important Questions

Finds the smallest element in each pass, Divides list into sorted and unsorted parts, Requires n-1 passes for n elements

Selection sort finds the minimum element in each pass, maintains sorted and unsorted portions, and needs n-1 passes. It doesn't only compare adjacent elements like bubble sort.

Bubble sort, Selection sort

Bubble sort works by repeatedly comparing adjacent elements and swapping them if they are unordered. Selection sort also uses swapping: after finding the smallest element in the unsorted part, it is swapped with the leftmost element of that unsorted list. Insertion sort mainly inserts an element into its correct position by shifting elements, so it is not described here as a swapping method.

Because large elements 'bubble up' to their correct position

It's called bubble sort because the largest elements gradually 'bubble up' to the end of the list in each pass, similar to air bubbles rising to the surface in water.

Quadratic time

Algorithms with nested loops have quadratic time complexity because the inner loop runs n times for each of the n iterations of the outer loop, giving n² operations.