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 |
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>() { |
|||
int count = 0; |
|||
⚫ | |||
// close to the minimum number of questions reqired |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
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); |
||
⚫ | |||
// use binary search to find the insertion spot |
|||
⚫ | |||
int count = 0; |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
// 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] |
||
( |
(2) Is red <, =, 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] |
||
( |
(4) Is green <, =, 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] |
||
( |
(6) Is green <, =, 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] |
||
( |
(8) Is blue <, =, or > yellow. Answer -1, 0, or 1: 1 |
||
( |
(9) Is red <, =, 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] |
||
( |
(11) Is green <, =, or > orange. Answer -1, 0, or 1: 1 |
||
( |
(12) Is red <, =, 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> |