This article describes the implementation method of parity sorting of Java exchange sorting. Share it for your reference. The details are as follows:
Parity sort, or parity transposition sort, or brick sort, is a relatively simple sorting algorithm that was originally invented for parallel computing with local interconnects. This is a comparative sort similar to the characteristics of bubble sorting.
In this algorithm, by comparing adjacent (odd-even) position numeric pairs in the array, if the odd-even pair is in the wrong order (the first one is greater than the second one), then exchange. Repeat the next step, but for all (even-odd) position numeric pairs. Keep going like this alternately.
Sorting of processor arrays
In parallel computing sorting, each processor processes one value corresponding to it and has only local interconnects with the left and right neighbors. All processors can compare and exchange operations with neighbors at the same time, alternately in odd-even, even-even-odd order. The algorithm was originally published by Habermann in 1972 and demonstrated its efficiency in parallel processing.
The algorithm can be effectively extended to cases where each processor has multiple values. In the BaudetStevenson Parity Merge Partitioning Algorithm, each processor sorts the subarrays it owns at each step, and then performs a merge partition or transposition merging with the neighbors.
Batcher parity and even sorting
Batcher parity sorting is a relevant but more efficient sorting algorithm that uses comparison-exchange and perfect-shuffle operations.
Batcher's approach is very efficient on parallel computing processors with extensive interconnection.
Worst time complexity/Theta(n^2)
The parity sort dynamic graph is as follows:
Code implementation:
package com.baobaotao.test; /** * Sort research* */ public class Sort { /** <span style="white-space:pre"> </span> * Parity sort<span style="white-space :pre"> </span> * @param array <span style="white-space:pre"> </span> */ public static void batcherSort(int[] array) { int length = array.length ; boolean flag = true ; while(true) { flag = true ; for(int i=1;i<length-1;i+=2) { if(array[i] > array[i+1]) { swap(array, i , i+1) ; flag = false ; } } for(int i=0;i<length-1;i+=2) { if(array[i] > array[i+1]) { swap(array, i , i+1) ; flag = false ; } } if(flag) break ; printArr(array) ; } } /** * Exchange arrays in order from small to large* @param a Array passed in * @param b The number to be exchanged b * @param c The number to be exchanged c */ public static void swap(int[] a, int b, int c) { int temp = 0 ; if(b < c) { if(a[b] > a[c]) { temp = a[b] ; a[b] = a[c] ; a[c] = temp ; } } } /** * Print array* @param array */ public static void printArr(int[] array) { for(int c : array) { System.out.print(c + " "); } System.out.println(); } public static void main(String[ ] args) { int[] number={11,95,45,15,78,84,51,24,12} ; batcherSort(number) ; } }Output analysis:
11 45 15 95 51 78 12 84 2411 15 45 51 12 95 24 78 8411 15 12 45 24 51 78 95 8411 12 15 24 45 51 78 84 95
I hope this article will be helpful to everyone's Java programming.