Return to Answer

Example 2: Think of a telephone book

All the names are sorted. Look for ‘Johnson’ in the book. I bet it will take you less than 3 minutes. As you know where J is in the alphabet now pretend you have those same 60,000 names and phone numbers - unsorted in the same type of book, all jumbled up. no particular order now go find Johnson in the book. I bet it will take you hours! It could be on page 3, or page 349; you never know where it is.

The if condition checks that arr[i] < 5000, but if you observe in case of a sorted array, after passing the number 5000 the condition is always false, and before that, it is always true, compiler optimizes the code here and skips the if condition which is referred as branch prediction.

all the names are sorted. look for ‘johnson’ in the book. I bet it will take you less than 3 minutes. as you know where J is in the alphabet now pretend you have those same 60,000 names and phone numbers - unsorted in the same type of book, all jumbled up. no particular order now go find johnson in the book. I bet it will take you hours! as it could be on page 3, or page 349., you never know where it is.

The if condition checks that arr[i] < 5000, but if you observe in case of a sorted array, after passing the number 5000 the condition is always false, and before that, it is always true. The CPU will recognize that pattern and be able to predict correctly which instruction to execute next after the conditional branch, instead of sometimes having to rewind after guessing wrong.

All the names are sorted. Look for ‘Johnson’ in the book. I bet it will take you less than 3 minutes. As you know where J is in the alphabet now pretend you have those same 60,000 names and phone numbers - unsorted in the same type of book, all jumbled up. no particular order now go find Johnson in the book. I bet it will take you hours! It could be on page 3, or page 349; you never know where it is.

// CPP program to demonstrate processing
// time of sorted and unsorted array
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

const int N = 100001;

int main()
{
    int arr[N];

    // Assign random values to array
    for (int i=0; i<N; i++)
        arr[i] = rand()%N;

    // for loop for unsorted array
    int count = 0;
    double start = clock();
    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    double end = clock();
    cout << "Time for unsorted array :: "
        << ((end - start)/CLOCKS_PER_SEC)
        << endl;
    sort(arr, arr+N);

    // for loop for sorted array
    count = 0;
    start = clock();

    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    end = clock();
    cout << "Time for sorted array :: "
        << ((end - start)/CLOCKS_PER_SEC)
        << endl;

    return 0;
}