Order by pair comparisons: Difference between revisions

Content added Content deleted
mNo edit summary
Line 416: Line 416:
<lang java>import java.util.*;
<lang java>import java.util.*;


public class OrderByPair {
public class SortComp1 {
public static void main(String[] args) {
public static void main(String[] args) {
List<String> items = Arrays.asList("violet", "red", "green", "indigo", "blue", "yellow", "orange");
List<String> items = Arrays.asList("violet", "red", "green", "indigo", "blue", "yellow", "orange");
List<String> sortedItems = new ArrayList<>();
List<String> sortedItems = new ArrayList<>();
Comparator<String> interactiveCompare = new Comparator<String>() {

// Use a binary insertion sort to order the items. It should ask for
int count = 0;
Scanner s = new Scanner(System.in);
// close to the minimum number of questions reqired
public int compare(String s1, String s2) {
System.out.printf("(%d) Is %s <, =, or > %s. Answer -1, 0, or 1: ", ++count, s1, s2);
return s.nextInt();
}
};
for (String item : items) {
for (String item : items) {
System.out.printf("Inserting '%s' into %s\n", item, sortedItems);
System.out.printf("Inserting '%s' into %s\n", item, sortedItems);
int spotToInsert = Collections.binarySearch(sortedItems, item, interactiveCompare);
// use binary search to find the insertion spot
int spotToInsert = Collections.binarySearch(sortedItems, item, new Comparator<String>() {
int count = 0;
Scanner s = new Scanner(System.in);
public int compare(String s1, String s2) {
System.out.printf("(%d) Is %s <, =, or > %s. Answer -1, 0, or 1: ", ++count, s1, s2);
return s.nextInt();
}
});
// when item does not equal an element in sortedItems,
// when item does not equal an element in sortedItems,
// it returns bitwise complement of insertion point
// it returns bitwise complement of insertion point
Line 448: Line 445:
(1) Is violet <, =, or > red. Answer -1, 0, or 1: 1
(1) Is violet <, =, or > red. Answer -1, 0, or 1: 1
Inserting 'green' into [red, violet]
Inserting 'green' into [red, violet]
(1) Is red <, =, or > green. Answer -1, 0, or 1: -1
(2) Is red <, =, or > green. Answer -1, 0, or 1: -1
(2) Is violet <, =, or > green. Answer -1, 0, or 1: 1
(3) Is violet <, =, or > green. Answer -1, 0, or 1: 1
Inserting 'indigo' into [red, green, violet]
Inserting 'indigo' into [red, green, violet]
(1) Is green <, =, or > indigo. Answer -1, 0, or 1: -1
(4) Is green <, =, or > indigo. Answer -1, 0, or 1: -1
(2) Is violet <, =, or > indigo. Answer -1, 0, or 1: 1
(5) Is violet <, =, or > indigo. Answer -1, 0, or 1: 1
Inserting 'blue' into [red, green, indigo, violet]
Inserting 'blue' into [red, green, indigo, violet]
(1) Is green <, =, or > blue. Answer -1, 0, or 1: -1
(6) Is green <, =, or > blue. Answer -1, 0, or 1: -1
(2) Is indigo <, =, or > blue. Answer -1, 0, or 1: 1
(7) Is indigo <, =, or > blue. Answer -1, 0, or 1: 1
Inserting 'yellow' into [red, green, blue, indigo, violet]
Inserting 'yellow' into [red, green, blue, indigo, violet]
(1) Is blue <, =, or > yellow. Answer -1, 0, or 1: 1
(8) Is blue <, =, or > yellow. Answer -1, 0, or 1: 1
(2) Is red <, =, or > yellow. Answer -1, 0, or 1: -1
(9) Is red <, =, or > yellow. Answer -1, 0, or 1: -1
(3) Is green <, =, or > yellow. Answer -1, 0, or 1: 1
(10) Is green <, =, or > yellow. Answer -1, 0, or 1: 1
Inserting 'orange' into [red, yellow, green, blue, indigo, violet]
Inserting 'orange' into [red, yellow, green, blue, indigo, violet]
(1) Is green <, =, or > orange. Answer -1, 0, or 1: 1
(11) Is green <, =, or > orange. Answer -1, 0, or 1: 1
(2) Is red <, =, or > orange. Answer -1, 0, or 1: -1
(12) Is red <, =, or > orange. Answer -1, 0, or 1: -1
(3) Is yellow <, =, or > orange. Answer -1, 0, or 1: 1
(13) Is yellow <, =, or > orange. Answer -1, 0, or 1: 1
[red, orange, yellow, green, blue, indigo, violet]
[red, orange, yellow, green, blue, indigo, violet]
</pre>
</pre>