Sorting algorithms

These flashcards cover key concepts surrounding elementary sorts, including selection sort, insertion sort, and various principles in sorting algorithms.

What is the purpose of sorting algorithms?

To rearrange an array of items in a particular order, usually ascending.

What are the two basic types of elementary sorting algorithms discussed?

Selection sort and insertion sort.

What is a key characteristic of a total order in sorting?

It must satisfy antisymmetry, transitivity, and totality.

How does selection sort operate?

It iteratively finds the minimum element from the unsorted part and swaps it with the first unsorted element.

In insertion sort, what does each iteration aim to do?

It moves the current element to its correct position among previously sorted elements.

Define 'inversion' in the context of sorting.

A pair of keys that are out of order.

What is the time complexity of selection sort in the average case?

O(n^2).

Why is insertion sort faster than selection sort on average for small datasets?

Because it makes fewer comparisons and moves elements only when necessary.

What type of array does insertion sort run in linear time on?

Partially sorted arrays.

What is a comparator?

An object that defines a sort order for sorting algorithms.

What characteristic makes insertion sort a stable sorting algorithm?

Equal items do not move past each other during sorting.

Why is selection sort not considered stable?

It can move equal items past one another due to long-distance exchanges.

What improvement does shuffle sort provide?

It generates a uniformly random permutation of the array.

What is the Java method to access the compareTo function in a Comparable object?

You invoke the compareTo method defined in the Comparable interface.

How can sorting algorithms be adapted to different data types in Java?

By using generics and Comparator interfaces.

What is the outcome of applying the compare() method in a Comparator?

It should return a negative integer, zero, or a positive integer based on the comparison of two objects.

What does it mean for a sort to be 'stable'?

It preserves the relative order of records with equal keys.

Which sorting method is demonstrated to involve shifting items instead of exchanging them?

Binary insertion sort.

How can you sort music by different criteria such as artist or song name?

By implementing comparators that define the desired sort order.

What is a common application of sorting algorithms in real life?

Sorting student records by name or section.

What is a key property that a usable comparator must fulfill?

It must enforce a total order on the items being compared.