CODEWITHSUNDEEP
javaalgorithmsorting
Rev Tyler
Rev Tyler

Reputation: 603

Numerical sort with multiple lists of ascending values

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.

Upvotes: 2

Views: 65

Answers (2)

Quicksilver
Quicksilver

Reputation: 164

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.

Upvotes: 1

Bohemian
Bohemian

Reputation: 425198

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

Upvotes: 1

Related Questions