|
| 1 | +package Sorts; |
| 2 | + |
| 3 | +/* Java program for Bitonic Sort. Note that this program |
| 4 | +works only when size of input is a power of 2. */ |
| 5 | +public class BitonicSort |
| 6 | +{ |
| 7 | + /* The parameter dir indicates the sorting direction, |
| 8 | + ASCENDING or DESCENDING; if (a[i] > a[j]) agrees |
| 9 | + with the direction, then a[i] and a[j] are |
| 10 | + interchanged. */ |
| 11 | + void compAndSwap(int a[], int i, int j, int dir) |
| 12 | + { |
| 13 | + if ( (a[i] > a[j] && dir == 1) || |
| 14 | + (a[i] < a[j] && dir == 0)) |
| 15 | + { |
| 16 | + // Swapping elements |
| 17 | + int temp = a[i]; |
| 18 | + a[i] = a[j]; |
| 19 | + a[j] = temp; |
| 20 | + } |
| 21 | + } |
| 22 | + |
| 23 | + /* It recursively sorts a bitonic sequence in ascending |
| 24 | + order, if dir = 1, and in descending order otherwise |
| 25 | + (means dir=0). The sequence to be sorted starts at |
| 26 | + index position low, the parameter cnt is the number |
| 27 | + of elements to be sorted.*/ |
| 28 | + void bitonicMerge(int a[], int low, int cnt, int dir) |
| 29 | + { |
| 30 | + if (cnt>1) |
| 31 | + { |
| 32 | + int k = cnt/2; |
| 33 | + for (int i=low; i<low+k; i++) |
| 34 | + compAndSwap(a,i, i+k, dir); |
| 35 | + bitonicMerge(a,low, k, dir); |
| 36 | + bitonicMerge(a,low+k, k, dir); |
| 37 | + } |
| 38 | + } |
| 39 | + |
| 40 | + /* This funcion first produces a bitonic sequence by |
| 41 | + recursively sorting its two halves in opposite sorting |
| 42 | + orders, and then calls bitonicMerge to make them in |
| 43 | + the same order */ |
| 44 | + void bitonicSort(int a[], int low, int cnt, int dir) |
| 45 | + { |
| 46 | + if (cnt>1) |
| 47 | + { |
| 48 | + int k = cnt/2; |
| 49 | + |
| 50 | + // sort in ascending order since dir here is 1 |
| 51 | + bitonicSort(a, low, k, 1); |
| 52 | + |
| 53 | + // sort in descending order since dir here is 0 |
| 54 | + bitonicSort(a,low+k, k, 0); |
| 55 | + |
| 56 | + // Will merge wole sequence in ascending order |
| 57 | + // since dir=1. |
| 58 | + bitonicMerge(a, low, cnt, dir); |
| 59 | + } |
| 60 | + } |
| 61 | + |
| 62 | + /*Caller of bitonicSort for sorting the entire array |
| 63 | + of length N in ASCENDING order */ |
| 64 | + void sort(int a[], int N, int up) |
| 65 | + { |
| 66 | + bitonicSort(a, 0, N, up); |
| 67 | + } |
| 68 | + |
| 69 | + /* A utility function to print array of size n */ |
| 70 | + static void printArray(int arr[]) |
| 71 | + { |
| 72 | + int n = arr.length; |
| 73 | + for (int i=0; i<n; ++i) |
| 74 | + System.out.print(arr[i] + " "); |
| 75 | + System.out.println(); |
| 76 | + } |
| 77 | + |
| 78 | + public static void main(String args[]) |
| 79 | + { |
| 80 | + int a[] = {3, 7, 4, 8, 6, 2, 1, 5}; |
| 81 | + int up = 1; |
| 82 | + BitonicSort ob = new BitonicSort(); |
| 83 | + ob.sort(a, a.length,up); |
| 84 | + System.out.println("\nSorted array"); |
| 85 | + printArray(a); |
| 86 | + } |
| 87 | +} |
| 88 | + |
0 commit comments