Java, NoSQL, SQL, REST API and other scary words

Most popular and simple Search and Sort algorithms

Binary Search

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].

  1. Compare x with the middle element.
  2. If x matches with middle element, we return the mid index.
  3. Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
  4. Else (x is smaller) recur for the left half.

Search an element in a sorted and rotated array

Input  : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}; key = 3

Output : Found at index 8

1) Find middle point mid = (first_element + length)/2

2) If key is present at middle point, return mid. if (arr[mid] == key) return mid;

3) Else If arr[l..mid] is sorted

  1.    a) If key to be searched lies in range from arr[l]

      to arr[mid], recur for arr[l..mid].

  1.    b) Else recur for arr[mid+1..r]

4) Else (arr[mid+1..r] must be sorted)

  1.    a) If key to be searched lies in range from arr[mid+1]

      to arr[r], recur for arr[mid+1..r].

  1.    b) Else recur for arr[l..mid]

Bubble Sort

// Optimized implementation of Bubble sort

#include <stdio.h>

 void swap(int xp, int yp)

{

    int temp = xp;  xp = *yp;   *yp = temp;

}

 // An optimized version of Bubble Sort

void bubbleSort(int arr[], int n)

{

   int i, j;  bool swapped;

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

   {

     swapped = false;   for (j = 0; j < n-i-1; j++)

     {

        if (arr[j] > arr[j+1])

        {

           swap(&arr[j], &arr[j+1]);    swapped = true;

        }

     }

      // IF no two elements were swapped by inner loop, then break

     if (swapped == false)    break;

   }

}

Insertion Sort

12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 5 (Size of input array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6

i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13

/Function to sort array using insertion sort/

    void sort(int arr[])

    {

        int n = arr.length;

        for (int i=1; i<n; ++i)

        {

            int key = arr[i];  int j = i-1;

             /* 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] > key)

            {

                arr[j+1] = arr[j];  j = j-1;

            }

            arr[j+1] = key;

        }

    }

Merge Sort

12, 11, 13, 5, 6 -> 5,6,11,12,13

We should split it into subarrays and paste back

If there are more than 1 elements in array:

  1. Find the middle point to divide the array into two halves:  

            middle m = (l+r)/2, where l – begin of the array, r is the end

  1. Call mergeSort for first half:   

            Call mergeSort(arr, l, m)

  1. Call mergeSort for second half:

            Call mergeSort(arr, m+1, r)

  1. Merge the two halves sorted in step 2 and 3:

            Call merge(arr, l, m, r)

Should be: 12,11,13; 5,6 -> 12, 11; 13; 5,6 -> 11,12;13;5,6 -> 11,12,13;5,6 -> 5,6,11,12,13

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Input: arr[] = {10, 22, 28, 29, 30, 40}, x = 54

Output: 22 and 30

1) Initialize a variable diff as infinite (Diff is used to store the

  difference between pair and x).  We need to find the minimum diff.

2) Initialize two index variables l and r in the given sorted array.

      (a) Initialize first to the leftmost index:  l = 0

      (b) Initialize second  the rightmost index:  r = n-1

3) Loop while l < r.

      (a) If  abs(arr[l] + arr[r] – sum) < diff  then

          update diff and result

      (b) Else if(arr[l] + arr[r] <  sum )  then l++

      (c) Else r–  

    // Prints the pair with sum cloest to x

    static void printClosest(int arr[], int n, int x)

    {

        int res_l=0, res_r=0;  // To store indexes of result pair

        int n = arr.length();

        // Initialize left and right indexes and difference between pair sum and x

        int l = 0, r = n-1, diff = Integer.MAX_VALUE;

          // While there are elements between l and r

        while (r > l)

        {

            // Check if this pair is closer than the closest pair so far

            if (Math.abs(arr[l] + arr[r] – x) < diff)

            {

               res_l = l; res_r = r;

               diff = Math.abs(arr[l] + arr[r] – x);

            }

              // If this pair has more sum, move to smaller values.

            if (arr[l] + arr[r] > x)

               r–;

            else // Move to larger values

               l++;

        }

      System.out.println(” The closest pair is “+arr[res_l]+” and “+ arr[res_r]);

}

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s