Sorting & Searching

Sorting & Searching

SUB TOPICS :

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

       }

}

Merge Sort

•       Merge Sort is a sorting algorithm based on the divide-and-conquer algorithm

•       Divide-and-conquer is a general algorithm design paradigm

–      Divide: divide the input data in two disjoint subsets

–      Recur: solve the sub problems associated with subsets

–      Conquer: combine the solutions for each subset into a solution

Searching

•       We’ll often work with large amounts of data stored in arrays

•       It may be necessary to determine whether an array contains a value that matches a certain key value

•       The process of finding a particular element of an array is called searching

•       Searching is an action to retrieve information based on particular key from some saved information

•       Key is used to do record searching which is desired from a set of data list

•       Key must be unique, means there must not be any same key in the data

•       Example:

                Student data consists of name, nim, gender, address, place and date of birth

                nim is used as key from the data, as it is unique.

•       Several types of searching algorithm:

–      Linear Search

–      Binary Search

–      Interpolation Search

Linear Search

•       Linear search compares each element of the array with the search key.

•       Since the array is not in any particular order, it’s just as likely that the value will be found in the first element as in the last

•       On average, therefore, the program will have to compare the search key with half the elements of the array

Binary Search

•       The linear searching method works well for small or unsorted arrays. However, for large arrays linear searching is inefficient

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

Interpolation Search

•       Interpolation search technique is performed on the sorted data

•       This searching process is almost similar with binary search technique

•       Searching technique is done with the approximate location of the data

•       Example:

•       If we want to find a name in the phone book, for example the one beginning with the letter T, then we would not look for from the beginning of the book, but we opened it at 2/3 or ¾ of the book.

   Summary

•       Sorting type:

•       Ascending

•       Descending

•       Simple sorting algorithms:

•                       Bubble sort

•                       Selection sort

•                       Insertion sort

•       Intermediate sorting algorithms:

•                       Quick Sort

•                       Merge Sort

•       The process of finding a particular element of an array is called searching

•       Searching is an action to retrieve information based on particular key from some saved information

•       Several types of searching algorithm:

•       Linear Search

•       Binary Search

•       Interpolation Search 

2201760945

Skyconnectiva

Kevin Orlando Sutanto