Bubble sort summary

The content and code of this article are from 《 Comics algorithm 》, Dialogue between Xiaohui and rhubarb , A very interesting book . Combining theory with practice , Do a test .

private static final int LEN = 20000;

	//  The first edition 
	void bubbleV1(int[] arr) {
    
		for (int i = 0; i < arr.length - 1; i++) {
    
			for (int j = 0; j < arr.length - 1 - i; j++) {
    
				int temp = 0;
				if (arr[j] > arr[j + 1]) {
    
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}

			}
			log(" The first " + (i + 1) + " round ");
			log(Arrays.toString(arr));
		}
	}

	/** *  In the first edition, if the element passes through less than arr.length-1 Round comparison has become orderly , The remaining rounds will still be compared , *  To overcome this shortcoming , Add a to judge whether the array has been ordered boolean Variable .  The second edition  * * @param arr */
	void bubbleV2(int[] arr) {
    
		for (int i = 0; i < arr.length - 1; i++) {
    
			boolean isSorted = true;
			for (int j = 0; j < arr.length - 1 - i; j++) {
    
				int temp = 0;
				log("compare " + arr[j] + " with " + arr[j + 1]);
				if (arr[j] > arr[j + 1]) {
    
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					isSorted = false;
				}

			}
			if (isSorted) {
    
				break;
			}
			log(" The first " + (i + 1) + " round ");
			log(Arrays.toString(arr));
		}
	}

	/** *  The third edition  [3,2,1,4,5,6,7,8] [2,1,3,4,5,6,7,8] [1,2,3,4,5,6,7,8] *  Suppose such an initial array , from 4 The starting elements are already orderly , But I have made many comparisons for nothing .  It is a point that needs to be optimized .  The key point of this problem is to define the ordered region in the array . *  According to the existing logic , The length of the ordered region and , The number of rounds of sorting is equal . For example, the length of the ordered area after the first round of sorting is 1,  The length of the ordered region after the second round of sorting is 2...... *  In fact, the length of the ordered region may be greater than this length , In the above example , In the second round of sorting , hinder 5 Elements already belong to the ordered region .  Therefore, the following multiple element comparisons are meaningless . *  Avoid it ： After each round of sorting , Record the location of the last element exchange , This position is the boundary without sequence , And then there's the orderly area . * * @param arr */
	void bubbleV3(int[] arr) {
    
		int lastExchangedIndex = 0;
		int sortBorder = arr.length - 1;
		for (int i = 0; i < arr.length - 1; i++) {
    
			boolean isSorted = true;
			for (int j = 0; j < sortBorder; j++) {
    
				int temp = 0;
				log("compare " + arr[j] + " with " + arr[j + 1]);
				if (arr[j] > arr[j + 1]) {
    
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					isSorted = false;
					lastExchangedIndex = j;
				}

			}
			sortBorder = lastExchangedIndex;
			log("border:" + sortBorder);
			if (isSorted) {
    
				break;
			}
			log(" The first " + (i + 1) + " round ");
			log(Arrays.toString(arr));
		}
	}

	/** *  The Fourth Edition ( Cocktail ordering ) [2,3,4,5,6,7,8,1]  The above example , The first three version sorting methods need to be sorted 7 round , However, most of the data are orderly . *  To overcome this shortcoming . * * @param arr */
	void bubbleV4(int[] arr) {
    
		int temp = 0;
		for (int i = 0; i < arr.length / 2; i++) {
    
			//  Orderly marking , The initial value of each round is true
			boolean isSorted = true;
			//  Odd round , Compare and exchange from left to right 
			for (int j = i; j < arr.length - 1 - i; j++) {
    
				log("compare " + arr[j] + " with " + arr[j + 1]);
				if (arr[j] > arr[j + 1]) {
    
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					isSorted = false;
				}

			}
			if (isSorted) {
    
				break;
			}
			log(" The first " + (i + 1) + " round ");
			log(Arrays.toString(arr));

			//  Even round , Compare and exchange from right to left 
			isSorted = true;
			for (int k = arr.length - 1 - i; k > i; k--) {
    
				if (arr[k] < arr[k - 1]) {
    
					temp = arr[k];
					arr[k] = arr[k - 1];
					arr[k - 1] = temp;
					isSorted = false;
				}
			}
			if (isSorted) {
    
				break;
			}
			log(" The first " + (i + 2) + " round ");
			log(Arrays.toString(arr));
		}
	}

	@Test
	public void test() {
    
		// int[] arr={3,2,1,4,5,6,7,8};
		int[] arr = {
     2, 3, 4, 5, 6, 7, 8, 1 };
		// int[] arr={5,8,6,3,9,2,1,7};
		// int[] arr={25, 58, 29, 3, 21, 3, 60, 46, 79, 15};
		// bubbleV1(arr);
		// bubbleV2(arr);
		// bubbleV3(arr);
		bubbleV4(arr);
		log(Arrays.toString(arr));

	}

	@Test
	public void test2() {
    
		int[] arr2 = new int[LEN];
		Random random = new Random();
		for (int i = 0; i < LEN; i++) {
    
			arr2[i] = random.nextInt(100);
		}
		// log(Arrays.toString(arr2));

		long begin, end;

		begin = System.currentTimeMillis();
		bubbleV1(arr2);
		end = System.currentTimeMillis();
		System.out.println(end - begin);

		begin = System.currentTimeMillis();
		bubbleV2(arr2);
		end = System.currentTimeMillis();
		System.out.println(end - begin);

		begin = System.currentTimeMillis();
		bubbleV3(arr2);
		end = System.currentTimeMillis();
		System.out.println(end - begin);

		begin = System.currentTimeMillis();
		bubbleV4(arr2);
		end = System.currentTimeMillis();
		System.out.println(end - begin);

	}

	void log(String x) {
    
		if (false) {
    
			System.out.println(x);
		}
	}

Use them separately 1 Ten thousand elements and 2 Test 10000 integer data , give the result as follows

Method version	The length of the array ( ten thousand )	Time consuming (ms)
1	1	2833
2	1	3
3	1	2
4	1	2
1	2	10475
2	2	4
3	2	3
4	2	3