1

I'm stuck on this problem(2 weeks). Any idea of how to approach it?.

Let L be a list of n different integer numbers, assume that the elements of x of L are in the range [1,750]. Design a linear ordering algorithm to order the elements of L

I already tried with insertion sort. But i'm not sure if my approach is right:

Construct an array of bits. Initialize them to zero.
Read the input, for each value you see set the respective bit in the array to 1.
Scan the array, for each bit set, output the respective value.

Complexity => O(2n) = O(n)

6
  • Well, what's your approach? Oct 23, 2013 at 5:45
  • @ChristianTernus He said he tried using insertion sort, fwiw. Oct 23, 2013 at 5:45
  • Yeah, but that's not the same thing as showing code or at least pseudocode. Oct 23, 2013 at 5:45
  • At wc, I don't think it's possible to sort at O(n). Oct 23, 2013 at 5:46
  • Possible duplicate of Sorting in linear time?
    – Ritwik
    Oct 19, 2015 at 14:32

5 Answers 5

8

Try Radix sort - http://en.wikipedia.org/wiki/Radix_sort

If you consider given 750 as constant, it sorts at O(n).

Comparison based sorting can't sort in less than O(nlogn), but if number of values is bounded by D, you can sort in O(D*n), or O(n) if you consider D as constant.

2
  • Sure its a theorem. Any comparison algorithm is O(n log n). Could you give me a wider explanation? Oct 23, 2013 at 5:56
  • explanation for radix or for comparison based sorting complexity?
    – Lior
    Oct 23, 2013 at 12:04
6

I won't give a full approach, but here's one observation that ought to help.

You already know that the numbers are strictly within the range [1, 750]. It's not particularly difficult to figure out how many of each number there are in linear time.

Once you have that information, how could you get back the sorted list (again, in linear time)?


As for the approach that you've given, that's not an insertion sort, it's more like a bucket sort or counting sort (which is what I was trying to hint at). The one thing I see is that your approach does not work if the array can contain duplicates. If you're given that there are none, then you're good to go. Otherwise, you'll need to modify what you have to deal with this.

1
  • 1
    Note, I would not recommend an approach similar to this if the range is particularly large. Oct 23, 2013 at 5:50
3

You can use Counting sort. Make a Hash of inputs and at each insertion just increment the value at corresponding indexes. This sorts in O(n) time with extra memory O(n).

2

Here's some code:

IntegerSort (Array A):
   Dimension Work as Array[1..750]

   Fill Work with (0)

   For i:=0 to A.Length - 1 
     Work[A[i]]++

   n = 0;
   For i:=1 to 750
      For j :=1 to Work[i] 
         A[n++] = i

As all loops are O(n) the algorithm is O(n) as well.

In an array Work which spans over the complete range of numbers and which is initialized with 0, increase each element Work[k] by one, with k=A[i] for all elements of A.

Now reconstruct the array by scanning through the Work array. Any element >0 represents one or more elements in the original array. As we are scanning from 1 to 750, we will reconstruct the sorted array.

0

As I understood you are talking about counting sort, where you see how many times your array (list in your way) contains some value and put these values into another array. Then you walk through the array and out some number as many times as it has been written this array.

You do something like this (on python as you as you originally wrote):

L = [1, 5, 2, 1, 1, 0, 1, 750, 1000] # input list

counter = [0 for i in range(0, 751)]

for value in L:
    counter[value] += 1

for i in range(751):
    for j in range(counter[i]):
        print(i, end=' ')

# Output: 0 1 1 1 1 5 750

But note that if there are values more than 750 in the input list, they won't be considered.

So this sort doesn't works for values more than some fixed value W (750 in your way) and takes time O(max(n, W)) where n is an input list's size. So this sort isn't linear for large values in input list.

Hope that you understood me with my English)

Your Answer

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

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