1

I am testing the run times of insertion sort using iterative and recursive functions.

However, my results are showing that the iterative version is taking longer to sort than the recursive version. Is this correct?

    // Used to determine how long a sort took
    private long startTime, stopTime;
    public int[] recursiveSort(int[] list){
        // Start the clock
        this.startTime = System.nanoTime();
        int n = list.length;
        insertionSortRecursive(list, n);
        // Stop the clock
        this.stopTime = System.nanoTime();
        return list;
    }

    public void insertionSortRecursive(int[] arr, int n){
        // Base case
        if (n <= 1)
            return;

        // Sort first n-1 elements
        insertionSortRecursive( arr, n - 1 );

        // Insert last element at its correct position in sorted array.
        int last = arr[n - 1];
        int j = n - 2;

        // Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position.
        while (j >= 0 && arr[j] > last){
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = last;
    }

My iterative version is below. I have run a test 50 of random array of size 3000, and for all of them, the time it took to sort the array recursively took less time than iteratively.

public int[] iterativeSort(int[] list){
    // Start the clock
    this.startTime = System.nanoTime();

    int n = list.length;

    for (int i = 1; i < n; ++i){
        int key = list[i];
        int j = i-1;

        /* Move elements of list[0..i-1], that are greater than key, to one position ahead of their current position */
        while (j >= 0 && list[j] > key){
            list[j + 1] = list[j];
            j = j - 1;

        }
        list[j + 1] = key;
    }

    // Stop the clock
    this.stopTime = System.nanoTime();
    return list;
}
nabeelh21
  • 53
  • 12
  • https://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping This link will answer your question related to performance. – Swrov Haque Feb 03 '18 at 22:47
  • 1
    Sounds like your testing methods are off. I did add a test to this and it shows that the iterative version is between 3-7 times faster than the recursive. Are you sure you are not passing the same array to both methods instead of 2 different copies because then whatever version you use second time around will be sorting an already sorted array? – Sylwester Feb 03 '18 at 23:04
  • Thanks, I will double check. I think that might have been the case., – nabeelh21 Feb 04 '18 at 19:17

0 Answers0