Insert semi-sorted into unsorted array

Question

Welcome to your first day at PPCG Inc. As our newest junior assistant document sorter, you are responsible for making sure all documents we sent down to you are archived in alphabetical order. It's so easy a monkey can do it. Well, metaphorically speaking, as we did hire a monkey to do it. Guess what? Turns out monkeys lack an understanding of our alphabet. Anyway, there's no time to fix the mess there is right now, so just try to not make the situation any worse, ok? Then get to it! If you get hungry, there's bananas over by the water cooler. Good luck!

Job Description

Input

• You will receive a list of strings (the archive) and a string that needs to be added to that list (the document)
• All strings will contain only uppercase letters, lowercase letters and spaces
• Strings will always start and end with a letter

Task

Determine the target position of the document: the position it should receive in the archive. The target position can be determined as follows:

• For each position:
  • Count the amount of strings in the archive before that position that are alphabetically before the document
  • Count the amount of strings in the archive after that position that are alphabetically after the document
  • Define the score of the position as the sum of the above two counts
• The target position of the document is the position with the highest score
• In case of a tie, all positions with the highest score are equally valid as target position. Only one needs to be selected.

When sorting:

• Uppercase and lowercase letters are equivalent
• Spaces come before letters

Output

• The archive with the document added to it in any form

OR

• The target position of the document, in either a 0-based or 1-based index

Job evaluation

Fewest bytes wins!

Example I/O

Archive:
    Applebuck Season
    Friendship is Magic
    The Ticket Master
    Griffon the BrushOff
    Boast Busters
    Bridle Gossip

Document: Dragonshy

Position scores (0-based index):
0: 0 + 3 = 3
1: 1 + 3 = 4
2: 1 + 2 = 3
3: 1 + 1 = 2
4: 1 + 0 = 1
5: 2 + 0 = 2
6: 3 + 0 = 3

Target position: 1

Answer 1

JavaScript (ES6), 81 bytes

(a,d)=>a.map((e,i)=>d[l="toLowerCase"]()<e[l]()?s--:++s>m&&(++m,p=++i),m=s=p=0)|p

Ungolfed:

function position(archive, document) {
    var score = 0;
    var max = 0;
    var pos = 0;
    var i = 0;
    while (i < archive.length) {
        if (archive[i++].toLowerCase() > document.toLowerCase()) {
            score--;
        } else {
            score++;
            if (score > max) {
                max++;
                pos = i;
            }
        }
    }
    return pos;
}

Edit: Saved a lot of bytes thanks to @user81655.

Answer 2

Pyth, 40 38 bytes

Credits to @Katenkyo for teaching me that A xnor B is basically A==B. (A xor B is also A!=B)

AQJ+],k0.e,rb0hkGteh.Msmq<hdrH0<edeZJJ

Try it online!

How it works:

It sums the XNOR of whether the entry is smaller than the document, and whether the entry's index is smaller than the document's index.

It finds the position in which this sum is the maximum, then outputs it.

Answer 3

Python 3, 135 167 Bytes

def a(b,c):a=[sum(map(lambda x:x.lower()>c.lower(),b[i:]))+sum(map(lambda x:x.lower()<c.lower(),b[:i]))for i in range(0,len(b)+1)];b.insert(a.index(max(a)),c);print(b)

Answer 4

Ruby, 97 bytes

Anonymous function, returns the target position.

->a,d{d.upcase!;(0...a.size).max_by{|i|a[0,i].count{|s|s.upcase<d}+a[i..-1].count{|s|s.upcase>d}}}

When actually inserting into the archive, 110 bytes:

->a,d{t=d.upcase;a.insert (0...a.size).max_by{|i|a[0,i].count{|s|s.upcase<d}+a[i..-1].count{|s|s.upcase>d}},d}

Answer 5

Pyth, 54 52 47 45 bytes

AQVhlG=Ys+m>rH0rd0:G0Nm<rH0rd0gGNI>YZ=ZY=kN;k

Expect input is a list, first element is a list of strings (archive), second element is a string (document)

AQ                                            # initialize G and H with the archive and the document
  VhlG                                        # iterate over the indexes on archive
      =Ys+                                    # concatenate and sum the following scores
          m>rH0rd0:G0N                        # map a string comparison between the document and the archives up to the index, returning true(1) for lower, and false(0) for higher
                      m<rH0rd0gGN             # same as above, but starts at the index and goes up to the end of the archive, returning false(0) for lower, and true(1) for higher
                                 I>YZ         # Check if score is higher than highest
                                     =ZY      # update highest score
                                        =kN;  # update index
                                            k # print index

Test here

• Saved 5 bytes on input initialization (thanks @Kenny Lau)

Answer 6

MATL, 32 bytes

hk4#S4#S%2#0)>t0whYsw~0hPYsP+K#X>

Input is a cell array of strings (several strings separated by spaces and enclosed in curly braces) for the archive, and a string for the document. Output is 1-based. In case of a tie the first position is returned.

Try it online!

Explanation

h      % Concatenate archive and document as a cell array of strings
k      % Convert all strings to lowercase
4#S    % Sort and output the indices of the sorting
4#S    % Again. This gives the indices that applied to the concatenated
       % array would make it sorted
2#0)   % Separate last index (document) from the others (archive)
>      % Is it greater? Gives zero/one array the size of the archive
t      % Duplicate that array
0wh    % Prepend a 0
Ys     % Cumulative sum. This is first part of the score
w~     % Swap. Negate zero/one array
0h     % Postpend a 0
PYsP   % Reverse, cumulative sum, reverse. Second part of the score
+      % Add. This is the score of each position
K#X>   % Arg max