Home > Software engineering >  Sort list into multiple lists based on its values
Sort list into multiple lists based on its values

Time:11-28

I have a list and I need to sort it in ascending/descending based on its sequence. For e.g. I start with the first index and create a sublist until values are in either ascending/descending order. If the order changed then start creating a new sublist.

Input

List<Integer> = [1,2,3,4,8,7,5,6]

Output

List<List<Integer>> = [[1,2,3,4,8], [8,7,5], [5,6]]

Input

List<Integer> = [8,7,8,9]

Output

List<List<Integer>> = [[8,7], [7,8,9]]

Input

List<Integer> = [1,2,2,1]

Output

List<List<Integer>> = [[1,2], [2,2], [2,1]]

CodePudding user response:

Here's something that may help. Explanations have been added as comments at important places.

The crucial component is the simple enum Direction. I have assumed "equals" also apart from "ascending" and "descending". If that is not required, then include the equals check in Direction.ASC or Direction.DESC depending upon your choice.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.BiPredicate;

public class SortedSubLists{
    public static void main( String[] args ){
        List<List<Integer>> testData = Arrays.asList( 
            Arrays.asList( 1,2,3,4,8,7,5,6 ),
            Arrays.asList( 8,7,8,9 ),
            Arrays.asList( 1,2,2,1 )
        );
        
        for( List<Integer> input : testData ) {
            List<List<Integer>> subLists = split( input );
            
            System.out.println( "\r\nInput: "   input );
            for( List<Integer> l : subLists ) System.out.println( l );
        }
    }

    /** Represents the direction of the movement of data */
    private static enum Direction {
        ASC(( prev, curr ) -> prev - curr < 0), DESC(( prev, curr ) -> prev - curr > 0), EQ(( prev, curr ) -> prev - curr == 0);

        private Direction( BiPredicate<Integer, Integer> applicability ){
            this.applicability = applicability;
        }

        private BiPredicate<Integer, Integer> applicability;

        static Direction get( Integer prev, Integer curr ){
            for( Direction d : values() ){
                if( d.applicability.test( prev, curr ) ) return d;
            }

            return null;
        }
    }

    private static List<List<Integer>> split( List<Integer> list ){
        Direction dir = null;
        List<List<Integer>> result = new ArrayList<>();

        Integer prev = null;
        List<Integer> currList = null;
        for( Integer i : list ){
            /* For the first element in the input, create a sub-list here and add the first element. */
            if( prev == null ) {
                currList = newList( result );
                currList.add( i );
            }
            else{
                /* Find the direction. If it has changed, create a new sub-list. Otherwise, continue with the
                 * existing one. */
                Direction newDir = Direction.get( prev, i );
                if( dir == null ) dir = newDir;
                else{
                    if( dir != newDir ) {
                        dir = newDir;
                        currList = newList( result );
                        currList.add( prev );
                    }
                }

                currList.add( i );
            }
            
            prev = i;

        }
        return result;
    }

    private static List<Integer> newList( List<List<Integer>> result ){
        List<Integer> newList = new ArrayList<>();
        result.add( newList );
        return newList;
    }
}

Output from running the program

Input: [1, 2, 3, 4, 8, 7, 5, 6]
[1, 2, 3, 4, 8]
[8, 7, 5]
[5, 6]

Input: [8, 7, 8, 9]
[8, 7]
[7, 8, 9]

Input: [1, 2, 2, 1]
[1, 2]
[2, 2]
[2, 1]

CodePudding user response:

Try this.

static <T extends Comparable<T>> List<List<T>> sortedSubList(List<T> list) {
    int size = list.size();
    List<List<T>> result = new ArrayList<>();
    int start = 0;
    if (size >= 2) {
        int prev = list.get(0).compareTo(list.get(1));
        for (int i = 1, max = size - 1; i < max;   i) {
            int next = list.get(i).compareTo(list.get(i   1));
            if (prev != next) {
                result.add(list.subList(start, i   1));
                start = i;
            }
            prev = next;
        }
    }
    result.add(list.subList(start, size));
    return result;
}

and

static <T extends Comparable<T>> void test(List<T> list) {
    System.out.println(list   " -> "   sortedSubList(list));
}

public static void main(String[] args) throws IOException {
    test(List.of(1, 2, 3, 4, 8, 7, 5, 6));
    test(List.of(8, 7, 8, 9));
    test(List.of(1, 2, 2, 1));
    test(List.of(1, 2));
    test(List.of(1));
    test(List.of());
    test(List.of("a", "b", "b", "a"));
}

output:

[1, 2, 3, 4, 8, 7, 5, 6] -> [[1, 2, 3, 4, 8], [8, 7, 5], [5, 6]]
[8, 7, 8, 9] -> [[8, 7], [7, 8, 9]]
[1, 2, 2, 1] -> [[1, 2], [2, 2], [2, 1]]
[1, 2] -> [[1, 2]]
[1] -> [[1]]
[] -> [[]]
[a, b, b, a] -> [[a, b], [b, b], [b, a]]
  •  Tags:  
  • java
  • Related