1
$\begingroup$

I've started with thinking of a bucket sort/radix sort variation, only to be disproved by a colleague.

Here's the problem:

Given an array with $k$ distinct elements, it is known that the smallest element appears once, the 2nd smallest element appears twice, the 3rd smallest element appears 4 times, the 4th smallest appears 8 times, and so on until the $k$-th smallest element, which appears exactly $2^{k-1}$ times.

Marking the size of the array as $n=2^k-1$, suggest an algorithm to stable sort the array in $O(n)$, provide explanation for the algorithm.

The second path of thought I had was making a new array sized $\log(n)$ with a queue in each cell, thus repeating elements keep their order.

However, the best algorithm I came of is doing this is $O(nk)=O(n\log n)$ time, which seems pretty legit to a sorting algorithm without a given range(such as in bucketsort). Yet the problem demands $O(n)$.

$\endgroup$
2
  • $\begingroup$ Bucket sort doesn't seem to be a bad idea. How are you addressing the cells in your $log(n)$-sized array of queues? Linear search? $\endgroup$
    – Bergi
    May 30, 2022 at 14:01
  • $\begingroup$ It seems you don't have k distinct elements then unless n = 1. $\endgroup$
    – gnasher729
    May 30, 2022 at 14:26

4 Answers 4

4
$\begingroup$

Copy the elements into a temporary array. As long as the temporary array isn't empty, repeat this:

  1. Find the majority value in the temporary array (e.g., using Boyer-Moore (or, as Rainer's answer reminds, simply max in our case, but I'll keep majority now)).
  2. Copy the majority elements backwards into the original array.
  3. Remove the majority elements from the temporary array.

Python implementation including test (Try it online!):

def sort(xs):
    tmp = xs[:]
    i = len(xs)
    while tmp:
        m = majority(tmp)
        for x in reversed(tmp):
            if x == m:
                i -= 1
                xs[i] = x
        tmp = [x for x in tmp if x != m]

def majority(xs):
    leader = None
    lead = 0
    for x in xs:
        if not lead:
            leader = x
            lead = 1
        elif x == leader:
            lead += 1
        else:
            lead -= 1
    return leader

from random import sample, shuffle
k = 15
xs = sorted(sample(range(1000), k))
xs = [[x] for i, x in enumerate(xs) for x in [x] * 2**i]
shuffle(xs)
expect = sorted(xs)
sort(xs)
print(xs == expect)
print(all(x is e for x, e in zip(xs, expect)))

For the curious reading the test code: I wrap each number in a list so that I get distinct (but equal-valued) objects. That allows testing the stability, which I do at the end with the identity checks using is. Note that Python's own sorted is stable, so I use that to compute the expected order.

$\endgroup$
1
$\begingroup$

Find the maximum element, then partition the array into two buckets, smaller and equals. Apply the algorithm recursively to the smaller bucket. Here is an example implementation in Python:

def quicksort(data):
    '''stable out-of-place quicksort with maximum element for pivot'''
    if not data:
        return []
    pivot = max(data)
    smaller = [x for x in data if x < pivot]
    equals = [x for x in data if x == pivot]
    return quicksort(smaller) + equals

If the majority element is not necessarily the largest one, you have to expand it into a full quicksort and use the Boyer-Moore majority algorithm to find the pivot, like this:

def quicksort(data):
    '''stable out-of-place quicksort with majority element for pivot'''
    if not data:
        return []
    pivot = majority(data)
    smaller = [x for x in data if x < pivot]
    equals = [x for x in data if x == pivot]
    greater = [x for x in data if x > pivot]
    return quicksort(smaller) + equals + quicksort(greater)

Runtime complexity is linear because half of the items fall into the equals bucket, where no recursive sort is applied. Both algorithms produce a correct and stable sort on any input, but linear runtime complexity is only guaranteed if a majority element exists and is chosen for pivot.

$\endgroup$
0
$\begingroup$

Consider a version of Mergesort that returns an array of lists. Each list in the array groups all element with the same value (and stores them in the same order as they appear in the original array).

Clearly each array has at most $k$ elements. Moreover, if we are given two sorted arrays, each of which stores $m$ elements overall in its lists, we can merge them in time $O(\min\{m,k\}) = O(\min\{m, \log n\})$.

The running time of the algorithm is therefore described by the recurrence:

$$T(m) = 2T(m/2) + O(\min\{m,\log n\}),$$ which has solution $T(n) = O(n)$.

$\endgroup$
0
$\begingroup$

The main idea is to sort it from the largest element that basically will appear $n/2$ times, the second largest will appear $n/4$ and continues on until the smallest.

For example after sorting this array $[8,3,2,8,8,8,3]$ it will look like that $[2,3,3,8,8,8,8]$ (where k=3). In order to take out the all appearances of 8 it will cost $O(n)$ (one iteration for finding who the largest is, and second to move all of his appearances to be between $n/2_{th}$ and the $n_{th}$ places).

Now we have half sorted array $[3,2,3,8,8,8,8]$ so we will need to deal with the remaining half array $[3,2,3]$ so basically we are facing now the same problem but with k=2.

Therefore we will use recursive solution:

$T(n)=T(\frac{n}{2})+O(n)$ By using the master theorem the answer is $O(n)$

For better understanding it really close to merge-sort just with sorting half array every time.

$\endgroup$
1
  • $\begingroup$ BTW The question does not require Boyer-Moore because more information is given. The largest element will be the majority element and also will appear on n / 2 places, and that continues on for the second largest until the smallest element appears once. $\endgroup$ May 31, 2022 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.