INSERTION IN ARRAY AT BEGINNING AND END

ALGORITHM FOR INSERTION IN ARRAY AT BEGINNING AND END:

INSERT_BEG(LA,LB,UB,ITEM): Here LA is a linear array with lower bound LB and upper bound UB. This algorithm insert an element ITEM at the beginning of the linear array LA.

1. Set I = UB
2. Repeat steps 3 and 4 while I >= LB
3. Set LA[I+1] = LA[I]
4. Set I = I-1
5. Set LA[LB] = ITEM
6. Set UB = UB+1
7. Exit

INSERT_END(LA,LB,UB,ITEM): Here LA is a linear array with lower bound LB and upper bound UB. This algorithm insert an element ITEM at the end of the linear array LA.

1. Set I = UB
2. Set I = I+1
3. Set LA[I] = ITEM
4. Set UB=UB+1
5. Exit 

ALGORITHM FOR BINARY SEARCH

ALGORITHM FOR BINARY SEARCH IN AN ARRAY:

In Binary searching,firstly the array is divided into two halves then the element to be searched for is searched in the first half if the element is lesser than the middle element of the array. Otherwise second half is searched for the element.This binary division is continued to the half in which searching is being done and until we find the element. If element is found then algorithm returns a true value otherwise  it returns a false value.
NOTE: For binary searching the array should be sorted in an order.

BINARY(A,LB,UB,ITEM,LOC): Here A is an sorted array with lower bound LB and upper bound UB and ITEM is a given item of information. The variables BEG, END and MID denote, respectively, the beginning,end and middle locations of a segment of DATA. This algorithm finds the location LOC of ITEM in DATA or sets LOC=NULL.

1. Set BEG=LB,END=UB and MID=INT((BEG+END)/2)
2. Repeat Steps 3 and 4 while BEG<=END and
                  A[MID]!= ITEM
3. If ITEM < A[MID]  then
             Set END= MID-1
    Else
              Set BEG= MID+1
  [End of If structure]
4. Set MID = INT((BEG+END)/2)
      [End of Step 2 loop]
5.If A[MID]=ITEM then
        Set LOC=MID
   Else
        Set LOC=NULL
[End of If structure]
6. Exit.

ALGORITHM FOR MERGING OF LINEAR ARRAYS

ALGORITHM FOR MERGING OF LINEAR ARRAYS:
Merging: Merging is the operation of combining the elements of two linear arrays into a single array. The single array created after merging should have enough memory to accommodate all the elements of both the arrays.
Merging is done in sorted and unsorted arrays.

Algorithm for merging two unsorted linear arrays:
           MERGE_UNSORT(A,M,Q,N): Here A is an array with M elements and Q is an array with N elements and R is an array with L elements such that L=M+N.
 1.Repeat for I=1 to M
          R[I]=A[I]
          [End of loop]
2. Set K=1
3. Repeat for J=M+1 to M+N
          Set R[J]=Q[K]
          K=K+1
          [End of loop]
4.Exit.


Algorithm for merging two sorted arrays:
          MERGE_SORTED(A,M,Q,N):  Here A is an array with M elements and Q is an array with N elements and R is an array with L elements such that L=M+N.
1.Set I=J=1
2.Repeat while (I<=M And J<=N)
3. If A[I]<Q[J] then
           R[K]=A[I]
           I=I+1
          J=J+1
4. Else
      R[K]=Q[J]
      J=J+1
5. K=K+1
   [End of If structure ]
   [End of step 2]
6. If   I=M+1  then
       Repeat while J<=N
             R[K]=Q[J]
              K =K+1
             J=J+1
7.If J=N+1 then
          Repeat while I<=P
           R[K]=A[I]
           K=K+1
            I=I+1
            [End of If structure]
8. Exit

ALGORITHMS FOR DIFFERENT OPERATIONS ON ONE-DIMENSIONAL ARRAY

ALGORITHMS FOR DIFFERENT OPERATIONS ON ONE-DIMENTIONAL ARRAYS:

1. Algorithm for traversing an array:

TRAVERSE(A,UB,LB): Here A is a linear array with LB as lower bound and UB as upper bound. This algorithm traverses A applying an operation PROCESS to each element of A.

   Step 1: Set K:=LB

   Step 2: Repeat Steps 3 and 4 while K<=UB

   Step 3: Apply PROCESS to A[K]

   Step 4: Set K:=K+1

   Step 5: Exit.

2. Algorithm for insertion in an array:

INSERT(A,N,K,ITEM): Here A is a linear array with N elements, K is a positive integer such that K<=N. This algorithm inserts an element ITEM into the Kth position in A.

   Step 1:Set J:=N

   Step 2: Repeat Steps 3 and 4 while J>=K

   Step 3:Set A[J+1]:=A[J]

   Step 4: Set J:= J-1

              [End of step 2]

   Step 5: Set A[K]:=ITEM

   Step 6: N:=N+1

   Step 7: Exit

3. Algorithm for deletion in an array:

DELETE(A,N,K,ITEM): Here A is a linear array with N elements and K is a positive integer such that K<=N. This algorithm deletes the Kth element from A.

   Step 1: ITEM:=A[K]

   Step 2: Repeat for J:=K to N-1

               Set A[J]:= A[J+1]

                 [ End of loop]

   Step 3: Set N:=N-1

   Step 4: Exit

SORTING

SORTING:
                 Sorting is the process of arranging the elements in some logical order. This logical order may be ascending or descending in case of numeric value.

Sorting can be classified into following categories on the basis of where the data is sorted:

1. Internal Sorting: An internal sort is any data sorting process that takes place entirely within the main memory of a computer. It is independent of time to read/write a record.
2. External Sorting: External sorting uses secondary memory. It can take large input and deals with some sorting the data stored in data files. When the volume of data to be sort is very large and cannot be held in computer main memory, then external sorting is used.

Classification of Sorting techniques:

1.Sorting by insertion: The items are considered one at a time and each new item is inserted into the appropriate position relative to the previously sorted items. The technique which follows this category is insertion sort.

2.Sorting by exchanging: If two items are found to be out of order they are interchanged. This interchanging process is repeated until no more exchanges are necessary. The technique which follows this category are:

• Shell sort
• Bubble sort
• Quick sort.

3.Sorting by selection: First the smallest (or largest) item is located and it is somehow separated from the rest then the next smallest (or next largest) is selected and so on. The techniques which follows this category are:

• Selection sort
• Heap sort.

4.Sorting by merging: Merging operation combines two or more ordered list into a single ordered list. The technique which follows this category is Merge Sort.

5.Sorting by distribution:  These methods were used to sort punched cards for many years before electronic computers existed. The distribution is based on the digit of the category is Bucket Sort (Radix Sort).