2929. Design Pattern - StrategyStrategy Pattern
Behavioral Pattern: Strategy Pattern.
1. Strategy Pattern
A Strategy defines a set of algorithms that can be used interchangeably. Use the strategy pattern when:
- Many related classes differ only in their behavior.
- You need different variants of an algorithm.
- An algorithm uses data that client shouldn’t know about.
- You need to vary a behavior’s algorithm at run-time.
2. Implementation
2.1 Strategy Interface
public interface Sorting {
public int[] sort(int[] nums);
}
2.2 Sorting Algorithms
public class BubbleSort implements Sorting {
@Override
public int[] sort(int[] nums) {
System.out.println("Bubble sort on array:" + Arrays.toString(nums));
if (nums == null || nums.length < 2) {
return nums;
}
for (int i = 0; i < nums.length; i++) {
for (int j = nums.length - 1; j > i; j--) {
if (nums[j] < nums[j - 1]) {
int temp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = temp;
}
}
}
return nums;
}
}
public class MergeSort implements Sorting {
@Override
public int[] sort(int[] nums) {
System.out.println("Merge sort on array:" + Arrays.toString(nums));
if (nums == null || nums.length < 2) {
return nums;
}
helper(nums, 0, nums.length - 1);
return nums;
}
private void helper(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
helper(nums, start, mid);
helper(nums, mid + 1, end);
merge(nums, start, mid, end);
}
private void merge(int[] nums, int start, int mid, int end) {
int[] copy = Arrays.copyOf(nums, nums.length);
int left = start;
int right = mid + 1;
for (int k = start; k <= end; k++) {
if (left > mid) { // no item at left
nums[k] = copy[right];
right++;
}
else if(right > end) { // no item at right
nums[k] = copy[left];
left++;
}
else if (copy[left] <= copy[right]) {
nums[k] = copy[left];
left++;
}
else{
nums[k] = copy[right];
right++;
}
}
}
}
public class QuickSort implements Sorting {
@Override
public int[] sort(int[] nums) {
System.out.println("Quick sort on array:" + Arrays.toString(nums));
if (nums == null || nums.length < 2) {
return nums;
}
helper(nums, 0, nums.length - 1);
return nums;
}
private void helper(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int pivot = partition(nums, start, end);
helper(nums, start, pivot - 1);
helper(nums, pivot + 1, end);
}
// one way
private int partition(int[] nums, int start, int end) {
int pivot = start; // select the first as the pivot
for (int i = start + 1; i <= end; i++) {
if (nums[i] < nums[start]) {
pivot++;
int temp = nums[pivot];
nums[pivot] = nums[i];
nums[i] = temp;
}
}
int temp = nums[pivot];
nums[pivot] = nums[start];
nums[start] = temp;
return pivot;
}
}
2.3 Context
public class Context {
private Sorting sorting;
public Context(Sorting sorting){
this.sorting = sorting;
}
public int[] executeStrategy(int[] nums){
return sorting.sort(nums);
}
}
2.4 Client
public class Client {
public void run() {
int[] nums = new int[]{3,5,1,8,2,9,7,4};
Context context = new Context(new BubbleSort());
System.out.println(Arrays.toString(context.executeStrategy(nums.clone())));
context = new Context(new MergeSort());
System.out.println(Arrays.toString(context.executeStrategy(nums.clone())));
context = new Context(new QuickSort());
System.out.println(Arrays.toString(context.executeStrategy(nums.clone())));
}
}
Output.
Bubble sort on array:[3, 5, 1, 8, 2, 9, 7, 4]
[1, 2, 3, 4, 5, 7, 8, 9]
Merge sort on array:[3, 5, 1, 8, 2, 9, 7, 4]
[1, 2, 3, 4, 5, 7, 8, 9]
Quick sort on array:[3, 5, 1, 8, 2, 9, 7, 4]
[1, 2, 3, 4, 5, 7, 8, 9]