2

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.

Rev Tyler
  • 601
  • 7
  • 17
  • I do not know the name, but looks interesting, nevertheless. 1+ – Eugene Jun 15 '21 at 01:53
  • 1
    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](https://stackoverflow.com/a/3350656/10986894) – Rebel Rae Jun 15 '21 at 02:03
  • 2
    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 Jun 15 '21 at 02: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 Jun 15 '21 at 06:02

2 Answers2

1

Nothing exists, but the algorithm is simple enough:

  1. separate dupes into tmplist
  2. sort list
  3. add list to result
  4. switch list and tmplist
  5. repeat while list is non-empty
Bohemian
  • 412,405
  • 93
  • 575
  • 722
  • This is pretty much what I was thinking. It seemed pretty brute force, but that's what I ended up doing. – Rev Tyler Jun 15 '21 at 06:01
  • "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"? – Bohemian Jun 15 '21 at 06:09
1

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.

Quicksilver
  • 136
  • 8