“Confusing even and odd sorting.”

Parity sorting

Java data structures and algorithms after class programming questions simple sorting 3.4

The original sentence
3.4 Another simple sorting algorithm is parity sorting. The idea is to repeat two scans in the array. The first scan selects all pairs of data items, a[I] and a[j+1], where j is odd (j=1, 3, 5...). . If the values of their keywords are in reverse order, they are swapped. The second scan does the same for all even-numbered items (j= 2,4,6...). . Repeat this sort twice until the array is all sorted. Replace the bubbleSort() method in the bubblesort.java program (Listing 3.1) with the oddEvenSort() method. To make sure it can run in sorts of different data volumes, you also need to figure out the number of two scans.Copy the code
Interpretation of the

The idea given in the original sentence can be seen to be very clear (the previous several questions are also, the idea given is also very clear, although few but give a feeling that you can read it all at once)

In a word

An array that compares two neighbors starting with the odd digits and then starting with the even digits. It’s always comparing two adjacent elements.

First post code

public class ArrayBub {
	private long[] a;
	private int nElems;
	//
	public ArrayBub(int max) {
		a = new long[max];
		nElems = 0;
	}
	//
	public void insert(long newV) {
		a[nElems++] = newV;		
	}
	//
	public void display(a) {
		for (int i = 0 ; i < nElems; i++) {
			System.out.print(a[i] + "");
		}
		System.out.println();
	}
	
	//
	public void oddEvenSort(a) {
		int oe;		
		boolean sorted = false;
		int i;
		
		while(! sorted) { sorted =true;
			
			for (oe = 0; oe < 2; oe++) {
                                // parallel traversal, successively as the starting point
				for (i = oe; i < nElems-1; i+=2) {
					if (a[i] > a[i+1]) {
						sorted = false;
                                                // Indicates that there are non-ascending pairs. Changing the Boolean value indicates that sorting needs to continue
						// A non-ascending pair is encountered
						swap(i, i+1);
					}
				}
			}
		}
	}
	
	//
	public void swap(int one, int two) {
		long temp = a[one];
		a[one] = a[two];
		a[two] = temp;
	}
	// The value of the corresponding coordinate is swapped
}

/ / verification
public class ArrayBubApp {
	public static void main(String[] args) {
		int maxSize = 10;	
		//
		ArrayBub arr3;
		arr3 = new ArrayBub(maxSize);
		arr3.insert(7);
		arr3.insert(8);
		arr3.insert(6);
		arr3.insert(5);
		arr3.insert(4);
		arr3.insert(3);
		arr3.insert(2);
		arr3.insert(1);
		arr3.insert(0);
		arr3.insert(-1);
		//
		System.out.println(Before the "odd");
		arr3.display();
		//
		System.out.println("Odd"); arr3.oddEvenSort(); arr3.display(); }}// Console outputBefore the odd7 8 6 5 4 3 2 1 0 -1After the odd -1 0 1 2 3 4 5 6 7 8 
Copy the code
The code analysis

1. The special thing about this code is that if you’ve written bubble sort and you thought it was cool enough to control the end of the traversal by dynamically decreasing out from n, then you’ll definitely feel new here as well.

It’s not the end of the loop, but it’s the beginning of the loop, it’s going from zero to one, and it’s going to control the beginning of the loop each time.

2. Every time I jumps to the next parity bit, I’m still comparing the two adjacent elements.

When actually debugging, it will be found that the yellow bar jumps inexplicably. This is a recorded GIF of the whole debugging process

After reading it, people just want to slowly draw a question mark on their forehead, and there is no very intuitive trend of change.

At this time, you can write again on paper, after all, too puzzling.

The experimental data were used

7, 8, 6, 5, 4, 3, 2, 1Copy the code
drawing

The seller show

Buyers show

It’s hard to tell at this point,

Although I wrote from beginning to end, I still don’t know how it somehow became an ascending order — slowly beat a clam??

But at least once you write it you know that the two elements will be ordered (the pairs in parentheses are always ordered), which is the most intuitive for even pairs in the first round.

I still can’t see how it does that.

Change the data to a person’s height and see how they rank.

As can be seen from the picture, 1.8 meters was imperceptibly changed to the last position.

In the last round, 1.2 was moved to the front of 1.3, just behind 1.1

Speaking of 1.1, it has also been moved from the back to the front

Overall, the position of meter 8 is underlined from the upper left corner to the lower right corner, as is meter 7. 1.6 meters is also underlined and then doubled back

If you recall how bubble sort works, you compare two adjacent elements, and then the largest element is moved to the end.

To do that, you have to compare all the elements in the array in pairs to make sure that they are sorted in ascending order.

The connection between this problem and bubbling is that it must have been compared.

This time again will see the above 1.8 meters:

It was in the odd digit, and then it was in the even digit, and then it was in the odd digit, and then it was in the even digit, and then it was in the odd digit, and then it was in the even digit, and then it was in the right digit, and then it was in the last digit.Copy the code

And then, you see, all the other elements are like this, the odd digit, the next digit is going to be in the even digit, and then you compare them in pairs.

In this way, every two or two elements are compared to each other successively. Always end up bigger (smaller) and moved to the front or back.

conclusion

It turns out that odd and even sorting actually works the same way as bubbling, by comparing all the elements in pairs, and finally determining the maximum value, the minimum value will also be compared to the first.

That’s why some bloggers say, right

Odd-Even Sort

This is basically a variation of bubble-sort.

So, even and odd sort is not that hard to write, two zeros and ones as a starting point for different traversals. Compare adjacent elements.

How do you do that? In fact, it works the same way as bubbling, comparing adjacent elements in pairs in different order until the smallest element is moved to the front and the largest element is moved to the back.

reference

Data Structures and Algorithms (Java) – Odd-even Sorting – Bluesky’s article – Zhihu

Odd – even sort – Wikipedia