Numerical sort with multiple lists of ascending values

Question

I've had trouble articulating a simple way to break this question down in to a question title, and therefore a google search.

I'm wondering if there is a sorting algorithm already defined that can sort an array of numbers without keeping pairs adjacent. Easier to explain with an example:

Values:

1,3,5,2,1,3,2,4

A normal numerical sort would come out as:

1,1,2,2,3,3,4,5

What I would like:

1,2,3,4,5,1,2,3

I could hack this together, I just want to know if there is a name for this kind of sort.

I do not know the name, but looks interesting, nevertheless. 1+ — Eugene
– Eugene, Commented Jun 15, 2021 at 1:53
There are a few good solutions of varying complexities. Sort -> filter is a great go-to solution, however a hash table is provably more efficient. Answered here — Rebel Rae
– Rebel Rae, Commented Jun 15, 2021 at 2:03
What would be the rules such that there are no ambiguities? Why is 1,3,5,2,1,3,2,4 => 1,2,3,4,5,1,2,3 and not 1,2,3,5,1,2,3,4 — WJS
– WJS, Commented Jun 15, 2021 at 2:21
@wjs good question. The idea is that the first set must have all the unique numbers. Only duplicates go on to subsequent sets. — Rev Tyler
– Rev Tyler, Commented Jun 15, 2021 at 6:02

Bohemian · Accepted Answer · 2021-06-15 03:13:22Z

1

Nothing exists, but the algorithm is simple enough:

separate dupes into tmplist
sort list
add list to result
switch list and tmplist
repeat while list is non-empty

answered Jun 15, 2021 at 3:13

Bohemian♦

427k103 gold badges603 silver badges750 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rev Tyler Over a year ago

This is pretty much what I was thinking. It seemed pretty brute force, but that's what I ended up doing.

Bohemian Over a year ago

"brute force" (usually descriptive of simple impl, but poor time complexity) isn't quite the right description; if you use a Set to track dupes, de-duping would be O(n), leaving O(k log k) for the sort, so quite quick. Perhaps "agricultural"? 😀

Quicksilver · Accepted Answer · 2021-06-15 04:20:43Z

You may use the common selection sort algorithm and make some modification to it.

For example:

static void modifiedSelectionSort(int[] arr)
{
    Integer lastSelection = null;

    for (int i = 0; i < arr.length - 1; i++)
    {
        // Find the minimum element in unsorted array which is greater than lastSelection
        Integer minIdx = null;
        for (int j = i; j < arr.length; j++)
            if ((minIdx == null || arr[j] < arr[minIdx]) && (lastSelection == null || arr[j] > lastSelection))
                minIdx = j;

        // Check whether the last selection is the greatest number
        if (minIdx == null) {
            lastSelection = null;
            i--;
        } else {
            // Store the last selection
            lastSelection = arr[minIdx];

            if (minIdx != i) {
                int temp = arr[minIdx];
                arr[minIdx] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

I think there is no name for this special sorting method.

Collectives™ on Stack Overflow

Numerical sort with multiple lists of ascending values

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related