“This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The introduction

More recently, I’ve started working on algorithms again, starting with the basics of array sorting: bubbling, selecting, merging and writing. Debugging once no problem, submission is not through, greatly hit confidence. If the sample is random and large enough, and the result is the same as the result provided by the JDK, then there is nothing wrong with the result.

Array sort logarithm

Take, for example, a self-written selection sort. The code is as follows:

private static void selectSort(int[] array){
	for (int i = 0; i < array.length; i++) {
		for (int j = i + 1; j < array.length; j++) {
			if(array[j]<array[i]){ swap(array,i,j); }}}}/** * Swap the array I and j positions *@paramArray an array of *@paramI place *@paramJ * / position
private static void swap(int[] array,int i,int j){
	array[i] = array[i] ^ array[j];
	array[j] = array[i] ^ array[j];
	array[i] = array[i] ^ array[j];
}
Copy the code

The swap method uses xOR to swap two positions in an array, but only if I! =j

The sorting algorithm in the JDK

With error-free sorting algorithms, you need the absolutely correct sorting methods provided by the JDK.

public static void comparator(int[] arr) {
	Arrays.sort(arr);
}
Copy the code

Random sample generation

Randomly generate arrays as samples for sorting comparisons.

public static int[] generateRandomArray(int maxSize, int maxValue) {
	// Generate random number range [0,maxSize]
	int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
	for (int i = 0; i < arr.length; i++) {
		// Generate the element [-maxValue,maxValue]
		arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
	}
	return arr;
}
Copy the code

Copy an array

An array that needs to be sorted using two methods needs to be copied to produce the same array.

public static int[] copyArray(int[] arr) {
	if (arr == null) {
		return null;
	}
	int[] res = new int[arr.length];
	System.arraycopy(arr, 0, res, 0, arr.length);
	return res;
}
Copy the code

Comparative approach

After the two sorting ends, whether the results are consistent needs comparison method.

public static boolean isEqual(int[] arr1, int[] arr2) {
	if ((arr1 == null&& arr2 ! =null) || (arr1 ! =null && arr2 == null)) {
		return false;
	}
	if (arr1 == null && arr2 == null) {
		return true;
	}
	if(arr1.length ! = arr2.length) {return false;
	}
	for (int i = 0; i < arr1.length; i++) {
		if(arr1[i] ! = arr2[i]) {return false; }}return true;
}
Copy the code

Perform more

public static void main(String[] args) {
	int maxSize = 100;
	int maxValue = 100;
	int testTime = 500000;
	boolean succeed = true;
	for (int i = 0; i < testTime; i++) {
		int[] arr1 = generateRandomArray(maxSize, maxValue);
		int[] arr2 = copyArray(arr1);
		selectSort(arr1);
		comparator(arr2);
		if(! isEqual(arr1, arr2)) { succeed =false;
			break;
		}
	}
	System.out.println(succeed);
}
Copy the code

conclusion

The logarithm can be used to verify the accuracy of the array sorting algorithm by comparing the results of the exact sorting algorithm with the uncertain sorting algorithm in a sufficient sample size to determine whether the algorithm is accurate or an illusion of certain data.