Sorting & Searching

Sorting and Searching

SORTING

Needs to speed up seatching operation in a list.

Sorting type : Ascending and Descending

Sorting Algorithm :

a) Internal sorting : all data to be stored are loaded to RAM

b) External sorting : sorting process using secondary storage

Simple : Bubble sort

          : Selection sort

          : Insertion sort

Intermediate : Quick sort

                 : Merge sort 

Buble Sort

Compare two neighboring values.

Compare and swap (if necessary).

Also known as exchange sort.

Selection Sort

for(i=0; i<N-1; i++){      /* N=number of data */

  Set idx_smallest equal to i

  for(j=i+1; j<N; j++){

  If array[ j ] < array [ idx_smallest ] then idx_smallest = j

    }

  Swap array[ i ] with array[ idx_smallest ]

}

Insertion Sort

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

     x = A[i], insert x to its suitable place between A[0] and A[i-1].

}

Quick Sort

void QuickSort(int left, int right)

{

      if(left < right){

            //arrange elements  R[left],...,R[right] that

            //producing new sequence:

            R[left],...,R[J-1] < R[J] and R[J+1],...,R[right] > R[J].

            QuickSort(left, J-1);

            QuickSort(J+1, right);

       }

}

Merge Sort

A sorting algorithm based on the divide-and-conquer algorithm.

Divide-and-conquer : A general algorithm design paradigm

~ Divide : Divide the input data into two disjoint subsets

~ Recur : Solve the sub problems associated with subsets

~ Conquer : Combine the solutions for each subset into a solution

SEARCHING

The process of finding a particular element of an array.

An action to retrieve information based on particular key from some saved information.

Key : Used to do record searching which is desired from a set of data list and mus be unique.

Several types of searching algorithm :

- Linear Search

Compares each element of the array with the search key.

For small or unsorted arrays.

- Binary Search

If the array sorted, the high-speed binary search technique can be used.

For large arrays.

- Interpolation Search

Performed on the sorted data. Similiar with binary search technique.

Searching technique is done with the approximate location of data