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