12 classic String-based Java interview questions with simple explanations and code.

 

1️⃣ Check if a String is a Palindrome

Problem
Given a string, check if it reads the same forward and backward. Example: "madam" → palindrome, "hello" → not palindrome.

Idea
Use two pointers: one at the beginning, one at the end, and compare characters.

public class PalindromeString {
    public static void main(String[] args) {
        String str = "Madam";

        if (isPalindrome(str)) {
            System.out.println(str + " is a palindrome");
        } else {
            System.out.println(str + " is not a palindrome");
        }
    }

    public static boolean isPalindrome(String s) {
        if (s == null) return false;
        s = s.toLowerCase();
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

---

2️⃣ Reverse a String (Without Using Library Reverse)

Problem
Reverse a given string: input "hello" → output "olleh".

Idea
Convert to char array and swap from both ends.

public class ReverseString {
    public static void main(String[] args) {
        String str = "hello";
        System.out.println("Original: " + str);
        System.out.println("Reversed: " + reverse(str));
    }

    public static String reverse(String s) {
        if (s == null) return null;

        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;

        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
        return new String(chars);
    }
}

---

3️⃣ Reverse Words in a Sentence

Problem
Given "Java is awesome", output "awesome is Java" (reverse word order, not characters inside each word).

Idea
Split on spaces, reverse the array of words, then join back.

public class ReverseWordsInSentence {
    public static void main(String[] args) {
        String sentence = "Java is awesome";
        System.out.println(reverseWords(sentence));
    }

    public static String reverseWords(String s) {
        if (s == null || s.trim().isEmpty()) return s;

        String[] words = s.trim().split("\\s+");
        int left = 0, right = words.length - 1;

        while (left < right) {
            String tmp = words[left];
            words[left] = words[right];
            words[right] = tmp;
            left++;
            right--;
        }

        return String.join(" ", words);
    }
}

---

4️⃣ Check if Two Strings are Anagrams

Problem
Two strings are anagrams if they contain the same characters with the same frequency (order doesn’t matter).
Example: "listen" and "silent" → anagrams.

Idea
Either sort both strings and compare, or count character frequencies. Here we sort.

import java.util.Arrays;

public class AnagramCheck {
    public static void main(String[] args) {
        String s1 = "listen";
        String s2 = "silent";

        if (areAnagrams(s1, s2)) {
            System.out.println(s1 + " and " + s2 + " are anagrams");
        } else {
            System.out.println(s1 + " and " + s2 + " are not anagrams");
        }
    }

    public static boolean areAnagrams(String a, String b) {
        if (a == null || b == null) return false;

        a = a.replaceAll("\\s+", "").toLowerCase();
        b = b.replaceAll("\\s+", "").toLowerCase();

        if (a.length() != b.length()) return false;

        char[] ca = a.toCharArray();
        char[] cb = b.toCharArray();

        Arrays.sort(ca);
        Arrays.sort(cb);

        return Arrays.equals(ca, cb);
    }
}

---

5️⃣ Find the First Non-Repeating Character

Problem
Given a string, find the first character that does not repeat. Example: "swiss" → first non-repeating is 'w'.

Idea
First pass: count frequencies. Second pass: return first char with count 1.

import java.util.LinkedHashMap;
import java.util.Map;

public class FirstNonRepeatingChar {
    public static void main(String[] args) {
        String str = "swiss";
        Character result = firstNonRepeating(str);
        System.out.println("First non-repeating character: " + result);
    }

    public static Character firstNonRepeating(String s) {
        if (s == null) return null;

        Map<Character, Integer> freq = new LinkedHashMap<>();

        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        for (Map.Entry<Character, Integer> e : freq.entrySet()) {
            if (e.getValue() == 1) {
                return e.getKey();
            }
        }
        return null; // no unique char
    }
}

---

6️⃣ Count Vowels and Consonants

Problem
Given a string, count how many vowels and consonants are present (alphabet letters only).

Idea
Loop through characters, check if alphabet, then check if it’s in 'aeiou'.

public class VowelConsonantCount {
    public static void main(String[] args) {
        String str = "Hello Java 123";

        int vowels = 0;
        int consonants = 0;

        String lower = str.toLowerCase();

        for (int i = 0; i < lower.length(); i++) {
            char ch = lower.charAt(i);

            if (ch >= 'a' && ch <= 'z') {
                if ("aeiou".indexOf(ch) != -1) {
                    vowels++;
                } else {
                    consonants++;
                }
            }
        }

        System.out.println("Vowels: " + vowels);
        System.out.println("Consonants: " + consonants);
    }
}

---

7️⃣ Remove All Duplicates Characters (Keep First Occurrence)

Problem
Input: "programming" → Output: "progamin" (remove repeated chars, keep the first time they appear).

Idea
Use a boolean array or Set to track already seen characters.

import java.util.HashSet;
import java.util.Set;

public class RemoveDuplicateChars {
    public static void main(String[] args) {
        String str = "programming";
        System.out.println(removeDuplicates(str));
    }

    public static String removeDuplicates(String s) {
        if (s == null) return null;

        Set<Character> seen = new HashSet<>();
        StringBuilder result = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (!seen.contains(c)) {
                seen.add(c);
                result.append(c);
            }
        }
        return result.toString();
    }
}

---

8️⃣ Check if One String is a Rotation of Another

Problem
Check if s2 is a rotation of s1.
Example: s1 = "waterbottle", s2 = "erbottlewat" → rotation.

Idea
If lengths are same, check if s2 is a substring of s1 + s1.

public class StringRotationCheck {
    public static void main(String[] args) {
        String s1 = "waterbottle";
        String s2 = "erbottlewat";

        if (isRotation(s1, s2)) {
            System.out.println(s2 + " is a rotation of " + s1);
        } else {
            System.out.println(s2 + " is NOT a rotation of " + s1);
        }
    }

    public static boolean isRotation(String s1, String s2) {
        if (s1 == null || s2 == null) return false;
        if (s1.length() != s2.length()) return false;
        if (s1.isEmpty()) return true; // both empty

        String doubled = s1 + s1;
        return doubled.contains(s2);
    }
}

---

9️⃣ Longest Substring Without Repeating Characters

Problem
Given a string, find the length of the longest substring without repeating characters.
Example: "abcabcbb" → longest is "abc" → length 3.

Idea
Use sliding window with a map that stores last index of each character.

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {
    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("Length: " + lengthOfLongestSubstring(s));
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null) return 0;

        Map<Character, Integer> lastIndex = new HashMap<>();
        int start = 0;
        int maxLen = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (lastIndex.containsKey(c) && lastIndex.get(c) >= start) {
                // move start to one position after the last occurrence
                start = lastIndex.get(c) + 1;
            }

            lastIndex.put(c, i);
            maxLen = Math.max(maxLen, i - start + 1);
        }

        return maxLen;
    }
}

---

🔟 Character Frequency Count

Problem
Print how many times each character appears in a string.
Example: "banana" → b:1, a:3, n:2.

Idea
Use a Map<Character, Integer> and count all characters.

import java.util.LinkedHashMap;
import java.util.Map;

public class CharacterFrequency {
    public static void main(String[] args) {
        String str = "banana";
        printCharFrequency(str);
    }

    public static void printCharFrequency(String s) {
        if (s == null) return;

        Map<Character, Integer> freq = new LinkedHashMap<>();

        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }

        for (Map.Entry<Character, Integer> e : freq.entrySet()) {
            System.out.println(e.getKey() + " -> " + e.getValue());
        }
    }
}

---

1️⃣1️⃣ Count Occurrences of a Substring

Problem
Given a string text and a string pattern, count how many times pattern appears in text (non-overlapping).

Example: text = "aaaa", pattern = "aa" → result = 2.

Idea
Scan using indexOf in a loop and move index by pattern length.

public class SubstringOccurrences {
    public static void main(String[] args) {
        String text = "aaaa";
        String pattern = "aa";
        System.out.println("Count: " + countOccurrences(text, pattern));
    }

    public static int countOccurrences(String text, String pattern) {
        if (text == null || pattern == null || pattern.isEmpty()) return 0;

        int count = 0;
        int index = 0;

        while ((index = text.indexOf(pattern, index)) != -1) {
            count++;
            index += pattern.length(); // move past this occurrence
        }
        return count;
    }
}

---

1️⃣2️⃣ Simple String Compression (Run-Length Encoding Style)

Problem
Compress a string by replacing consecutive repeating characters with the character followed by the count.
Example: "aaabbc" → "a3b2c1".
If compressed string is not smaller, return original.

Idea
Loop through string and count runs.

public class StringCompression {
    public static void main(String[] args) {
        String s = "aaabbc";
        System.out.println("Original: " + s);
        System.out.println("Compressed: " + compress(s));
    }

    public static String compress(String s) {
        if (s == null || s.isEmpty()) return s;

        StringBuilder sb = new StringBuilder();
        int count = 1;

        for (int i = 1; i <= s.length(); i++) {
            if (i < s.length() && s.charAt(i) == s.charAt(i - 1)) {
                count++;
            } else {
                sb.append(s.charAt(i - 1)).append(count);
                count = 1;
            }
        }

        String compressed = sb.toString();
        return compressed.length() < s.length() ? compressed : s;
    }
}

---

 

How Graphs Are Stored and Traversed in Java (DFS & BFS Explained)

Graphs are everywhere: social networks, maps, workflows, dependencies, and more.
In this post, we’ll see:

• How to store a graph in Java

• How to print the graph

• How DFS (Depth-First Search) and BFS (Breadth-First Search) work

• A simple implementation with main()

We’ll keep everything very simple and beginner-friendly.

---

1. The Example Graph

We’ll use this small undirected graph with 5 nodes: 0, 1, 2, 3, 4.

🔹 Visual graph (text-based)

    1
   / \
  0   2
  |
  3

  1
  |
  4

🔹 Edges

We have these connections (edges):

• 0 — 1

• 0 — 3

• 1 — 2

• 1 — 4

This is an undirected graph, so:

• If 0 is connected to 1 → 1 is also connected to 0.

---

2. How We Store the Graph in Java

The most common way to store a graph is using an Adjacency List.

2.1 What is an adjacency list?

For each node, we store a list of its neighbors.

For our graph:

Node 0 → neighbors: 1, 3
Node 1 → neighbors: 0, 2, 4
Node 2 → neighbors: 1
Node 3 → neighbors: 0
Node 4 → neighbors: 1

2.2 Java data structure

We use:

List<List<Integer>> graph = new ArrayList<>();

• graph is a list

• Each element of graph is another list of integers

• graph.get(i) gives the list of neighbors for node i

So:

graph.get(0) → [1, 3]
graph.get(1) → [0, 2, 4]
graph.get(2) → [1]
graph.get(3) → [0]
graph.get(4) → [1]

2.3 Step-by-step: building the adjacency list

Assume we have n = 5 nodes: 0..4.

Step 1: Create the outer list

int n = 5;
List<List<Integer>> graph = new ArrayList<>();

Now graph is empty:

graph: [ ]

Step 2: Create an empty neighbor list for each node

for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>());
}

Now we have:

graph[0] = [ ]
graph[1] = [ ]
graph[2] = [ ]
graph[3] = [ ]
graph[4] = [ ]

Step 3: Add edges (undirected)

For undirected edge 0 — 1:

graph.get(0).add(1); // 0 → 1
graph.get(1).add(0); // 1 → 0

For 0 — 3:

graph.get(0).add(3);
graph.get(3).add(0);

For 1 — 2:

graph.get(1).add(2);
graph.get(2).add(1);

For 1 — 4:

graph.get(1).add(4);
graph.get(4).add(1);

Now the adjacency list looks like:

graph[0] = [1, 3]
graph[1] = [0, 2, 4]
graph[2] = [1]
graph[3] = [0]
graph[4] = [1]

---

3. Printing the Graph

We can print the adjacency list like this:

static void printGraph(List<List<Integer>> graph) {
    for (int i = 0; i < graph.size(); i++) {
        System.out.print("Node " + i + " -> ");
        System.out.println(graph.get(i));
    }
}

Output:

Node 0 -> [1, 3]
Node 1 -> [0, 2, 4]
Node 2 -> [1]
Node 3 -> [0]
Node 4 -> [1]

This gives a clear picture of how the graph is stored in memory.

---

4. DFS (Depth-First Search) – Step by Step

DFS means: go as deep as possible along one path before backtracking.

We will start DFS from node 0.

4.1 DFS idea in simple words

1. Start at a node (e.g., 0)

2. Visit it and mark as visited

3. For each neighbor:

   • If not visited → go into that neighbor (recursively)

4. When no unvisited neighbors → go back (backtrack)

4.2 Run DFS on our graph

Adjacency list reminder:

0 : [1, 3]
1 : [0, 2, 4]
2 : [1]
3 : [0]
4 : [1]

Start: DFS(0)

Let’s track:

• visited[] = keeps track of nodes already seen

• output = order of printing

Step-by-step DFS from 0

1. Start at 0

   • Visit 0 → visited[0] = true

   • Output: 0

   • Neighbors: [1, 3]

2. Go to neighbor 1 (first neighbor of 0)

   • Visit 1 → visited[1] = true

   • Output: 0 1

   • Neighbors of 1: [0, 2, 4]

   • 0 is already visited → skip

   • Next: 2

3. Go to neighbor 2

   • Visit 2 → visited[2] = true

   • Output: 0 1 2

   • Neighbors of 2: [1] (already visited)

   • No more new neighbors → go back to 1

4. Back at 1, next neighbor is 4

   • Visit 4 → visited[4] = true

   • Output: 0 1 2 4

   • Neighbors of 4: [1] (already visited)

   • No more new neighbors → go back to 1 → back to 0

5. Back at 0, next neighbor is 3

   • Visit 3 → visited[3] = true

   • Output: 0 1 2 4 3

   • Neighbors of 3: [0] (already visited)

   • Done

Final DFS order starting from 0:

0 1 2 4 3

4.3 DFS Java code

static void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;                 // Mark current node as visited
    System.out.print(node + " ");         // Print the node

    // Go through all neighbors of this node
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {         // If neighbor is not visited
            dfs(neighbor, visited, graph); // Recursively visit neighbor
        }
    }
}

---

5. BFS (Breadth-First Search) – Step by Step

BFS means: visit nodes level by level, like waves going outwards.

We use a queue.

5.1 BFS idea in simple words

1. Start at a node and push it into a queue

2. While queue is not empty:

   • Remove (poll) one node

   • Visit it

   • Add all its unvisited neighbors to the queue

5.2 Run BFS from node 0

Adjacency list again:

0 : [1, 3]
1 : [0, 2, 4]
2 : [1]
3 : [0]
4 : [1]

Let’s track:

• visited[]

• queue

• output

Initial:

queue = [0]
visited[0] = true
output = (empty)

Step 1:

• Take from queue → node = 0

• Output: 0

• Neighbors: [1, 3]

  • 1 not visited → mark visited, add to queue

  • 3 not visited → mark visited, add to queue

Now:

queue = [1, 3]
visited = [0,1,0,1,0]
output = 0

Step 2:

• Take from queue → node = 1

• Output: 0 1

• Neighbors of 1: [0, 2, 4]

  • 0 already visited → skip

  • 2 not visited → mark visited, add to queue

  • 4 not visited → mark visited, add to queue

Now:

queue = [3, 2, 4]
visited = [1,1,1,1,1]
output = 0 1

Step 3:

• Take from queue → node = 3

• Output: 0 1 3

• Neighbors of 3: [0] (already visited)

• Queue: [2, 4]

Step 4:

• Take from queue → node = 2

• Output: 0 1 3 2

• Neighbors of 2: [1] (already visited)

• Queue: [4]

Step 5:

• Take from queue → node = 4

• Output: 0 1 3 2 4

• Neighbors of 4: [1] (already visited)

• Queue: [] → done

Final BFS order from 0:

0 1 3 2 4

5.3 BFS Java code

static void bfs(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> q = new LinkedList<>();

    visited[start] = true;  // Mark starting node
    q.add(start);           // Add start node into queue

    while (!q.isEmpty()) {
        int node = q.poll();        // Take one node from queue
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {   // If neighbor not visited
                visited[neighbor] = true;
                q.add(neighbor);        // Add neighbor to queue
            }
        }
    }
}

---

6. Full Simple Java Program (With main)

You can copy-paste this file and run directly.

import java.util.*;

public class GraphDemo {

    // ---------- DFS: Depth-First Search ----------
    static void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
        visited[node] = true;                 // Mark current node as visited
        System.out.print(node + " ");         // Print the node

        // Visit all neighbors
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {         // Only go to unvisited nodes
                dfs(neighbor, visited, graph);
            }
        }
    }

    // ---------- BFS: Breadth-First Search ----------
    static void bfs(int start, List<List<Integer>> graph) {
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> q = new LinkedList<>();

        visited[start] = true;   // Start node is visited
        q.add(start);            // Put start node in queue

        while (!q.isEmpty()) {
            int node = q.poll(); // Take from front of queue
            System.out.print(node + " ");

            // Add all unvisited neighbors to queue
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.add(neighbor);
                }
            }
        }
    }

    // ---------- Print Graph (Adjacency List) ----------
    static void printGraph(List<List<Integer>> graph) {
        System.out.println("Graph adjacency list:");
        for (int i = 0; i < graph.size(); i++) {
            System.out.println("Node " + i + " -> " + graph.get(i));
        }
    }

    public static void main(String[] args) {
        int n = 5;  // Number of nodes: 0,1,2,3,4

        // 1) Create empty graph
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 2) Add undirected edges: 0-1, 0-3, 1-2, 1-4
        addUndirectedEdge(graph, 0, 1);
        addUndirectedEdge(graph, 0, 3);
        addUndirectedEdge(graph, 1, 2);
        addUndirectedEdge(graph, 1, 4);

        // 3) Print graph
        printGraph(graph);

        // 4) Run DFS from node 0
        System.out.print("\nDFS from node 0: ");
        boolean[] visited = new boolean[n];
        dfs(0, visited, graph);

        // 5) Run BFS from node 0
        System.out.print("\nBFS from node 0: ");
        bfs(0, graph);
    }

    // Helper to add an undirected edge
    static void addUndirectedEdge(List<List<Integer>> graph, int u, int v) {
        graph.get(u).add(v);  // u -> v
        graph.get(v).add(u);  // v -> u
    }
}

Example output:

Graph adjacency list:
Node 0 -> [1, 3]
Node 1 -> [0, 2, 4]
Node 2 -> [1]
Node 3 -> [0]
Node 4 -> [1]

DFS from node 0: 0 1 2 4 3 
BFS from node 0: 0 1 3 2 4

🔢 Java Sorting Algorithms — Step-by-Step with Iterations

Sorting is a fundamental concept in programming and data structures.
Below are the five main sorting algorithms, explained in simple terms with visual examples, loop-by-loop walkthroughs, and complete Java programs.

---

🧮 1️⃣ Bubble Sort — Iteration by Iteration

💡 Concept

Bubble Sort repeatedly compares adjacent elements and swaps them if they’re in the wrong order.
With each pass, the largest element “bubbles” to the end of the array.

---

⚙️ How It Works

1. Start from the beginning of the array.

2. Compare adjacent elements.

3. Swap if the left is greater than the right.

4. Repeat until no more swaps are needed.

---

🧩 Example: [5, 4, 1, 3]

Initial Array:
[5, 4, 1, 3]

Pass 1

Comparison	Operation	Result
Compare 5 & 4	Swap	[4, 5, 1, 3]
Compare 5 & 1	Swap	[4, 1, 5, 3]
Compare 5 & 3	Swap	[4, 1, 3, 5]
✅ Largest element (5) “bubbled” to end.

Pass 2

Comparison	Operation	Result
Compare 4 & 1	Swap	[1, 4, 3, 5]
Compare 4 & 3	Swap	[1, 3, 4, 5]
✅ Second largest (4) in place.

Pass 3

Comparison	Operation	Result
Compare 1 & 3	No swap	[1, 3, 4, 5]
✅ Sorted.

---

💻 Java Code

package com.vi.sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3};
        System.out.println("Before Sorting: " + Arrays.toString(a));
        doBubbleSort(a);
        System.out.println("After Sorting: " + Arrays.toString(a));
    }

    public static void doBubbleSort(int[] a) {
        boolean sorted = false;
        int iteration = 1;
        while (!sorted) {
            sorted = true;
            System.out.println("Iteration " + iteration++ + ": " + Arrays.toString(a));
            for (int i = 0; i < a.length - 1; i++) {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    sorted = false;
                }
            }
        }
    }
}

---

🧾 Output

Before Sorting: [5, 4, 1, 3]
Iteration 1: [5, 4, 1, 3]
Iteration 2: [4, 1, 3, 5]
Iteration 3: [1, 3, 4, 5]
After Sorting: [1, 3, 4, 5]

---

🧠 Key Points

• Each pass “bubbles” the largest remaining element to the end.

• Works well for small datasets.

• Time: O(n²), Space: O(1), Stable: ✅ Yes

---

🧩 2️⃣ Insertion Sort — Iteration by Iteration

💡 Concept

Insertion Sort builds a sorted portion of the array one element at a time.
Each element is compared backward and inserted into its correct position.

---

⚙️ How It Works

1. Start from index 1.

2. Compare it to elements before it.

3. Shift larger elements to the right.

4. Insert current element into correct place.

---

🧩 Example: [5, 4, 1, 3]

---

Iteration 1 (i = 1, key = 4)

Left sorted part: [5]

Compare key=4 with previous elements:

• 4 < 5 → shift 5 →
  [5, 5, 1, 3]

Insert 4 into the empty slot:

➡️ [4, 5, 1, 3]

---

Iteration 2 (i = 2, key = 1)

Left sorted part: [4, 5]

Compare key=1 with previous elements:

• 1 < 5 → shift → [4, 5, 5, 3]

• 1 < 4 → shift → [4, 4, 5, 3]

Insert 1:

➡️ [1, 4, 5, 3]

---

Iteration 3 (i = 3, key = 3)

Left sorted part: [1, 4, 5]

Compare key=3 with previous elements:

• 3 < 5 → shift → [1, 4, 5, 5]

• 3 < 4 → shift → [1, 4, 4, 5]

• Next element is 1 (1 < 3) → stop early

Insert 3:

➡️ [1, 3, 4, 5] ✓

---

💻 Java Code

package com.vi.sort;

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3};
        System.out.println("Before Sorting: " + Arrays.toString(a));
        doInsertionSort(a);
        System.out.println("After Sorting: " + Arrays.toString(a));
    }

    public static void doInsertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
            System.out.println("Iteration " + i + ": " + Arrays.toString(a));
        }
    }
}

---

🧾 Output

Iteration 1: [4, 5, 1, 3]
Iteration 2: [1, 4, 5, 3]
Iteration 3: [1, 3, 4, 5]

---

🧠 Key Points

• Works best on nearly sorted arrays.

• Time: O(n²), Space: O(1), Stable: ✅ Yes

• Ideal for real-time insertion problems.

---

🧩 3️⃣ Selection Sort — Iteration by Iteration

💡 Concept

Selection Sort repeatedly finds the smallest element from the unsorted part and places it at the start.

---

⚙️ How It Works

1. Loop through the array to find the smallest.

2. Swap it with the first unsorted element.

3. Move the sorted boundary forward.

---

🧩 Example: [5, 4, 1, 3]

Pass	Smallest	Swap	Result
1	1	1 ↔ 5	[1, 4, 5, 3]
2	3	3 ↔ 4	[1, 3, 5, 4]
3	4	4 ↔ 5	[1, 3, 4, 5]
✅ Sorted [1, 3, 4, 5]

---

💻 Java Code

package com.vi.sort;

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3};
        System.out.println("Before Sorting: " + Arrays.toString(a));
        doSelectionSort(a);
        System.out.println("After Sorting: " + Arrays.toString(a));
    }

    public static void doSelectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            int temp = a[min];
            a[min] = a[i];
            a[i] = temp;
            System.out.println("Iteration " + (i + 1) + ": " + Arrays.toString(a));
        }
    }
}

---

🧾 Output

Iteration 1: [1, 4, 5, 3]
Iteration 2: [1, 3, 5, 4]
Iteration 3: [1, 3, 4, 5]

---

🧠 Key Points

• Simple but slow.

• Time: O(n²), Space: O(1), Stable: ❌ No.

• Best when minimizing swaps.

---

🧩 4️⃣ Merge Sort — Iteration by Iteration

💡 Concept

Merge Sort follows divide and conquer — splitting the array, sorting halves, and merging them.

---

⚙️ How It Works

1. Divide the array into halves.

2. Recursively sort each half.

3. Merge the two sorted halves.

---

🧩 Example: [5, 4, 1, 3]

Divide → [5,4] [1,3]
Sort → [4,5] [1,3]
Merge → [1,3,4,5]

Merge process:
Left [4,5], Right [1,3]
1 < 4 → pick 1
3 < 4 → pick 3
Append remaining → [1,3,4,5]

---

💻 Java Code

package com.vi.sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3};
        System.out.println("Before Sorting: " + Arrays.toString(a));
        mergeSort(a, 0, a.length - 1);
        System.out.println("After Sorting: " + Arrays.toString(a));
    }

    public static void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }

    public static void merge(int[] a, int left, int mid, int right) {
        int n1 = mid - left + 1, n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) L[i] = a[left + i];
        for (int j = 0; j < n2; j++) R[j] = a[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) a[k++] = L[i++];
            else a[k++] = R[j++];
        }
        while (i < n1) a[k++] = L[i++];
        while (j < n2) a[k++] = R[j++];
        System.out.println("Merging step: " + Arrays.toString(a));
    }
}

---

🧾 Output

Before Sorting: [5, 4, 1, 3]
Merging step: [4, 5, 1, 3]
Merging step: [4, 5, 1, 3]
Merging step: [1, 3, 4, 5]
After Sorting: [1, 3, 4, 5]

---

🧠 Key Points

• Time: O(n log n), Space: O(n)

• Stable: ✅ Yes

• Great for large datasets or linked lists.

---

🧩 5️⃣ Quick Sort — Iteration by Iteration

💡 Concept

Quick Sort also uses divide and conquer — but partitions around a pivot element.

---

⚙️ How It Works

1. Choose a pivot.

2. Partition the array around it.

3. Recursively apply on left and right sides.

---

🧩 Example: [5, 4, 1, 3]

Step 1: Pivot = 3
→ Partition → [1, 3, 5, 4]
Step 2: Left [1] sorted, right [5,4] → Pivot = 4
→ Swap → [1, 3, 4, 5] ✅

---

💻 Java Code

package com.vi.sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3};
        System.out.println("Before Sorting: " + Arrays.toString(a));
        quickSort(a, 0, a.length - 1);
        System.out.println("After Sorting: " + Arrays.toString(a));
    }

    public static void quickSort(int[] a, int low, int high) {
        if (low < high) {
            int pi = partition(a, low, high);
            System.out.println("After partition (pivot index " + pi + "): " + Arrays.toString(a));
            quickSort(a, low, pi - 1);
            quickSort(a, pi + 1, high);
        }
    }

    public static int partition(int[] a, int low, int high) {
        int pivot = a[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (a[j] < pivot) {
                i++;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        int temp = a[i + 1];
        a[i + 1] = a[high];
        a[high] = temp;
        return i + 1;
    }
}

---

🧾 Output

Before Sorting: [5, 4, 1, 3]
After partition (pivot index 1): [1, 3, 5, 4]
After partition (pivot index 3): [1, 3, 4, 5]
After Sorting: [1, 3, 4, 5]

---

🧠 Key Points

• Average: O(n log n), Worst: O(n²)

• Space: O(log n)

• Stable: ❌ No

• Used internally in Arrays.sort() for primitives.

---

📊 Sorting Algorithm Summary Table

Algorithm	Time Complexity	Space	Stable	Best Use
Bubble Sort	O(n²)	O(1)	✅	Educational, small datasets
Insertion Sort	O(n²)	O(1)	✅	Small or nearly sorted data
Selection Sort	O(n²)	O(1)	❌	Minimal swaps
Merge Sort	O(n log n)	O(n)	✅	Large or linked data
Quick Sort	O(n log n) avg	O(log n)	❌	Fast general-purpose sorting

---

🧭 Final Thoughts

• 🧮 Bubble Sort → Great for beginners.

• ✏️ Insertion Sort → Efficient for small, sorted data.

• 🧲 Selection Sort → Minimal swaps, easy to implement.

• ⚙️ Merge Sort → Predictable performance, always O(n log n).

• ⚡ Quick Sort → Industry favorite; excellent average speed.