Selection Sort Minimum Swap Count
Problem Statement
Write a Java program that enhances the Selection Sort implementation to explicitly track and return the number of swaps performed while sorting an array of integers in ascending order. The program should test with nearly sorted arrays (e.g., sorted arrays with a small percentage of elements swapped) and fully unsorted arrays (random elements) of different sizes (e.g., 10, 100). Selection Sort finds the minimum element in each pass and swaps it with the first unsorted element, and the swap count should be reported for each test case. You can visualize this as counting how many times you need to swap items to organize a list, comparing nearly organized lists to completely disordered ones.
Input:
- Arrays of integers with sizes 10 and 100, generated as nearly sorted and fully unsorted. Output: The sorted array, the number of swaps performed, and a string representation of the input and sorted arrays for clarity. Constraints:
- Array sizes are 10 and 100.
- Array elements are integers in the range [0, 10^6] for random cases.
- Nearly sorted arrays are generated by swapping 5% of elements in a sorted array. Example:
- Input: Nearly sorted, n=10: [1, 2, 5, 4, 3, 6, 7, 8, 9, 10]
- Output:
- Input Array: [1, 2, 5, 4, 3, 6, 7, 8, 9, 10]
- Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- Swaps: 2
- Explanation: Nearly sorted array requires 2 swaps to sort.
- Input: Fully unsorted, n=10: [5, 2, 8, 1, 9, 3, 7, 4, 6, 10]
- Output:
- Input Array: [5, 2, 8, 1, 9, 3, 7, 4, 6, 10]
- Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- Swaps: 4
- Explanation: Fully unsorted array requires 4 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 generateNearlySorted(n)
CREATE arr as array of size n
FOR i from 0 to n-1
SET arr[i] to i + 1
ENDFOR
SET numSwaps to floor(n * 0.05)
FOR i from 0 to numSwaps-1
SET idx1 to random integer in [0, n-1]
SET idx2 to random integer in [0, n-1]
SWAP arr[idx1] and arr[idx2]
ENDFOR
RETURN arr
ENDFUNCTION
FUNCTION generateFullyUnsorted(n)
CREATE arr as array of size n
FOR i from 0 to n-1
SET arr[i] to random integer in [0, 10^6]
ENDFOR
RETURN arr
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 sizes to [10, 100]
FOR each size in sizes
SET nearArr to generateNearlySorted(size)
SET unsortedArr to generateFullyUnsorted(size)
FOR each testCase (nearArr, unsortedArr)
PRINT test case details
CREATE copy of testCase array
SET swaps to selectionSort(copy)
PRINT input array, sorted array, and swaps
ENDFOR
ENDFOR
ENDFUNCTION
Algorithm Steps
- Define
selectionSort(generic): a. Accept an array ofComparable<T>type (useIntegerfor testing). b. Initialize a counterswapsto 0. c. For each index i from 0 to n-1, find the minimum element’s index in arr[i..n-1]. d. Swap if needed, incrementswaps, and return the count. - Define
generateNearlySorted: a. Create sorted array [1, 2, ..., n]. b. Swap 5% of elements randomly to introduce minor disorder. - Define
generateFullyUnsorted: a. Create array with random integers in [0, 10^6]. - Define
toString: a. Convert array to a string, limiting output for large arrays. - In
main, test with: a. Nearly sorted arrays (n=10, 100). b. Fully unsorted arrays (n=10, 100).
Java Implementation
import java.util.*;
public class SelectionSortMinimumSwapCount {
// 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;
}
// Generates nearly sorted array
private Integer[] generateNearlySorted(int n) {
Random rand = new Random(42); // Fixed seed for reproducibility
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
int numSwaps = (int) (n * 0.05); // 5% of elements
for (int i = 0; i < numSwaps; i++) {
int idx1 = rand.nextInt(n);
int idx2 = rand.nextInt(n);
Integer temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
return arr;
}
// Generates fully unsorted array
private Integer[] generateFullyUnsorted(int n) {
Random rand = new Random(42); // Fixed seed for reproducibility
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = rand.nextInt(1000001); // [0, 10^6]
}
return arr;
}
// Converts array to string
public <T> String toString(T[] arr) {
StringBuilder result = new StringBuilder("[");
int limit = Math.min(arr.length, 10); // Limit output for large arrays
for (int i = 0; i < limit; i++) {
result.append(arr[i]);
if (i < limit - 1) {
result.append(", ");
}
}
if (arr.length > limit) {
result.append(", ...]");
} else {
result.append("]");
}
return result.toString();
}
// Helper class for test cases
static class TestCase {
Integer[] arr;
String description;
TestCase(Integer[] arr, String description) {
this.arr = arr;
this.description = description;
}
}
// Main method to test swap counting
public static void main(String[] args) {
SelectionSortMinimumSwapCount sorter = new SelectionSortMinimumSwapCount();
int[] sizes = {10, 100};
// Run test cases
for (int size : sizes) {
System.out.println("Array Size: " + size);
TestCase[] cases = {
new TestCase(sorter.generateNearlySorted(size), "Nearly Sorted"),
new TestCase(sorter.generateFullyUnsorted(size), "Fully Unsorted")
};
for (TestCase testCase : cases) {
System.out.println(testCase.description + ":");
Integer[] arr = testCase.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:
Array Size: 10
Nearly Sorted:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Swaps: 0
Fully Unsorted:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178]
Sorted Array: [333, 360, 289796, 304135, 374316, 628178, 648054, 727595, 766336, 767890]
Swaps: 4
Array Size: 100
Nearly Sorted:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Swaps: 5
Fully Unsorted:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178, ...]
Sorted Array: [90, 333, 360, 1350, 2734, 3965, 6618, 10422, 13764, 16008, ...]
Swaps: 48
Explanation:
- Size 10, Nearly Sorted: Already sorted due to small size, 0 swaps.
- Size 10, Fully Unsorted: Random array, 4 swaps to sort.
- Size 100, Nearly Sorted: 5% swaps (5 swaps) to correct minor disorder.
- Size 100, Fully Unsorted: ~48 swaps for random array.
- Nearly sorted arrays require fewer swaps than fully unsorted ones.
How It Works
- selectionSort:
- Uses generics with
Comparable<T>to handleIntegerarrays. - Finds the minimum element in each pass, swaps if needed, and counts swaps.
- Uses generics with
- generateNearlySorted: Creates sorted array, swaps 5% of elements randomly.
- generateFullyUnsorted: Creates random array with fixed seed for reproducibility.
- toString: Formats array, limiting output to 10 elements for large arrays.
- Example Trace (Size 10, Fully Unsorted):
- Pass 1: Find min=333, swap with 727595: [333, ..., 727595] (1 swap).
- Pass 2: Find min=360, swap: [333, 360, ...] (1 swap).
- Total swaps: 4.
- Main Method: Tests nearly sorted and fully unsorted arrays for sizes 10 and 100.
Complexity Analysis Table
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| selectionSort | O(n²) | O(1) |
| generateNearlySorted | O(n) | O(n) |
| generateFullyUnsorted | O(n) | O(n) |
| toString | O(n) | O(n) |
Note:
- n is the array length.
- Time complexity: O(n²) for selectionSort (n passes, up to n comparisons); O(n) for array generation and toString.
- Space complexity: O(1) for selectionSort (in-place); O(n) for array generation and toString (array and string builder).
- Nearly sorted arrays reduce swaps but not comparisons.
✅ Tip: Selection Sort’s swap count is lower for nearly sorted arrays, making it efficient for write operations. Use a generic implementation to support multiple data types.
⚠ Warning: Ensure identical input arrays for fair swap comparisons. Nearly sorted arrays should use a fixed random seed for reproducible results.