Sort an Array Without Using Built-in Sorting Methods - Java

Category: Medium | Concepts used: Bubble sort, selection sort

---

Problem Statement

Given an array, sort it in ascending order without using Arrays.sort() or any other built-in sort.

Input : [5, 2, 8, 1, 9]      Output: [1, 2, 5, 8, 9]

Examples (with edge scenarios)

#	Input	Output	Why
1	[5, 2, 8, 1, 9]	[1, 2, 5, 8, 9]	Normal case
2	[] (empty)	[]	Nothing to sort
3	[7] (single element)	[7]	Already “sorted” trivially
4	[3, 3, 3] (all same)	[3, 3, 3]	No visible change, but algorithm still runs
5	[5, 4, 3, 2, 1] (already reverse-sorted, worst case)	[1, 2, 3, 4, 5]	Maximum number of swaps needed — good stress test

Common Fresher Mistake

Mistake	What happens	Fix
Off-by-one errors in the inner loop bounds	IndexOutOfBoundsException, or missing the last comparison	Carefully define loop bounds: outer loop 0 to n-1, inner loop typically 0 to n-i-1 (bubble sort)
Not adding an early-exit optimization for bubble sort	Works, but always runs the full O(n²) even on nearly-sorted input	Add a “swapped” flag — if no swaps happen in a full pass, the array is already sorted, so stop early

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: Organizing File Drawers

Imagine you are organizing a messy drawer of physical files:

• Bubble Sort (Neighbor Swapping): You look at the first two files in the drawer. If they are in the wrong order, you swap them. Then you look at the second and third files, swap them if needed, and continue this neighbor check all the way to the end. The heaviest (largest) file “bubbles” to the very back of the drawer. You go back to the front and repeat this process for the remaining unsorted files.
• Selection Sort (The Scavenger Hunt): You scan the entire drawer from front to back to find the absolute smallest file. Once you locate it, you immediately swap it with the very first file. Then, starting from the second slot, you scan the rest of the drawer to find the next smallest file and swap it with the second file. You repeat this search-and-swap scavenger hunt until the drawer is fully sorted!

---

Solution 1 — Bubble Sort

Intuition

Repeatedly walk through the array, comparing each pair of neighbors. If they’re in the wrong order, swap them. After each full pass, the largest unsorted element “bubbles up” to its correct position at the end — like air bubbles rising to the top of water. Repeat until no more swaps are needed.

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;

for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;

for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

if (!swapped) {
                break; // already sorted, no need for further passes
            }
        }
    }

public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr)); // [1, 2, 5, 8, 9]
    }
}

Output:

[1, 2, 5, 8, 9]

Dry Run (arr = [5, 2, 8, 1])

Pass 1 (i=0):
  j=0: 5>2 -> swap -> [2,5,8,1]
  j=1: 5>8? no
  j=2: 8>1 -> swap -> [2,5,1,8]
  swapped=true

Pass 2 (i=1):
  j=0: 2>5? no
  j=1: 5>1 -> swap -> [2,1,5,8]
  swapped=true

Pass 3 (i=2):
  j=0: 2>1 -> swap -> [1,2,5,8]
  swapped=true

Pass 4 (i=3): loop condition i<n-1 (3<3) false -> loop ends

Final: [1, 2, 5, 8]

Interviewer’s take

This is a fine, simple sorting algorithm to demonstrate — easy to explain step by step, which is valuable for QA interviews where clear communication matters. It’s O(n²) though, so interviewers may ask if you know of better options.

Follow-up questions you might get:

• “What’s the time complexity, best and worst case?” → Worst case O(n²) (reverse-sorted input); best case O(n) with the early-exit optimization (already-sorted input needs just one pass to confirm).
• “Do you know of any other simple sorting algorithms?” → leads to Solution 2 (selection sort) as an alternative.

---

Solution 2 — Selection Sort (Alternative, Fewer Swaps)

Intuition

Instead of repeatedly swapping neighbors, find the smallest remaining element in the unsorted portion of the array, and swap it directly into its correct final position. Repeat, shrinking the “unsorted” portion by one each time — like repeatedly picking out the smallest card from a pile and placing it at the front.

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

for (int i = 0; i < n - 1; i++) {
            int minIndex = i;

// find the smallest element in the remaining unsorted part
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

// swap the found minimum into its correct position
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9};
        selectionSort(arr);
        System.out.println(java.util.Arrays.toString(arr)); // [1, 2, 5, 8, 9]
    }
}

Output:

[1, 2, 5, 8, 9]

Dry Run (arr = [5, 2, 8, 1])

i=0: find min in [5,2,8,1] -> min is 1 at index 3 -> swap arr[0],arr[3] -> [1,2,8,5]
i=1: find min in [2,8,5] (from index 1) -> min is 2 at index 1 -> no swap needed (already in place)
i=2: find min in [8,5] (from index 2) -> min is 5 at index 3 -> swap arr[2],arr[3] -> [1,2,5,8]

Final: [1, 2, 5, 8]

Interviewer’s take

Also O(n²), but performs fewer actual swaps than bubble sort (at most n-1 swaps total, vs. potentially many more for bubble sort) — worth mentioning as a trade-off if swap cost matters (e.g., sorting large objects where swapping is expensive, not just simple integers).

---

📊 Visual Flowchart

graph TD
    Start["Input: Array arr"] --> Selection{"Choose Algorithm"}
    Selection -->|Bubble Sort| BLoop["Outer Loop: i from 0 to n-2"]
    BLoop --> BInit["swapped = false"]
    BInit --> BInner["Inner Loop: j from 0 to n-i-2"]
    BInner --> BCheck{"arr[j] > arr[j+1]?"}
    BCheck -->|Yes| BSwap["Swap arr[j] and arr[j+1]<br>swapped = true"]
    BSwap --> BNext["j++"]
    BCheck -->|No| BNext
    BNext --> BInner
    BInner -->|Done| BExit{"swapped == false?"}
    BExit -->|Yes| End["Sorted Array"]
    BExit -->|No| BNextOuter["i++"]
    BNextOuter --> BLoop
    Selection -->|Selection Sort| SLoop["Outer Loop: i from 0 to n-2"]
    SLoop --> SInit["minIndex = i"]
    SInit --> SInner["Inner Loop: j from i+1 to n-1"]
    SInner --> SCheck{"arr[j] < arr[minIndex]?"}
    SCheck -->|Yes| SUpdate["minIndex = j"]
    SUpdate --> SNext["j++"]
    SCheck -->|No| SNext
    SNext --> SInner
    SInner -->|Done| SCheckIndex{"minIndex != i?"}
    SCheckIndex -->|Yes| SSwap["Swap arr[i] and arr[minIndex]"]
    SSwap --> SNextOuter["i++"]
    SCheckIndex -->|No| SNextOuter
    SNextOuter --> SLoop

---

Final Verdict — Which Solution Should You Give?

• Both are acceptable manual sorting solutions for this exact question — the point is demonstrating you understand a sorting algorithm from scratch, not necessarily picking the theoretically “best” O(n²) option.
• Bubble sort is usually easier to explain out loud step-by-step (good for QA interviews); selection sort does fewer swaps.
• If asked “is this the most efficient way to sort in general?” — be honest: no, real-world code should just use Arrays.sort() (which uses a highly optimized algorithm internally, like Dual-Pivot Quicksort or TimSort depending on data type). This exercise is specifically about understanding sorting logic manually.

---

Quick Recap

Approach	Time (worst)	Time (best, with optimization)	Space	Swaps
Bubble Sort	O(n²)	O(n) with early exit	O(1)	Can be many
Selection Sort	O(n²)	O(n²) (no early-exit benefit)	O(1)	At most n-1