Reading Guide : Arrays

An array is a sequence of indexed components with the following properties :

• The length of the array is fixed when it is constructed.
• Each component has a fixed and unique index.
• Any component of the array can be accessed using its index. This is an efficient operation, having time complexity O(1).

Basic functions on arrays :

1. Insert an element

    public static void insert( int a[], int index, int num, int left, int right){
        // num : Number to be inserted at index
       // Time : O(n)
        for (int i=right; i >  index ; i--)
         a[i] = a[i-1];
        a[index] = num;
        }

2. Delete an element

public static void delete (int a[], int index, int left, int right){
       // Time : O(n)
        for(int i=index;i<right;i++)
            a[i] = a[i+1];
        a[right] = -1; // Puttin -1 for indicating null
        }

3. Find if the array is sorted

public static void isSorted(int a[]){
// Time : O(n)
 for(int i=0;i<a.length-1;i++)
    if (a[i] > a[i+1])
      return false;
return true;
}

4. Merge two sorted arrays

public static void merge( int a[], int al, int ar, int b[], int bl, int br, int c[]){
// al : a's left index ar : a's right index c: merged array
    int i= al;
    int j = bl;
    int k=0;
   
    while ( i<= ar && j <= br){
        if (a[i] <= b[j])
          c[k++] = a[i++];
        else
          c[k++] = b[j++];
    }
    while (i <= ar)
        c[k++] = a[i++];
   
    while (j <= br)
        c[k++] = b[j++];
}


Search Algorithms on arrays :

1. Linear Search

    final static int NONE = -1;
    public static int linearSearch(int a[], int target, int left, int right){
    /*
     *  Time : O(n) | Space : 1
     */
        for (int i=left;i<=right;i++){
            if(target == a[i])
                return i;
        }
        return NONE;
    }

2. Linear search on a sorted array
  
    public static int linearSearchSorted(int a[], int target, int left, int right){
        /*
         *  Time : Worst Case O(n) | Space : 1
         */
          for (int i=left;i<=right && target >= a[i];i++){
                if(target == a[i])
                    return i;
            }
            return NONE;
        }

3. Binary Search Iterative on sorted array
  
    public static int binarySearchIterative( int a[], int target ,int left, int right){
        /*
         * Time : O(log n)
         */
        while ( left <= right){
            int mid = (left + right) / 2;
           
            if ( target == a[mid])
                return mid;
            else if ( target > a[mid])
                left = mid + 1 ;
            else
                right = mid - 1 ;
        }
        return NONE;
    }

4. Binary Search Recursive on sorted array
  
public static int binarySearchRecursive( int a[], int target ,int left, int right){
       
        if ( left <= right){
            int mid = (left + right) / 2;
           
            if ( target == a[mid])
                return mid;
            else if ( target > a[mid])
                return binarySearchRecursive(a,target,left+ 1,right) ;
            else
                return binarySearchRecursive(a,target,left, mid -1 ) ;
        }
        return NONE;
    }

Sorting Algorithms on array

1. Selection sort
Find the least element in the array. Swap it to first index. Ignore the first and then find the least element in the remaining array. Repeat till end.

public static void selectionsort(int a[],int left,int right){
// Time : O(n*n)

    for (int p=left;p<=right;p++){
        int index=p;
        int min = a[p];

        for(int i=p+1;i<=right;i++)
            if(min > a[i] )
            { min = a[i];
              index = i;
             }
   
        if (p != index){
            int r = a[p];
            a[p] = min;
            a[index] = r;
        }

    }
}

2. Insertion Sort
Consider the array to be a sorted and unsorted part. Pick one element from the unsorted part and insert it into the sorted part.

public void insertionsort(int a[],int left, int right) {

for(int p=left+1;p<=right;p++)
{
   int ins = a[p];
for(k=p-1;k>=0;k++)
  if(a[k] > a[p])
   a[k+1] = a[k];

a[k] = ins;
}
}

Notes : Insertion sort is fast in-place sorting algorithm for small input sizes.

3. Quick Sort

public static void quicksort(int a[], int left, int right){

}

public static int partition (int a[], int left, int right) {

}
4. Merge Sort
This is a divide and conquer strategy. We basically divide the array into smaller arrays , sort the smaller arrays and merge them back.

public static void mergesort(int a[],int left, int right){
/*
 *  Time : O(n log n)
 *  Space : O(n)
 */
    int b[] = new int[right -left+1];
    domergesort(a,left,right,b);
}

public static void domergesort(int a[],int left,int right, int b[]){
   
    if(left < right){
        int mid = (left+right)/2;
        domergesort(a,left,mid,b);
        domergesort(a,mid+1,right,b);
        merge(a,left,mid,a,mid+1,right,b);
        for(int k=left;k<=right;k++)
            a[k] = b[k-left];
    }
}


5. Heap Sort

Other Operations on Arrays :

1. Randomize elements of array :

Permute-By-Sorting

1. n = length A
2. for i = 0 to n
3. do P[i] = Random(0,n^3)
4. Sort A using P as keys.
5. Return A

public static void permute(int a[])
{

}

Work in Progress... Sorry for the inconvenience.