'Why the insertion sort is slower than selection sort?
The code for selection sort in Java:
public class Selection {
public static void sort(Comparable[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i+1; j < n; j++) {
if (less(a[j], a[min])) min = j;
}
exch(a, i, min);
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
The code for insertion sort in Java:
public class Insertion {
public static void sort(Comparable[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && less(a[j],a[j-1]); j--) {
exch(a,j,j-1);
}
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
The test code to compare the speed of the two sorts:
import java.util.Random;
public class SortCompare {
public static double time(String alg, Double[] a) {
Stopwatch sw = new Stopwatch();
if (alg.equals("Insertion")) Insertion.sort(a);
else if (alg.equals("Selection")) Selection.sort(a);
else throw new IllegalArgumentException("Invalid algorithm: " + alg);
return sw.elapsedTime();
}
// Use alg to sort trials random arrays of length n.
public static double timeRandomInput(String alg, int n, int trials) {
double total = 0.0;
Random r=new Random();
Double[] a = new Double[n];
// Perform one experiment (generate and sort an array).
for (int t = 0; t < trials; t++) {
for (int i = 0; i < n; i++)
a[i] = r.nextDouble();
total += time(alg, a);
}
return total;
}
public static void main(String[] args) {
String alg1 = args[0];
String alg2 = args[1];
int n = Integer.parseInt(args[2]);
int trials = Integer.parseInt(args[3]);
double time1, time2;
time1 = timeRandomInput(alg1, n, trials); // Total for alg1.
time2 = timeRandomInput(alg2, n, trials); // Total for alg2.
System.out.printf("For %d random Doubles\n %s is", n, alg1);
System.out.println();
System.out.printf(" %.1f times faster than %s\n", time2/time1, alg2);
}
}
Below is the result:
For 1000 random Doubles
Insertion is
0.7 times faster than Selection
The helper class to measure the time:
public class Stopwatch {
private final long start;
/**
* Initializes a new stopwatch.
*/
public Stopwatch() {
start = System.currentTimeMillis();
}
/**
* Returns the elapsed CPU time (in seconds) since the stopwatch was created.
*
* @return elapsed CPU time (in seconds) since the stopwatch was created
*/
public double elapsedTime() {
long now = System.currentTimeMillis();
return (now - start) / 1000.0;
}
}
Why is the insertion sort slower than selection sort?
I see in Algorithms Fourth Edition that insertion sort is faster than selection sort and the result the book acquire is 1.7 times, but what I conclude is 0.7 or 0.8 times.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|