Introduction to Algorithm: basic search and sort algorithm (with Java)

So what is Algorithm?

It’s actually just a set of steps or instructions for completing a task. And to solve the problem with Algorithm, you will need to have an Algorithmic Thinking. It’s just a mindset to analyze a problem and breaking it down into distinct steps that can be solved separately. So let’s get down to the main point! But remember that to understand the contents of this blog, you will have to know some basic Java.


Intro

As the title suggests, We are going to implement the algorithm “basic search/sort algorithms” with Java. I published similar algorithm related posts in the past, but since I posted it in multiple divisions I decided to put it together on my blog. The search and sort algorithms implemented this time are as follows.

Search algorithm

  • Linear Search
  • Binary Search

Sort algorithm

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Shell Sort
  • Quick Sort

Let’s start with Linear Search

Linear search sequentially checks each element of the list until it finds an element that matches the target value. If the algorithm reaches the end of the list, the search terminates unsuccessfully.

Average complexity: O (n) O (n)

Extract an element from the top of the list Compare the value of the retrieved element with the value of the element to be retrieved

  1.  If they match, the search is completed
  2. If they do not match, return to 1. and take out the next element
public class linearSearch {
    public static int execute(int[] data, int target){
        int notFound = -1;
        for(int i = 0; i < data.length; i++){
            if(data[i] == target){
                return i;
            }
        }
        return notFound;
    }
    public static void main(String[] args){
        int[] data = {1, 2, 3, 4, 5};
        int result;
        result = linearSearch.execute(data, 3);
        if(result != -1) {
            System.out.println("Found: index key = " + result);
        }
        else{
            System.out.println("Not found.");
        }

    }

}

Binary Search

Binary search works on sorted arrays. The binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than the middle element, the search continues in the lower half of the array. If the target value is greater than the middle element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration

Average calculation amount: O(log2n)O(log2⁡n)

  1. Sort the arrays (assuming that they are sorted in ascending order here)
  2.  Examine the element in the middle of the array If the central element is not the target value and the target data is larger than the center value,
  3. examine the latter part of the data from the center.
  4. If the element at the center is not the target value and the target data is smaller than the value at the center, check the first part from the center
  5. Back to 2.
public class binarySearch {
    public static boolean execute(int[] data, int target) {
        int low = 0;
        int high = data.length - 1;
        while (low <= high) {
            int middle = (low + high) / 2;
            if (data[middle] == target) {
                return true;
            } else if (data[middle] < target) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] data = {23, 25, 53, 444, 5466, 12646};
        boolean result;
        result = binarySearch.execute(data, 25);
        if (result){
            System.out.println("Found!");
        }
        else {
            System.out.println("Not Found.");
        }
    }

}

 


Bubble Sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. 

Average Complexity: O(n2)O(n2)

  1. The values of the first element ‘A’ and the next element ‘B’ next to each other are compared
  2.  If the element ‘A’ is larger than the element ‘B’, exchange the values of the element ‘A’ and the element ‘B’
  3. Move the head element to ‘B’ and compare/exchange the value of element ‘C’ next to element ‘B’
  4. Move the first element to ‘C’, ‘D’, ‘E’ … and repeat comparison/exchange until the end of the list
  5. An element with the largest value floats to the end of the list
  6. As the end of the list contains the largest value, shift the position of the end of the list (reduce the number of elements one by one) and repeat steps 1 to 6
public class bubbleSort {
    public static void sort(int[] array){
        int temp;
        for(int i = 0; i < array.length; i++){
            for(int j = 0; j< array.length -i -1; j ++){
                if(array[j] > array[j + 1]){
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }

    }
    public static void main(String[] args){
        int[] test = { 103, 25, 12, 62, 8};

        bubbleSort.sort(test);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Selection Sort

In computer scienceselection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

1. The first element of the array is set as an element “A 0” having a provisional minimum value

2. Compare the values of elements other than “A 0” and “A 0” and exchange the values of “A 0” and “A 0” if an element “A 1” having a value smaller than “A 0” is found

3. By repeating step 2, “A 0” is set to the minimum value in the array

4. Next, except for “A0”, elements other than “A1” and “A1”, elements other than “A2” and “A2” except for “A1” are compared/exchanged and alignment is completed

public class selectionSort {
    public static void sort(int[] array){
        for(int i = 0; i < array.length; i++ ){
            int index = i;
            for(int j = i + 1; j < array.length; j++){
                if(array[j] < array[index]){
                    index = j;
                }
            }
            if(i != index){
                int tmp = array[index];
                array[index] = array[i];
                array[i] = tmp;

            }
        }
    }
    public static void main(String[] args){
        int[] test
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        selectionSort.sort(test);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Insertion Sort

Insertion sort iterates, consuming one input element each repetition and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there. It repeats until no input elements remain.

  1. Determine the aligned index ‘A’
  2. Let element ‘B’ next to ‘A’ not be aligned
  3. Insert ‘B’ in ‘A’
  4. Compare the values of A ‘and’ B ‘and exchange’ A ‘if the value of’ B ‘is small
  5. ‘A’ and ‘B’ are aligned parts
  6. Let element ‘C’ next to ‘B’ not be aligned
  7. Insert ‘C’ in aligned parts ‘A’, ‘B’
  8. Compare the values of ‘C’ and ‘B’ adjacent to each other and exchange ‘B’ if the value of ‘C’ is small
  9. Furthermore, compare the values of ‘C’ and ‘A’ and exchange ‘A’ if the value of ‘C’ is small
public class insertionSort {

    public static void sort(int[] array){
        for(int i = 1; i < array.length; i++){
            int j = i;
            while(j >= 1 && array[j-1] > array[j]){
                int tmp = array[j];
                array[j] = array[j - 1];
                array[j-1] = tmp;
                j --;

            }
        }

    }

    public static void main(String[] args){
        int[] test
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        insertionSort.sort(test);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Shell Sort

Shellsort is a generalization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, considering every hth element gives a sorted list. Such a list is said to be h-sorted. Equivalently, it can be thought of as h interleaved lists, each individually sorted.

  1. For insert sorting, comparison and exchange are performed on adjacent elements, shell sorting compares / exchanges elements separated by h.
    h The process of sorting away elements is called h-sorting.
  2. Insert sort is used for h – sort alignment logic.
  3. In shell sorting, by decreasing the number of h of h – sorting, eventually, it becomes a simple insertion sort (h = 1).
  4. By the time the insertion sort is reached since the “almost aligned” state has been
  5. completed, you can make an alignment that takes advantage of the insertion sort.
public class shellSort {
    public static void sort(int[] array){
        int h = array.length / 2;

        while(h > 0){
            for(int i=h; i < array.length; i++){
                int j = i;
                while(j >= h && array[j - h] > array[j]){
                    int tmp = array[j];
                    array[j] = array[j-h];
                    array[j-h] = tmp;
                    j --;
                }
            }
            h /= 2;
        }

    }


    public static void main(String[] args){
        int[] test
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        shellSort.sort(test);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

 


Quick Sort

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

  1. If the number of elements is one or less, it is regarded assorted and sort processing is not performed
  2. Pick up elements to be the pivot
  3. Divide it into two parts centered on the pivot – an element with a value greater than the pivot value and an element with a smaller value
  4. Apply this algorithm recursively to the divided part (sublist)
public class quickSort {

    public static void sort(int[] array, int left, int right){
        if(left <= right){
            int p = array[(left + right)/2];
            int l = left;
            int r = right;
            while(l <= r){
                while (array[l] < p){
                    l ++;
                }
                while (array[r] > p){
                    r --;
                }
                if (l <= r){
                    int tmp = array[l];
                    array[l] = array[r];
                    array[r] = tmp;
                    l++ ;
                    r-- ;
                }
            }
            quickSort.sort(array, left, r);
            quickSort.sort(array, l, right);
        }
    }

    public static void main(String[] args){
        int[] test
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        quickSort.sort(test, 0, test.length-1);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *