Sorts

Question 1

Insertion

Answer 1

The insertion sort
algorithm sorts a list
of values by
repeatedly inserting
an unsorted element
into a sorted sublist
until the whole list
is sorted

Question 2

Merge

Answer 2

Let T(n) denote the time required for sorting an
array of n elements using merge sort. Without loss
of generality, assume n is a power of 2. The merge
sort algorithm splits the array into two subarrays,
sorts the subarrays using the same algorithm
recursively, and then merges the subarrays

Question 3

Quick sort

Answer 3

Quick sort, developed by C. A. R. Hoare (1962),
works as follows: The algorithm selects an element,
called the pivot, in the array. Divide the array into
two parts such that all the elements in the first part
are less than or equal to the pivot and all the
elements in the second part are greater than the
pivot. Recursively apply the quick sort algorithm to
the first part and then the second part.

Question 4

Bucket Sort

Answer 4

The bucket sort algorithm works as follows.

Assume
the keys are in the range from 0 to N-1. We need N
buckets labeled 0, 1, …, and N-1.

If an element’s key
is i, the element is put into the bucket i.

Each bucket
holds the elements with the same key value.

You can
use an ArrayList to implement a bucket.

Question 5

Why sorting

Answer 5

Sorting is a classic subject in computer science. There are three
reasons for studying sorting algorithms.
1. Sorting algorithms illustrate many creative approaches
to problem solving and these approaches can be applied
to solve other problems.
2. Sorting algorithms are good for practicing fundamental
programming techniques using selection statements,
loops, methods, and arrays.
3. Sorting algorithms are excellent examples to
demonstrate algorithm performance.