Implemented basic search / sort algorithm in Java

I am a new graduate engineer from April. This is Qiita's first post.

Introduction

As the title suggests, the basic search / sort algorithms I wrote it in Java. I published it on Blog before, but I posted it in 4 parts. I will put it together in Qiita. The search / sort algorithm implemented this time is as follows.

Search algorithm

• Linear Search
• Binary Search

Sort algorithm

• Bubble Sort
• Selection Sort
• Insertion Sort
• Shell Sort
• Quick Sort
• Merge Sort
• Heap Sort
• Bucket Sort
• Counting Sort

Linear Search

Average complexity: $ O (n) $

1. Extract elements from the top of the list
2. Compare the value of the extracted element with the value of the element you want to find ・ If they match, the search is complete. ・ If they do not match, go back to 1. and extract 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

Average complexity: $ O (\ log_2 {n}) $

1. Sort the array (assuming it is sorted in ascending order)
2. Examine the element in the center of the array
3. The central element is not the desired value and the desired data is greater than the central value If so, look at the latter half of the center. The central element is not the desired value and the desired data is smaller than the central value If so, check the first half from the center
4. Return 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) >>> 1;
            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

Average complexity: $ O (n ^ 2) $

1. Compare the values of the first element'A'and the adjacent next element'B'
2. If element'A'is greater than element'B', exchange the values of element'A'and element'B'
3. Move the first element to'B'and compare / exchange the values of element'B'and adjacent element'C'
4. Repeat the comparison / exchange until the end of the list, moving the first element to'C','D','E' ...
5. The element with the highest value emerges at the end of the list
6. Since the end of the list contains the largest value, shift the position of the end of the list (reduce the number of elements 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
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        bubbleSort.sort(test);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Selection Sort

Average complexity: $ O (n ^ 2) $

1. Set the first element of the array as the element "A0" with a temporary minimum value.
2. Compare the values of elements other than "A0" and "A0", and if the element "A1" with a value smaller than "A0" is found, exchange the values of "A0" and "A0".
3. By repeating 2., "A0" is set to the minimum value in the array.
4. Next, compare / exchange the elements other than "A1" and "A1" except "A0", and the elements other than "A2" and "A2" except "A1" to complete the alignment.

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

Average complexity: $ O (n ^ 2) $

1. Determine the sorted index'A'
2. Make the next element'B' after'A'the unaligned part
3. Insert'B'in'A'
4. Compare the values of A'and'B' and if the value of'B'is smaller, replace it with'A' 5.'A' and'B' become the aligned part
5. Let'C', the element next to'B', be the unaligned part
6. Insert'C'in the aligned parts'A',' B'
7. Compare the values of adjacent'C'and'B' and exchange for'B' if the value of'C'is smaller.
8. Furthermore, compare the values of'C'and'A', and if the value of'C'is smaller, exchange it for'A'.

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

Average complexity: $ O (n ^ 1.25) $

Insertion sort compares and exchanges adjacent elements, and shellsort compares / exchanges elements that are separated by h. The process of aligning elements that are separated by h is called h-sorting. Insertion sort is used for the alignment logic of h-sort. In shellsort, the number of h in h-sort is reduced to make a simple insertion sort (h = 1). By the time it becomes an insertion sort, it is in a state of being "almost aligned", so it is possible to perform 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

Average complexity: $ O (n \ log {n}) $

1. If the number of elements is 1 or less, it is considered as aligned and sorting is not performed.
2. Pick up the element that will be the pivot
3. Divide into two parts centered on the pivot-an element with a value greater than or less than the value of the pivot
4. Apply this algorithm recursively to the divided parts (sublists)

public class quickSort {

    public static void sort(int[] array, int left, int right){
        if(left <= right){
            int p = array[(left + right) >>> 1];
            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] );
        }

    }
}

Merge Sort

Average complexity: $ O (n \ log {n}) $

1. Split an unsorted list into two sublists
2. Align the sublist
3. Merge sublists into one sorted list

public class mergeSort {

    public static void sort(int[] array, int low, int high){
        if(low < high){
            int middle = (low + high) >>> 1;
            mergeSort.sort(array, low , middle);
            mergeSort.sort(array, middle+1, high);
            mergeSort.merge(array, low, middle, high);
        }

    }
    public static void merge(int[] array, int low, int middle, int high){
        int[] helper = new int[array.length];

        for (int i = low; i <= high; i++){
            helper[i] = array[i];
        }
        int helperLeft = low;
        int helperRight = middle + 1;
        int current = low;

        while (helperLeft <= middle && helperRight <= high){
            if (helper[helperLeft] <= helper[helperRight]){
                array[current] = helper[helperLeft];
                helperLeft ++;
            }
            else {
                array[current] = helper[helperRight];
                helperRight ++;

            }
            current ++;
        }
        int remaining = middle - helperLeft;
        for (int i = 0; i <= remaining; i++){
            array[current + i] = helper[helperLeft + i];
        }



    }

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

    }
}

Heap Sort

Average complexity: $ O (n \ log {n}) $

1. Build a bottom-up heap in the array to be sorted
2. Swap the first element [1] and the last element [N] of the constructed heap
3. Reconstruct the heap from element [1] to element [N-1]
4. Swap the first element [1] and the last element [N-1] of the heap
5. Return to 3. (The last element in 4. moves to [N-2], [N-3] ...)
6. Sorting is complete when the heap structure is gone

public class heapSort {

    public static void sort(int[] array) {
        int n = array.length;

        for (int i = n /2 -1; i>=0; i--){
            heap(array, n, i);
        }
        
        for (int i = n-1 ; i>=0; i --){
            if (array[0] > array[i]) {
                int tmp = array[0];
                array[0] = array[i];
                array[i] = tmp;

                heap(array, i-1, 0);
            }

        }
    }
    
    public static void heap(int[] array, int n , int root){
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;

        if (left < n && array[left] > array[largest]){
            largest = left;
        }

        if (right < n && array[right] > array[largest]){
            largest = right;
        }

        if (largest != root){
            int swap = array[root];
            array[root] = array[largest];
            array[largest] = swap;

            heap(array, n ,largest);
        }
    }


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

Bucket Sort

Average complexity: $ O (n + k) $

As a premise, the data to be sorted is an integer from 1 to 10.

1. Prepare 10 buckets corresponding to 1 to 10 side by side.
2. Put the data in the corresponding bucket
3. Extract data from the bucket in order

public class bucketSort {

    public static void sort(int[] array, int maxValue){
        int[] bucket = new int[maxValue + 1];

        for (int i = 0; i < bucket.length; i++){
            bucket[i] = 0;
        }

        for (int i = 0; i < array.length; i++){
            bucket[array[i]] ++;
        }

        int outPos = 0;
        for (int i = 0; i < bucket.length; i++){
            for (int j = 0; j < bucket[i]; j++){
                array[outPos++] = i;
            }
        }
    }


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

Counting Sort

Average complexity: $ O (nk) $

As a premise, the data to be sorted is an integer from 0 to 5. Let's set the array A to be sorted as {5,3,3,1,4}.

1. Prepare array C for counting keys (data in array A) and 2. prepare working array B for sorting.
2. Count the frequency of occurrence of data in array A (using array C)
3. Find the cumulative frequency distribution of the keys (held by array C)
4. Copy data from array A to array B according to the cumulative frequency distribution (of array C) (copy data from array B to the original array A if necessary)

public class countingSort {

    public static int[] sort(int[] array, int maxValue){
        int[] counts = new int[maxValue + 1];

        for (int i = 0; i < array.length; i ++){
            counts[array[i]] ++;
        }

        int total = 0;
        for (int i =0 ;i <= maxValue; i++){
            int count = counts[i];
            counts[i] = total;
            total += count;
        }

        int[] sortedValues = new int[array.length];
        for (int i = 0; i < array.length; i++){
            sortedValues[counts[array[i]]] = array[i];
            counts[array[i]] ++ ;
        }
        return sortedValues;


    }

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

}

Github

The code for the Java implementation of this search and sort algorithm I summarized it on Github. If you have any concerns, please publicize it (I'm studying because I'm likely to use Java in training).

https://github.com/takaaki82/algorithm-training-java

in conclusion

We are planning to take the Applied Information Technology Engineer Examination in October. Because this range is also the question range If you have any suggestions or other things you should do Please comment!