Order by pair comparisons: Difference between revisions
Content added Content deleted
(added go) |
(added java) |
||
Line 410: | Line 410: | ||
(11) Is violet < indigo? n |
(11) Is violet < indigo? n |
||
[red orange yellow green blue indigo violet] |
[red orange yellow green blue indigo violet] |
||
</pre> |
|||
=={{header|Java}}== |
|||
===Java: Binary search insertion sort=== |
|||
<lang java>import java.util.*; |
|||
public class OrderByPair { |
|||
public static void main(String[] args) { |
|||
List<String> items = Arrays.asList("violet", "red", "green", "indigo", "blue", "yellow", "orange"); |
|||
List<String> sortedItems = new ArrayList<>(); |
|||
// Use a binary insertion sort to order the items. It should ask for |
|||
// close to the minimum number of questions reqired |
|||
for (String item : items) { |
|||
System.out.printf("Inserting '%s' into %s\n", item, sortedItems); |
|||
// 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, |
|||
// it returns bitwise complement of insertion point |
|||
if (spotToInsert < 0) spotToInsert = ~spotToInsert; |
|||
sortedItems.add(spotToInsert, item); |
|||
} |
|||
System.out.println(sortedItems); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Inserting 'violet' into [] |
|||
Inserting 'red' into [violet] |
|||
(1) Is violet <, =, or > red. Answer -1, 0, or 1: 1 |
|||
Inserting 'green' into [red, violet] |
|||
(1) Is red <, =, or > green. Answer -1, 0, or 1: -1 |
|||
(2) Is violet <, =, or > green. Answer -1, 0, or 1: 1 |
|||
Inserting 'indigo' into [red, green, violet] |
|||
(1) Is green <, =, or > indigo. Answer -1, 0, or 1: -1 |
|||
(2) Is violet <, =, or > indigo. Answer -1, 0, or 1: 1 |
|||
Inserting 'blue' into [red, green, indigo, violet] |
|||
(1) Is green <, =, or > blue. Answer -1, 0, or 1: -1 |
|||
(2) Is indigo <, =, or > blue. Answer -1, 0, or 1: 1 |
|||
Inserting 'yellow' into [red, green, blue, indigo, violet] |
|||
(1) Is blue <, =, or > yellow. Answer -1, 0, or 1: 1 |
|||
(2) Is red <, =, or > yellow. Answer -1, 0, or 1: -1 |
|||
(3) Is green <, =, or > yellow. Answer -1, 0, or 1: 1 |
|||
Inserting 'orange' into [red, yellow, green, blue, indigo, violet] |
|||
(1) Is green <, =, or > orange. Answer -1, 0, or 1: 1 |
|||
(2) Is red <, =, or > orange. Answer -1, 0, or 1: -1 |
|||
(3) Is yellow <, =, or > orange. Answer -1, 0, or 1: 1 |
|||
[red, orange, yellow, green, blue, indigo, violet] |
|||
</pre> |
|||
===Java: Standard sort with custom comparator=== |
|||
<lang java>import java.util.*; |
|||
public class OrderByPair { |
|||
public static void main(String[] args) { |
|||
List<String> items = Arrays.asList("violet", "red", "green", "indigo", "blue", "yellow", "orange"); |
|||
Collections.sort(items, 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(); |
|||
} |
|||
}); |
|||
System.out.println(items); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
(1) Is red <, =, or > violet. Answer -1, 0, or 1: -1 |
|||
(2) Is green <, =, or > red. Answer -1, 0, or 1: 1 |
|||
(3) Is green <, =, or > violet. Answer -1, 0, or 1: -1 |
|||
(4) Is green <, =, or > red. Answer -1, 0, or 1: 1 |
|||
(5) Is indigo <, =, or > green. Answer -1, 0, or 1: 1 |
|||
(6) Is indigo <, =, or > violet. Answer -1, 0, or 1: -1 |
|||
(7) Is blue <, =, or > indigo. Answer -1, 0, or 1: -1 |
|||
(8) Is blue <, =, or > green. Answer -1, 0, or 1: 1 |
|||
(9) Is yellow <, =, or > blue. Answer -1, 0, or 1: -1 |
|||
(10) Is yellow <, =, or > green. Answer -1, 0, or 1: -1 |
|||
(11) Is yellow <, =, or > red. Answer -1, 0, or 1: 1 |
|||
(12) Is orange <, =, or > blue. Answer -1, 0, or 1: -1 |
|||
(13) Is orange <, =, or > yellow. Answer -1, 0, or 1: 1 |
|||
(14) Is orange <, =, or > green. Answer -1, 0, or 1: 1 |
|||
[red, yellow, green, orange, blue, indigo, violet] |
|||
</pre> |
</pre> |
||