- Show, in the style of the example trace with Algorithm 2.1, how selection sort
ID: 665007 • Letter: #
Question
- Show, in the style of the example trace with Algorithm 2.1, how selection sort
sorts the array E A S Y Q U E S T I O N.
public class Selection
{
public static void sort(Comparable[] a)
{ // Sort a[] into increasing order.
int N = a.length; // array length
for (int i = 0; i < N; i++)
{ // Exchange a[i] with smallest entry in a[i+1...N).
int min = i; // index of minimal entr.
for (int j = i+1; j < N; j++)
if (less(a[j], a[min])) min = j;
exch(a, i, min);
}
}
// See page 245 for less(), exch(), isSorted(), and main().
}
- Show, in the style of the example trace with Algorithm 2.2, how insertion sort
sorts the array E A S Y Q U E S T I O N.
public class Insertion
{
public static void sort(Comparable[] a)
{ // Sort a[] into increasing order.
int N = a.length;
for (int i = 1; i < N; i++)
{ // Insert a[i] among a[i-1], a[i-2], a[i-3]... ..
for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
exch(a, j, j-1);
}
}
// See page 245 for less(), exch(), isSorted(), and main().
}
- Which method runs faster for an array with all keys identical, selection sort or
insertion sort?
- Which method runs faster for an array in reverse order, selection sort or insertion
sort?
- Suppose that we use insertion sort on a randomly ordered array where elements
have only one of three values. Is the running time linear, quadratic, or something in
between?
Explanation / Answer
1. It will start with
E A S Y Q U E S T I O N
A E S Y Q U E S T I O N
A E E Y Q U S S T I O N
A E E Y I U S S T Q N
and similarly it will continue
Insertion on the other hand will continue on each tranversal and will compare with other objects.
It will be insertion sort as all are identical.It will be done in O(1)
It will be selection sort as it is very easy to sort the array and it wll be done in one go.
This should take quadratic time (time (n2)). Take just the elements in the back third of the array. About a third of these elements will be 1's, and in order to insert them into the sorted sequence they'd need to be moved above 2/3's of the way down the array. Therefore, the work done would be at least (n / 3)(2n / 3) = 2n2 / 9, which is quadratic.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.