Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Selection Sort for String Arrays

Problem Statement

Write a Java program that extends the Selection Sort implementation to sort an array of strings lexicographically in ascending order (based on Unicode values, case-sensitive). The program should count the number of swaps performed and test with string arrays containing strings of varying lengths (short, medium, long) and cases (mixed upper/lowercase, all lowercase), including edge cases like empty arrays and arrays with duplicate strings. Selection Sort will find the lexicographically smallest string in each pass and swap it with the first unsorted element. You can visualize this as organizing a list of words alphabetically, selecting the "smallest" word (e.g., "apple" before "Banana") to build the sorted list.

Input:

  • An array of strings to be sorted lexicographically. Output: The sorted array, the number of swaps performed, and a string representation of the input and sorted arrays for clarity. Constraints:
  • The array length n is between 0 and 10^5.
  • Strings can be of any length and contain any valid Unicode characters. Example:
  • Input: array = ["banana", "Apple", "cherry", "date"]
  • Output:
    • Input Array: [banana, Apple, cherry, date]
    • Sorted Array: [Apple, banana, cherry, date]
    • Swaps: 2
  • Explanation: Selection Sort sorts lexicographically (case-sensitive, "Apple" < "banana"), requiring 2 swaps.
  • Input: array = ["cat", "Cat", "CAT"]
  • Output:
    • Input Array: [cat, Cat, CAT]
    • Sorted Array: [CAT, Cat, cat]
    • Swaps: 2
  • Explanation: Case-sensitive sorting places uppercase before lowercase, 2 swaps.

Pseudocode

FUNCTION selectionSort(arr)
    SET n to length of arr
    CREATE swaps as integer, initialized to 0
    FOR i from 0 to n-1
        SET minIdx to i
        FOR j from i+1 to n-1
            IF arr[j] < arr[minIdx] THEN
                SET minIdx to j
            ENDIF
        ENDFOR
        IF minIdx != i THEN
            SET temp to arr[i]
            SET arr[i] to arr[minIdx]
            SET arr[minIdx] to temp
            INCREMENT swaps
        ENDIF
    ENDFOR
    RETURN swaps
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of input string arrays
    FOR each testCase in testCases
        PRINT test case details
        CREATE copy of testCase array
        SET swaps to selectionSort(copy)
        PRINT input array, sorted array, and swaps
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define selectionSort (generic): a. Accept an array of Comparable<T> type (use String for testing). b. Initialize a counter swaps to 0. c. For each index i from 0 to n-1:
    • Find the index minIdx of the lexicographically smallest element in arr[i..n-1] using compareTo.
    • If minIdx != i, swap arr[i] with arr[minIdx] and increment swaps. d. Return the number of swaps.
  2. Define toString: a. Convert the array to a string, e.g., "[banana, Apple, cherry]".
  3. In main, test with: a. Mixed case strings (short, n=4). b. Mixed case strings with duplicates (n=5). c. Long strings (n=6). d. Empty array (n=0). e. Single-element array (n=1). f. All lowercase strings (n=7).

Java Implementation

import java.util.*;

public class SelectionSortStringArray {
    // Performs Selection Sort for Comparable types and counts swaps
    public <T extends Comparable<T>> int selectionSort(T[] arr) {
        int n = arr.length;
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j].compareTo(arr[minIdx]) < 0) {
                    minIdx = j;
                }
            }
            if (minIdx != i) {
                T temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
                swaps++;
            }
        }
        return swaps;
    }

    // Converts array to string
    public <T> String toString(T[] arr) {
        StringBuilder result = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            result.append(arr[i]);
            if (i < arr.length - 1) {
                result.append(", ");
            }
        }
        result.append("]");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        String[] arr;
        String description;

        TestCase(String[] arr, String description) {
            this.arr = arr;
            this.description = description;
        }
    }

    // Main method to test string Selection Sort
    public static void main(String[] args) {
        SelectionSortStringArray sorter = new SelectionSortStringArray();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new String[]{"banana", "Apple", "cherry", "date"}, "Mixed case (n=4)"),
            new TestCase(new String[]{"cat", "Cat", "CAT", "cat", "Dog"}, "Mixed case with duplicates (n=5)"),
            new TestCase(new String[]{"elephant", "giraffe", "hippopotamus", "rhinoceros", "zebra", "antelope"}, "Long strings (n=6)"),
            new TestCase(new String[]{}, "Empty (n=0)"),
            new TestCase(new String[]{"single"}, "Single element (n=1)"),
            new TestCase(new String[]{"apple", "banana", "cherry", "date", "elderberry", "fig", "grape"}, "All lowercase (n=7)")
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ": " + testCases[i].description);
            String[] arr = testCases[i].arr.clone(); // Copy to preserve original
            System.out.println("Input Array: " + sorter.toString(arr));
            int swaps = sorter.selectionSort(arr);
            System.out.println("Sorted Array: " + sorter.toString(arr));
            System.out.println("Swaps: " + swaps + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1: Mixed case (n=4)
Input Array: [banana, Apple, cherry, date]
Sorted Array: [Apple, banana, cherry, date]
Swaps: 2

Test case 2: Mixed case with duplicates (n=5)
Input Array: [cat, Cat, CAT, cat, Dog]
Sorted Array: [CAT, Cat, Dog, cat, cat]
Swaps: 4

Test case 3: Long strings (n=6)
Input Array: [elephant, giraffe, hippopotamus, rhinoceros, zebra, antelope]
Sorted Array: [antelope, elephant, giraffe, hippopotamus, rhinoceros, zebra]
Swaps: 5

Test case 4: Empty (n=0)
Input Array: []
Sorted Array: []
Swaps: 0

Test case 5: Single element (n=1)
Input Array: [single]
Sorted Array: [single]
Swaps: 0

Test case 6: All lowercase (n=7)
Input Array: [apple, banana, cherry, date, elderberry, fig, grape]
Sorted Array: [apple, banana, cherry, date, elderberry, fig, grape]
Swaps: 0

Explanation:

  • Test case 1: Mixed case strings, 2 swaps ("Apple" before "banana" due to case).
  • Test case 2: Mixed case with duplicates, 4 swaps (uppercase "CAT" first).
  • Test case 3: Long strings, 5 swaps to sort lexicographically.
  • Test case 4: Empty array, 0 swaps.
  • Test case 5: Single element, 0 swaps.
  • Test case 6: Already sorted lowercase strings, 0 swaps.

How It Works

  • selectionSort:
    • Uses generics with Comparable<T> to handle String arrays.
    • Finds the lexicographically smallest string in each pass using compareTo.
    • Swaps if needed, counts swaps, and builds the sorted array.
  • toString: Formats array as a string, handling String elements.
  • Example Trace (Test case 1):
    • Pass 1: Find min="Apple" at index 1, swap with "banana": [Apple, banana, cherry, date] (1 swap).
    • Pass 2: Find min="banana", no swap: [Apple, banana, cherry, date].
    • Pass 3: Find min="cherry", no swap: [Apple, banana, cherry, date].
    • Pass 4: Find min="date", no swap. Total swaps: 2.
  • Main Method: Tests mixed case, duplicates, long strings, empty, single element, and lowercase arrays.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
selectionSortO(n²)O(1)
toStringO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n²) for selectionSort (n passes, up to n comparisons each); O(n) for toString. String comparisons depend on string length, but this is not included in standard analysis.
  • Space complexity: O(1) for selectionSort (in-place); O(n) for toString (string builder).
  • Selection Sort performs O(n²) comparisons, with swaps O(n) in the worst case.

✅ Tip: Use generics with Comparable to extend Selection Sort to strings, leveraging compareTo for lexicographical ordering. Test with mixed cases to understand case-sensitive sorting.

⚠ Warning: Java’s compareTo is case-sensitive (uppercase before lowercase). For case-insensitive sorting, use compareToIgnoreCase. Handle empty arrays to avoid index errors.