Instantly share code, notes, and snippets.

Embed
What would you like to do?
Using Binary Search to Sort Array
package chapter7;
import java.util.Arrays;
public class UniqueSorted {
private static int[]generateJunk(int count) {
int values[] = new int[count];
for (int i = 0; i < values.length; i++) {
values[i] = (int) (Math.random() * 100) + 1;
}
return values;
}
private static void print(int x[], int columnsize, int numPerLine) {
for (int i = 0; i < x.length; i++) {
System.out.printf("%" + columnsize + "d", x[i]);
if ((i + 1) % numPerLine == 0 || (i + 1) == x.length)
System.out.println();
}
}
private static void insertElement(int[] temp, int count, int index, int value) {
for (int i = count - 1; i >= index; i--) {
temp[i + 1] = temp[i];
}
temp[index] = value;
}
private static int []uniqueSort(int x[]) {
int temp[] = new int[x.length];
int count = 0; // No elements in temp
// Prime temp with one element
temp[count++] = x[0];
for (int i = 1; i < x.length; i++) {
int index = Arrays.binarySearch(temp, 0, count, x[i]);
if (index < 0) {
// Not in temp, insert it!
index = -index - 1;
insertElement(temp, count, index, x[i]);
count++;
}
}
return Arrays.copyOf(temp, count);
}
private static int []sort(int x[]) {
int temp[] = new int[x.length];
int count = 0; // No elements in temp
// Prime temp with one element
temp[count++] = x[0];
for (int i = 1; i < x.length; i++) {
int index = Arrays.binarySearch(temp, 0, count, x[i]);
index = index < 0 ? -index - 1 : index;
insertElement(temp, count, index, x[i]);
count++;
}
return temp;
}
public static void main(String[] args) {
int values[] = generateJunk(100);
System.out.println("Random Junk!");
print(values, 5, 10);
System.out.println();
System.out.println("Sorted Junk!");
int duplicate[] = values.clone();
duplicate = sort(duplicate);
print(duplicate, 5, 10);
System.out.println();
System.out.println("Now Sorted With No Dups");
duplicate = values.clone();
duplicate = uniqueSort(values);
print(duplicate, 5, 10);
System.out.println();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment