Answer to Question #290492 in Java | JSP | JSF for Meena

Question

Give the following list: B E A D C F H G

Apply selection sort AND merge sort to sort the list in ascending order. Show all the insertion steps for each data.

Answer 1

import java.util.Arrays;

public class Main {
    public static void selectionSort(char[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[min] > array[j]) {
                    min = j;
                }
            }
            if (i != min) {
                char tmp = array[i];
                array[i] = array[min];
                array[min] = tmp;
            }
        }
    }


    public static void mergeSort(char[] a, char[] b, int n) {
        for (int width = 1; width < n; width = 2 * width) {
            for (int i = 0; i < n; i = i + 2 * width) {
                merge(a, i, Math.min(i + width, n), Math.min(i + 2 * width, n), b);
            }
            System.arraycopy(b, 0, a, 0, n);
        }
    }

    public static void merge(char[] a, int iLeft, int iRight, int iEnd, char[] b) {
        for (int i = iLeft, j = iRight, k = iLeft; k < iEnd; k++) {
            if (i < iRight && (j >= iEnd || a[i] <= a[j])) {
                b[k] = a[i++];
            } else {
                b[k] = a[j++];
            }
        }
    }

    public static void main(String[] args) {
        char[] array = {'B', 'E', 'A', 'D', 'C', 'F', 'H', 'G'};
        selectionSort(Arrays.copyOf(array, array.length));
        char[] a = Arrays.copyOf(array, array.length);
        mergeSort(Arrays.copyOf(array, array.length), a, array.length);
    }
}

Selection:

[B, E, A, D, C, F, H, G]

[A, E, B, D, C, F, H, G]

[A, B, E, D, C, F, H, G]

[A, B, C, D, E, F, H, G]

[A, B, C, D, E, F, H, G]

[A, B, C, D, E, F, H, G]

[A, B, C, D, E, F, H, G]

[A, B, C, D, E, F, G, H]

Merge:

[B, E, A, D, C, F, G, H]

[A, B, D, E, C, F, G, H]

[A, B, C, D, E, F, G, H]