Sieve of Eratosthenes algorithm: Efficient way to find prime numbers

First, lets find prime numbers in following manner, which tries to divide each number, say n, by each integer i, where 2<= i <= n/2.

Below code finds the prime numbers between 2 and 10,00,000.

    private static void findPrime() {
        int count = 0;
        int num = 1000000;
        for (int i = 2; i <= num; i++) {
            count = 0;
            for (int j = 2; j <= i / 2; j++) {
                if (i % j == 0) {
                    count++;
                    break;
                }
            }
            if (count == 0) {
                System.out.println(i);
            }
        }
    }

Above code took 64 seconds (64,575 msecs) when executed on my machine.

Now following is the Java implementation of Sieve of Eratosthenes algorithm to find prime numbers.
It assumes each number to be prime and then tries to eliminate the non-prime ones. Below is the java implementation:

    public static void findPrimeBySieve() {
        int num = 1000000;
        // initially assume all integers are prime
        boolean[] isPrime = new boolean[num + 1];
        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i * i <= num; i++) {

            // if i is prime, then mark multiples of i as nonprime
            // suffices to consider mutiples i, i+1, ..., N/i
            if (isPrime[i]) {
                for (int j = i; i * j <= num; j++) {
                    isPrime[i * j] = false;
                }
            }
        }

        // count primes
        int primes = 0;
        for (int i = 2; i <= num; i++) {
            if (isPrime[i]){
                System.out.println(i);
                primes++;
            }
        }
        System.out.println("The number of primes <= " + primes);
    }

Execution time of above code was only 0.5 seconds (529 msecs) on my machine, i.e., 128 times faster for finding prime numbers between 2 and 1000000.

Hope you liked the post. Connect at +Java Territory  to stay tuned with latest updates.

Read More

Optimizing Bubble Sort Algorithm

Having been in Java world for around 5 years, I believe Bubble Sort is the probably simplest and widely used sorting algorithm that works by repeatedly swapping the adjacent elements if they are not in the right order. However, with just a little tweaking, it’s possible to make it more efficient. So, we will first see what Bubble Sort algorithm is and then move to its optimization part.

To sort the entire array, the array is traversed n-1 time (array having n elements). These are called passes. In the first pass the largest element moves to the last position (sorting in ascending order). So if the original (unsorted) array is:

55           33           99           77           44

During the first iteration, adjacent elements will be compared, and swapped if larger element is on left side), as shown below:

After first iteration, the largest element is at the last position.

33          55        77          44         99

Now, in the 2nd pass, we will consider the first (n-1) elements only (because last position already has largest element). After 2nd pass the array will be

33           55           44           77           99

i.e., 77 will be moved to the (n-1)th position. 

After (n-1) iterations, (n-1) elements will be moved to their proper positions, the last element has to be the smallest. So the array will be sorted after n-1 passes.

Algorithm:

void bubbleSort(int array[], int n) {

       for (int i = 0; i < n; i++) {

              for (int j = 0; j < n - i - 1; j++) {

                     if (array[j] > array[j + 1]) {

                           int temp = array[j + 1];

                           array[j + 1] = array[j];

                           array[j] = temp;

                     }

              }

       }

}

Time Complexity: O(n*n)

Auxiliary Space: O(1)

Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.

Sorting In Place: Yes

Stable: Yes

Improvement (Optimization):

In the above example, the array got sorted after 2nd pass, but we will still continue with the 3rd, 4th pass. Suppose if the array is already sorted, then there will be no swapping (because adjacent elements are always in order), but still we will continue with the passes and there will still be (n-1) passes.

If we can identify, that the array is sorted, then we should stop execution of further passes. This is the optimization over the original bubble sort algorithm.

If there is no swapping in an iteration pass, it means the array has become sorted, so algorithm should be smart enough to skip further iterations.

For this we can have a flag variable which is set to true before each pass and is made false when a swapping is performed.

void optimizedBubbleSort(int array[], int n) {

       for (int i = 0; i < n; i++) {

              boolean flag = true;

              for (int j = 0; j < n - i - 1; j++) {

                     if (array[j] > array[j + 1]) {

                           flag = false;

                           int temp = array[j + 1];

                           array[j + 1] = array[j];

                           array[j] = temp;

                     }

              }

              // No Swapping happened, array is sorted

              if (flag) {

                     return;

              }

       }

}

For the best case (array already sorted) the optimized algorithm will be O(n).

For average case also, the performance will see an improvement. Whereas the original algorithm was O(n²) for all the cases.

Read More

Java 8: Arrays.parallelSort()

In this post, we will discuss about new sorting API for Arrays introduced in JAVA 8, Arrays.parallelSort().

Java 8's parallel sort API uses a split-sort-merge concept to sort the arrays. The input array is broken into multiple sub-arrays that are sorted themselves and then finally merged resulting into a complete sorted array. The algorithm uses a threshold value and any array of size lesser than the threshold value is sorted using the appropriate Arrys.sort method. The algorithm requires a working space no greater than the size of the original array.

Read More

How String's substring function can cause memory leak in Java 6??

Hi friends, this is my first post on Java Insight blog. Hopefully this would be of little help to you.

Lets start off with String class, most widely used Java class may be.

We all use String's substring method so frequently while programming, but have you ever given a thought of how it works. How memory is managed? Can it lead to memory leaks? Truly speaking, I never had, until I stayed whole night in office debugging an application for memory leaks.

Enough of intro to engage you further I guess, so lets jump straightaway into action.

Read More