Why is Bubble/Selection/Pancake Sort faster when testing it with unsorted values?

Question

I have read in many places that the best case for those algorithms is when the array is already sorted and so making the program run them faster. For some reason, When I test the algorithms with unsorted and the same but sorted values, they run faster in the first case. Why?

This is the code for bubble sort:

// ----------------- (1) Bubble Sort -----------------------------
        // Unsorted
        long startTime11 = System.nanoTime();
        Sorting.bubbleSort(wordsToSort);
        long endTime11 = System.nanoTime();
        long timeLapsed11 = endTime11 - startTime11;
        // Already sorted
        long startTime12 = System.nanoTime();
        Sorting.bubbleSort(wordsToSort);
        long endTime12 = System.nanoTime();
        long timeLapsed12 = endTime12 - startTime12;
        // formats time with commas
        String formated11 = formatter.format(timeLapsed11);
        String formated12 = formatter.format(timeLapsed12);

bubbleSort method:

private static void bubbleSort(String[] arr, int n) {

        for (int i = 0; i < n - 1; ++i)
        {
            for (int j = 0; j < n - i - 1; ++j)
            {
                if (arr[j + 1].compareTo(arr[j]) < 0)
                {
                    String temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

CPU Time:

Unsorted: 11, 372, 240, 025, 900 nanoseconds.

Sorted: 22, 020, 911, 806, 900 nanoseconds.

The array has more than 600,000 elements in it.

More case results:

Test two of the array of +600000 elements:

Unsorted: 11, 392, 317, 750, 900 nanoseconds.

Sorted: 22, 024, 687, 559, 200 nanoseconds.

---

Array of 15000 words:

Unsorted: 1, 407, 057, 900 nanoseconds.

Sorted: 1, 650, 519, 600 nanoseconds.

Unsorted: 1, 430, 736, 200 nanoseconds.

Sorted: 1, 645, 250, 000 nanoseconds.

---

Array of 15000 words (Warmup phase added; advised from the comments)

Unsorted: 1, 453, 011, 900 nanoseconds.

Sorted: 1, 660, 550, 800 nanoseconds.

Unsorted: 2, 025, 017, 800 nanoseconds.

Sorted: 2, 466, 999, 700 nanoseconds.

---

Array of 2500 words

Unsorted: 44, 016, 900 nanoseconds.

Sorted: 20, 703, 300 nanoseconds.

Unsorted: 47, 074, 400 nanoseconds.

Sorted: 36, 121, 700 nanoseconds.

---

Array of 600 words

Unsorted: 7, 104, 600 nanoseconds.

Sorted: 1, 392, 100 nanoseconds.

Unsorted: 7, 144, 500 nanoseconds.

Sorted: 1, 324, 600 nanoseconds.

---

Here is the code with some txt files to test them and know better how to answer: https://github.com/Obed-Padilla/Sorting-algorithms

Answer 1

Given the long runtimes of 3 and 6 hours, I see two possible interesting explanations:

1. You always compare neighbor elements. When the array is unsorted, neighbor strings likely already differ at the first character, which makes the comparisons fast. When the array is sorted, neighbor strings likely share a common prefix, which makes comparisons slower.

2. You created the string objects in unsorted order, for example reading a file of unsorted strings into memory. I'm not much familiar with Java, but I suspect it does create them mostly sequentially in memory. So at the start, going through the strings in array order accesses the memory sequentially, which is cache-friendly. But then the sorting changes the array order. So going through the strings of the sorted array accesses the memory "randomly", which is cache-unfriendly.

Update after your question update with the additional timings and link to code/data: Both of the above reasons apply, although I suspect the cache one is the main one. Your timings show that with fewer and fewer words, the "sorted" case gets better and better compared to the "unsorted" case. That's expected, as for small inputs, more/everything fits in caches, and common prefixes are short (unless you choose similar words, but you didn't), so those two disadvantages of "sorted" go away. And the "unsorted" case still suffers from having to do the swap work and from branch prediction failures, making it slower than "sorted" when "sorted" doesn't have its disadvantages anymore. Also see Why is processing a sorted array slower than an unsorted array? as well as Why is processing a sorted array faster than processing an unsorted array? (Note that one says slower and the other says faster, and both are correct, for different usages and reasons).

I was able to reliably reproduce the "unsorted" case being faster than the "sorted" case (1.2 seconds vs 2.0 seconds, doing five rounds and ignoring the first round for warmup) with 10000 artificially created strings of 100 characters each. Still hoping that you'll share more infos about your data and runnable complete code, but (see update paragraph above) I think the above aspects are interesting anyway.

Sample benchmark results:

unsorted 1.263458034
sorted   1.985379993

unsorted 1.115940408
sorted   1.830749365

unsorted 1.157192938
sorted   2.175659597

unsorted 0.950845856
sorted   1.712224688

unsorted 1.243945757
sorted   1.979670624

Code (Attempt This Online!):

import java.util.*;

public class Main {

  public static void main(String[] args) {
    for(int j=0; j<5; j++){
        int n = 10000;
        String[] wordsToSort = new String[n];
        for (int i=0;i<n;i++)
            wordsToSort[i] = (""+new Character((char)(i%26+65))).repeat(100)+i;

        long start = System.nanoTime();
        bubbleSort(wordsToSort, n);
        System.out.println("unsorted " + (System.nanoTime() - start) / 1e9);

        start = System.nanoTime();
        bubbleSort(wordsToSort, n);
        System.out.println("sorted   " + (System.nanoTime() - start) / 1e9 + "\n");
    }
  }

    private static void bubbleSort(String[] arr, int n) {

        for (int i = 0; i < n - 1; ++i)
        {
            for (int j = 0; j < n - i - 1; ++j)
            {
                if (arr[j + 1].compareTo(arr[j]) < 0)
                {
                    String temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}

Answer 2

Aren't you using the same array in the variable field by the function ? same variable ?.

This may have to do with machine load . Usually , your machine may spend different amount of CPU cycles on each task , and perfoming certain task may push the priority for the execution down a bit , which lead to some delay .

If you perform raw execution of each algorithm around 50 times , the difference is uncanny on recorded time.