|
RadixSort |
Tests |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>public class RadixSort
/*> Use LSD (least significant digit) method by repeatedly sorting digits by single digit from right to left Given: {
170, 45, 75, 90, 802, 2, 66 }
Treat all
values as having same number of digits:
Given: { 170, 045, 075, 090, 802, 002, 066 }
1st Pass: { 170, 090, 802, 002, 045, 075, 066 }> 2nd Pass: { 802, 002, 045, 066, 170, 075, 090
}
pre
data-role="codeBlock"
data-info="js" class="language-javascript"> 3rd Pass: { 002, 045, 066, 075, 090, 170, 802 }>*/>
static
void sort(int [] a)
{> // Determine number of digits> int max = Arrays.stream(a).max().getAsInt();
int digits = (int)Math.log10(max) +
1;
for(int exp = 0; exp digits;
++exp)
{> countSort(a, (int)Math.pow(10, exp));
}> }> private
static void countSort(int[] a, int exp)
{
// Considering input as: { 170, 45,
75, 90, 802, 2, 66 }
int[] count = new
int[10];
> for(int i = 0; i a.length; ++i)> {> count[a[i] / exp % 10]++;> }
// Count
// Index: 0 1 2 3 4 5 6 7
8 9
// 1st: 2 0 2 0 0 2 1 0 0 0
// 2nd:> > for(int i = 1; i 10; ++i) > {> count[i] += count[i - 1];> }
// Count
// Index: 0 1 2 3 4 5 6 7
8 9
// 1st: 2 2 4 4 4 4 6 7 7 7
// 2nd:> > int[] result = new int[a.length]; > for(int i = a.length - 1; i = 0; --i)> {> result[count[a[i] / exp % 10] - 1] = a[i]; > count[a[i] / exp % 10]--;> }> // Index; 0 1 2 3 4 5 6 7 8 9> // Result:>
System.arraycopy(result, 0, a, 0, a.length);> }
} |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass() int[] data =
{ 170, 45, 75, 90, 802, 2, 66 };
sort(data);
boolean check =
Arrays.equals(new int[] {2, 45, 66, 75, 90, 170, 802}, data);> if(!check)
{
return false;> }> return true; }
|
Sort
Tests
boolean swapped;do> {> swapped = false;> for(int i = 1; i a.length; ++i)> {> if(a[i - 1] a[i])> {> swapped = true;> swap(a, i, i - 1);> }> }} while(swapped);}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>private static int partition(int[] a, int left, int right)> int pivot = a[(left + right) / 2];> while(left = right)> {while(a[left] pivot) left++;while(a[right] pivot) right--;if(left = right){> swap(a, left++, right--);> }> }return left;}> >private static void quickSort(int[] a, int left, int right)int idx = partition(a, left, right);if(left idx - 1){> quickSort(a, left, idx - 1);> }> if(idx right)> {quickSort(a, idx, right);}>}>> quickSort(a, 0, a.length - 1);>}if(a.length 2){> return;> }int mid = a.length / 2;int[] left = new int[mid];int[] right = new int[a.length - mid];System.arraycopy(a, 0, left, 0, left.length);System.arraycopy(a, mid, right, 0, right.length);mergeSort(left);mergeSort(right);> merge(a, left, right);>}>> while(leftPos left.length && rightPos right.length)private static void merge(int[] dst, int[] left, int[] right)> int dstPos = 0, leftPos = 0, rightPos = 0;{> if(left[leftPos] right[rightPos])> {> dst[dstPos++] = left[leftPos++];> }else{> dst[dstPos++] = right[rightPos++];> }> }while(leftPos left.length){> dst[dstPos++] = left[leftPos++];> }> while(rightPos right.length) > {dst[dstPos++] = right[rightPos++];}}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static void insertionSort(int[] a)for(int i = 1; i a.length; ++i){> for(int j = i; j 0; --j)> {> if(a[j] a[j - 1]) > {> swap(a, j, j - 1);> }> }}}int[] data = {5, 1, 4, 9, 6, 2, 7, 3, 8};bubbleSort(data);boolean check = Arrays.equals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}, data);> if(!check){return false;> }> data = new int[]{5, 1, 4, 9, 6, 2, 7, 3, 8};> quickSort(data);> check = Arrays.equals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}, data);> if(!check)> {> return false;> }data = new int[]{5, 1, 4, 9, 6, 2, 7, 3, 8};mergeSort(data);check = Arrays.equals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}, data);if(!check){> return false;> }> data = new int[]{5, 1, 4, 9, 6, 2, 7, 3, 8};pre data-role="codeBlock" data-info="js" class="language-javascript"> insertionSort(data);> check = Arrays.equals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}, data);> if(!check)> {> return false;> }return true;}