Sorting & Searching

Sub Topics

Sorting & Searching:

–Bubble Sort

–Selection Sort

–Insertion Sort

–Quick Sort

–Merge Sort

– Linear Search

– Binary Search

– Interpolation Search

 

Sorting

•Sorting needs to speed up searching operation in a list.

•Sorting type:

–Ascending

–Descending

Sorting algorithm:

1. Internal sorting

    All data to be sorted are loaded to RAM

2. External sorting

    Sorting process using secondary storage

•Simple:

–   Bubble sort

–  Selection sort

–  Insertion sort

•Intermediate:

–   Quick Sort

  Merge Sort

Bubble Sort

•Compare two neighboring values.

•Compare and swap (if necessary)

•Also known as exchange sort

•Source Code of Bubble Sort:

void Bubble(int *DataArr, int n)

{

    int i, j;

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

    for(j=n-1; j>=i; j--)

    if(DataArr[j-1] > DataArr[j])

               Swap(&DataArr[j-1],&DataArr[j]);

}

 

 

Selection Sort

Algorithm:

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

Algorithm:

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

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

}

 

 

 

Quick Sort

Algorithm:

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);

       }

}