Sorting array of 1000 distinct integers in the range [1, 5000], accessing each element at most once [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 12 years ago.

Suppose you have an array of 1000 integers. The integers are in random order, but you know each of the integers is between 1 and 5000 (inclusive). In addition, each number appears only once in the array. Assume that you can access each element of the array only once. Describe an algorithm to sort it.

Ho开发者_如何学运维w i can sorting?

If you used auxiliary storage in your algorithm, can you find an algorithm that remains O(n) space complexity?

---

        int[] firstarray = ....; // input array
        bool[] counterList = new bool[5000];

        for (int i = 0; i < 1000; i++)
        {
            counterList[firstarray[i]] = true;
        }

        int nCount = 0;
        for (int i = 0; i < 5000; i++)
        {
            if (counterList[i])
                firstarray[nCount++] = i;
        }

---

You could do a count sort, which will be O(5000) time and space complexity, which is pretty much O(N). This is a fairly good match for your ratio of 1000 numbers : range of 5000. Hopefully this meets your requirement of reading each number only once, even though it kind of "stores" them in the buckets.

If you want to save some memory, and likely some time (at most a constant factor of 5), then you can use larger buckets. Take a look at bucket sort.