Sorting Algorithms Flashcards

Flashcards covering sorting algorithms, including selection sort and insertion sort.

What are some applications of sorting in data analysis?

Ranking answers to a web query, finding top scoring students, finding cheap airplane tickets, searching in a phone directory.

What is the input for the sorting problem?

A list/array of data in an arbitrary order.

What is the output for the sorting problem?

A list/array in a sorted order.

Why is sorting data fundamental to computational problems?

Ranking data, finding top X items, and enabling faster searching through binary search.

What are the basic steps of the selection sort algorithm?

Find the minimum value, add it to the sorted array, and remove it from the input array.

How does selection sort work in-place?

It finds the minimum value and moves it to the first index by swapping.

What is the invariant for selection sort correctness analysis?

At the end of phase i, the first i+1 entries of the array are sorted and contain the minimum i+1 values.

What is the worst-case time complexity of selection sort?

O(n^2)

What are the basic steps of the insertion sort algorithm?

Insert the first value into the sorted array and take the first value from the input array.

What is the invariant for insertion sort correctness analysis?

The first i+1 entries of the array are sorted (in increasing order).

What is the worst-case time complexity of insertion sort?

O(n^2)

How does insertion sort work in-place?

Inserting the values into a sorted sub-array.