Array Sorting Techniques

Bubble Sort

Bubble sort is a fundamental sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process resembles bubbles rising to the surface, with larger values sinking to the end of the array.

Core Logic:

• Iterate through the array comparing pairs of neighboring elements.
• If the left element is greater than the right, swap them.
• After the first pass, the largest element is guaranteed to be at the end.
• Repeat the process for the remaining unsorted portion.
• The number of passes required is n - 1 for a array of length n.

Implementation:

public class ArraySorter {

    public void bubbleSort(int[] data) {
        int len = data.length;
        for (int pass = 0; pass < len - 1; pass++) {
            for (int idx = 0; idx < len - 1 - pass; idx++) {
                if (data[idx] > data[idx + 1]) {
                    int swapHolder = data[idx];
                    data[idx] = data[idx + 1];
                    data[idx + 1] = swapHolder;
                }
            }
        }
    }

    public void printData(int[] data) {
        for (int val : data) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}

Selection Sort

Selection sort generally performs fewer swaps than bubble sort, making it slightly more efficient in scenarios where write operations are costly.

Core Logic:

• Divide the array into a sorted and an unsorted region.
• In each iteration, find the maximum (or minimum) element in the unsorted region.
• Swap the found element with the last element of the unsorted region.
• Unlike bubble sort, it does not swap adjacent elements continuously but rather places the selected element directly into its final position.

Implementation:

public void selectionSort(int[] data) {
    int size = data.length;
    for (int i = 0; i < size - 1; i++) {
        int maxPos = 0;
        // Find the index of the maximum element in the unsorted part
        for (int j = 1; j < size - i; j++) {
            if (data[j] > data[maxPos]) {
                maxPos = j;
            }
        }
        // Swap the found maximum with the element at the end of the unsorted section
        int temp = data[size - 1 - i];
        data[size - 1 - i] = data[maxPos];
        data[maxPos] = temp;
    }
}

Reverse Order Sort

This technique inverts the order of elements in an array without necessarily sorting them by value.

Core Logic:

• Swap the first element with the last, the second with the second-to-last, and so on.
• The loop runs only up to the middle of the array to avoid swapping elements back to their original positions.

Implementation:

public void invertArray(int[] data) {
    int limit = data.length / 2;
    for (int i = 0; i < limit; i++) {
        int temp = data[i];
        data[i] = data[data.length - 1 - i];
        data[data.length - 1 - i] = temp;
    }
}

Practical Array Operations

The following example demonstrates copying array ranges, finding minimum values, modifying elements in a String array, and transposing a 2D matrix.

import java.util.Arrays;

public class ArrayPractice {

    public static void main(String[] args) {
        // 1. Copying a range of an array
        int[] source = {1, 2, 6, 7, 5};
        int[] destination = Arrays.copyOfRange(source, 0, 4);
        
        display(source);
        display(destination);

        // 2. Finding the minimum value
        int minVal = source[0];
        for (int num : source) {
            if (num < minVal) {
                minVal = num;
            }
        }
        System.out.println("Minimum value: " + minVal);

        // 3. Replacing an element in a String array
        String[] greeting = {"hello", ",", " ", "world", "!"};
        for (String s : greeting) System.out.print(s + " ");
        System.out.println();
        
        greeting[2] = "bb";
        for (String s : greeting) System.out.print(s + " ");
        System.out.println();

        // 4. Transposing a 2D matrix
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] transposed = new int[cols][rows];

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                transposed[c][r] = matrix[r][c];
                System.out.print(transposed[c][r]);
            }
            System.out.println();
        }
    }

    static void display(int[] arr) {
        for (int v : arr) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}