Saturday, July 26, 2014

Data Structures and Algorithms with Java - Part II (Data Structures & Algorithms)

‍ඔන්න DSA Final part එක දැන් post කරනවා ඔයාලට.....

Search Algorithms ගැන කතා කරොත් It can divided in to 2 categories

1. Linear Search
    • Small and Unsorted Arrays
    • Simple to implement but slow
     මෙහිදී array එකේ මුල සිට අවසානය දක්වා search key එක ලැබෙන තෙක් search කරයි.

Code  

//Code by me

public int linearSearch(int list[],int size,int SK){
    boolean found=false;
    int position=-1;
    int index=0;
    
    while(index<list.length && !found){
        if (list[index]==SK) {
                found = true;
                position = index;
            }
            ++index;
        }
        return position;
    }

 2. Binary Search
    • Large and sorted Arrays
   මෙහිදී array එක කොටස් 2 කට බෙදා එක් එක් කොටස නැවත නැවතත් බෙදා  වෙන වෙනම search key ලැබෙන තෙක්  search කරයි.


Code
//Code by me
public void binarySearch(int list[], int size, int SK) {
        int mid = (list.length - 1) / 2;
        boolean f = false;

        if (list[mid] > SK) {
            while (list[mid] != SK) {
                if (list[mid] == SK) {
                    ++mid;
                }

            }
        } else {
            while (list[mid] != SK) {
                --mid;
            }
        }

    }

Sort Algorithms ගැන කතා කරොත් It can divided in to 5 categories

1. Bubble sort

Code
//Referenced code
for (int x = 0; x < n; x++) {
            for (int y = 0; y < n - 1; y++) {
                if (array[y] > array[y + 1]) {
                    int temp = array[y + 1];
                    array[y + 1] = array[y];
                    array[y] = temp;
                }
            }
        }


2. Selection Sort


Code
//Referenced code
public static void selectionSort1(int[] x) {
        for (int i = 0; i < x.length - 1; i++) {
            for (int j = i + 1; j < x.length; j++) {
                if (x[i] > x[j]) {
                    //... Exchange elements
                    int temp = x[i];
                    x[i] = x[j];
                    x[j] = temp;
                }
            }
        }
    }

3. Insertion Sort


Code

//Referenced code

    public class MyInsertionSort {

        public static void main(String[] args) {

            int[] input = {4, 2, 9, 6, 23, 12, 34, 0, 1};
            insertionSort(input);
        }

        private static void printNumbers(int[] input) {

            for (int i = 0; i < input.length; i++) {
                System.out.print(input[i] + ", ");
            }
            System.out.println("\n");
        }

        public static void insertionSort(int array[]) {
            int n = array.length;
            for (int j = 1; j < n; j++) {
                int key = array[j];
                int i = j - 1;
                while ((i > -1) && (array[i] > key)) {
                    array[i + 1] = array[i];
                    i--;
                }
                array[i + 1] = key;
                printNumbers(array);
            }
        }
    }
4. Merger Sort


Code

//Referenced code
public class MyMergeSort {

        private int[] array;
        private int[] tempMergArr;
        private int length;

        public static void main(String a[]) {

            int[] inputArr = {45, 23, 11, 89, 77, 98, 4, 28, 65, 43};
            MyMergeSort mms = new MyMergeSort();
            mms.sort(inputArr);
            for (int i : inputArr) {
                System.out.print(i);
                System.out.print(" ");
            }
        }

        public void sort(int inputArr[]) {
            this.array = inputArr;
            this.length = inputArr.length;
            this.tempMergArr = new int[length];
            doMergeSort(0, length - 1);
        }

        private void doMergeSort(int lowerIndex, int higherIndex) {

            if (lowerIndex < higherIndex) {
                int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
                // Below step sorts the left side of the array
                doMergeSort(lowerIndex, middle);
                // Below step sorts the right side of the array
                doMergeSort(middle + 1, higherIndex);
                // Now merge both sides
                mergeParts(lowerIndex, middle, higherIndex);
            }
        }

        private void mergeParts(int lowerIndex, int middle, int higherIndex) {

            for (int i = lowerIndex; i <= higherIndex; i++) {
                tempMergArr[i] = array[i];
            }
            int i = lowerIndex;
            int j = middle + 1;
            int k = lowerIndex;
            while (i <= middle && j <= higherIndex) {
                if (tempMergArr[i] <= tempMergArr[j]) {
                    array[k] = tempMergArr[i];
                    i++;
                } else {
                    array[k] = tempMergArr[j];
                    j++;
                }
                k++;
            }
            while (i <= middle) {
                array[k] = tempMergArr[i];
                k++;
                i++;
            }

        }
    }

5.Quick Sort


Code
//Referenced code

    public class MyQuickSort {

        private int array[];
        private int length;

        public void sort(int[] inputArr) {

            if (inputArr == null || inputArr.length == 0) {
                return;
            }
            this.array = inputArr;
            length = inputArr.length;
            quickSort(0, length - 1);
        }

        private void quickSort(int lowerIndex, int higherIndex) {

            int i = lowerIndex;
            int j = higherIndex;
            // calculate pivot number, I am taking pivot as middle index number
            int pivot = array[lowerIndex + (higherIndex - lowerIndex) / 2];
            // Divide into two arrays
            while (i <= j) {
                /**
                 * In each iteration, we will identify a number from left side
                 * which is greater then the pivot value, and also we will
                 * identify a number from right side which is less then the
                 * pivot value. Once the search is done, then we exchange both
                 * numbers.
                 */
                while (array[i] < pivot) {
                    i++;
                }
                while (array[j] > pivot) {
                    j--;
                }
                if (i <= j) {
                    exchangeNumbers(i, j);
                    //move index to next position on both sides
                    i++;
                    j--;
                }
            }
            // call quickSort() method recursively
            if (lowerIndex < j) {
                quickSort(lowerIndex, j);
            }
            if (i < higherIndex) {
                quickSort(i, higherIndex);
            }
        }

        private void exchangeNumbers(int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        public static void main(String a[]) {

            MyQuickSort sorter = new MyQuickSort();
            int[] input = {24, 2, 45, 20, 56, 75, 2, 56, 99, 53, 12};
            sorter.sort(input);
            for (int i : input) {
                System.out.print(i);
                System.out.print(" ");
            }
        }
    }


Recursion

  • Recursion is the function calling  it self 
  • We can use instead of a loop which is in a large looping times
Code

Factorial

int factorial(int num ){
if (num <= 0) {
                return 1;
            } else {
                return num * factorial(--num );
            }
        }


Fabonaci

int fibonaci(int num ){

if (num <= 0) {
                return 0;
            } else {
                return num +  fibonaci(--num);
            }

        }



Trees

  • Hierarchy Concept
  • For File Systems/Java Class Hierarchy
  • Fast Searchable
  • Each Node Connect to multiple Nodes
  • Root/Parent/Child/Leaves/Height/Depth are some key words used in trees



Tress Traversing
  • PreOrder - VLR process
    • Visit first Left Right
  • PostOrder- LRV process
    • Left Right and Visit
  • InOrder- LVR process
    • Left Visit Right





Tree Balancing Techniques
  • Global
    • DSW Algorithm

  • Local
    • AVL
      • This consider about the level difference is equal to 1 or 0, it is balanced

    • Red Black
      • This consider about the level difference is upto 2 ,it is balanced



Tree Balancing

  • Left Rotate 
  • Right Rotate




Thank you for following The Explorer's DSA Tutorial. See you in another Tutorial :D




No comments:

Post a Comment