Custom sorting algorithm
Base on given array of characters design your own sorting algorithm to sort array of string.
There will be two inputs as per below.
Input :
char a[] = { ‘z’, ‘q’, ‘a’, ‘s’, ‘d’, ‘y’, ‘c’ };
String s[] = { “zasd”, “qazyc”, “yczaq”, “caq”, “czq”, “dzaq”, “czqa”, “zzsd” };
Output: It will be sorted string array
String s[] = { “zzsd”, “zasd”, “qazyc”, “dzaq”, “yczaq”, “czq”, “czqa”, “caq” };
Algorithm :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
package com.omt.learn.algo; public class CustomSortingAlgo { public static void main(String[] args) { char a[] = { 'z', 'q', 'a', 's', 'd', 'y', 'c' }; String s[] = { "zasd", "qazyc", "yczaq", "caq", "czq", "dzaq", "czqa", "zzsd" }; s = sortedStringArray(a, s); for (String string : s) { System.out.println(string); } } public static String[] sortedStringArray(char a[], String s[]) { return sortedStringArray(a, s, 0, s.length - 1); } public static String[] sortedStringArray(char a[], String s[], int start, int end) { int i = start; int j = end; String pivote = s[(start + end) / 2]; // You can also use start+(end-start)/2 to avoid overflow. while (i <= j) { while (compareTo(a, s[i], pivote) < 0) { i++; } while (compareTo(a, s[j], pivote) > 0) { j--; } if (i <= j) { String temp = s[i]; s[i] = s[j]; s[j] = temp; i++; j--; } } if (i < end) { sortedStringArray(a, s, i, end); } if (j > start) { sortedStringArray(a, s, start, j); } return s; } public static int compareTo(char a[], String first, String second) { int min = Math.min(first.length(), second.length()); int index = 0; while (min > 0) { if (first.charAt(index) != second.charAt(index)) { return getIndex(a, first.charAt(index)) - getIndex(a, second.charAt(index)); } index++; min--; } return first.length() - second.length(); } public static int getIndex(char a[], char c) { for (int i = 0; i < a.length; i++) { if (a[i] == c) { return i; } } return -1; } } |