-3
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;
    }
}

Above is the code for Selection 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;
    }
}

Above is the code for Insertion sort in java

import java.util.Random;
public class SortCompare {
    public static double time(String alg, Double[] a) {
        Stopwatch sw = new Stopwatch();
        if      (alg.equals("Insertion"))       Insertion2.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);
    }
}

Above is the test code to compare the speed of the two sort

Below is the result

For 1000 random Doubles

    Insertion is

 0.7 times faster than Selection

below is 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 the Insertion sort is slower than selection sort?

i see the Algorithms Fourth Edition says the Insertion sort is faster than selection sort and the result the book acquire is 1.7times.but what i conclude is 0.7 or 0.8 times

air
  • 163
  • 6
  • 5
    You [already asked this](https://stackoverflow.com/questions/72124744/why-the-insertion-sort-is-slower-than-selection-sort). You didn't need to open a different question, just to edit your original one to add the requested information. – Federico klez Culloca May 05 '22 at 12:59
  • 3
    And by the way, 1000 elements is not nearly enough to measure this kind of things. Please read [What is microbenchmarking](https://stackoverflow.com/questions/2842695/what-is-microbenchmarking) – Federico klez Culloca May 05 '22 at 13:03
  • i have edit my original one,and the result is same as when 10000 or 100000 elements – air May 05 '22 at 13:19
  • 2
    Of course you do. You're timing each single attempt instead of timing a bunch of them together, and each attempt has a ton of overhead because of all the things you're doing inside the `time` method. – Federico klez Culloca May 05 '22 at 13:24

0 Answers0