CODEWITHSUNDEEP
algorithmlist
Samad Lotia
Samad Lotia

Reputation: 733

How to sort a disjoint sublist?

Let's say I have the following list: [2, 1, 4, 6, 3, 7]. I also have some method that sorts any list. However, I want to perform a sort across only elements at indices 1, 2, & 4, i.e. the sublist [1, 4, 3]. Sorting across this sublist produces [1, 3, 4]. How can get the original list such that I only sort across indices 1, 2, and 4, i.e., [2, 1, 3, 6, 4, 7]?

Upvotes: 1

Views: 395

Answers (3)

Paddy3118
Paddy3118

Reputation: 4772

The following Python code does the job. It may differ from Jerry Coffins accepted answer as rather than sorting through indirection it extracts the values, sorts, then inserts them back.

data    = [7, 6, 5, 4, 3, 2, 1, 0]
indices = sorted([1,2,4])
values  = [data[i] for i in indices] # [6, 5, 3]
values.sort()                        # [3, 5, 6]
for index, value in zip(indices, values):
    data[index] = value
print (data)                         # [7, 3, 5, 4, 6, 2, 1, 0]
  1. The original indices should be sorted for things to work.

  2. The corresponding values are extracted.

  3. The values are sorted.

  4. The for loop puts the sorted values back into the original array.

Upvotes: 0

Samad Lotia
Samad Lotia

Reputation: 733

Thanks to the suggestion by Jerry Coffin, here's the solution in Java for those who are interested:

import java.util.List;
import java.util.AbstractList;
import java.util.Arrays;

public class ExtendedSubList<E> extends AbstractList<E>
{
    protected final List<E> parent;
    protected final int[] indices;

    public static <E> List<E> subList(final List<E> parent, int ... indices)
    {
        if (parent == null)
            throw new IllegalArgumentException("parent == null");
        if (indices == null)
            throw new IllegalArgumentException("indices == null");
        for (int i = 0; i < indices.length; i++)
            if (!(0 <= indices[i] && indices[i] < parent.size()))
                throw new IllegalArgumentException(String.format("index %d (at position %d) is not in bounds", indices[i], i));
        Arrays.sort(indices);
        return new ExtendedSubList(parent, indices);
    }

    protected ExtendedSubList(List<E> parent, int[] indices)
    {
        this.parent = parent;
        this.indices = indices;
    }

    public E get(int index)
    {
        return parent.get(indices[index]);
    }
    public int size()
    {
        return indices.length;
    }

    public E set(int index, E element)
    {
        return parent.set(indices[index], element);
    }
}

Usage example:

List<Integer> list = Arrays.asList(2, 1, 4, 6, 3, 7);
Collections.sort(ExtendedSubList.subList(list), 1, 2, 4);

The resulting list would produce: [2, 1, 3, 6, 4, 7].

Upvotes: 0

Jerry Coffin
Jerry Coffin

Reputation: 490663

The easiest way is probably to use an extra level of indirection. For example, create a list (here meaning just some linear collection, not necessarily a linked list) of the indexes of the three elements you want to sort, and code to do comparison/swapping through that layer of indirection.

Upvotes: 2

Related Questions