0

Assuming that you want to sort an array of positive integers not repeated, is it a good idea to sort by their value as index? For example:

Given an unsorted array like 

[5,3,4,1]

Create new array with size as max value (6) in the other array.

[null, null, null, null, null, null]

Add the elements. With the first element (5) goes to fifth position:

[null, null, null, null, null, 5]

With the second element: 

[null, null, null, 3, null, 5]

Sorting other elements...

[null, 1, null, 3, 4, 5]

Remove null values:

[1, 3, 4, 5]
Improve this question
4
  • 1
    What exactly is the question? The procedure you describe seems to be bucket sort. Commented Jun 26, 2017 at 12:06
  • Well all sorting would sort the array by their elements "value". Also, asking about "is this a good idea" is making your question either to broad or kind of subjective, both are reasons to close the question. Commented Jun 26, 2017 at 12:11
  • Pigeonhole sort Commented Jun 26, 2017 at 12:24
  • 1
    This is an O(n) sorting method. However, it is only applicable if the range of the values is relatively small. Commented Jun 26, 2017 at 12:29

3 Answers 3

Reset to default
1

It is no good idea! Sorting the two numbers [0,9223372036854775807] will exceed your memory.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Some situations where this might be non-ideal:

  • Repeated values: suppose you have two 5's, you would only end up with one. Whether you want that to happen is up to you

  • Large range: a lot of memory space can be wasted if you have a large difference between the smallest and biggest value, and not many in-between. e.g. if you only had 1 and 999 in the array, you would need a 1000-long array just to sort two values. You might not have enough memory to do this in the more general case, and constructing + filling a large array like this is time-consuming

  • Removing the null values: this kind of follows on from the previous point - each array deletion is O(n), so deleting many values can be very costly

I'm sure there are others, these are the ones I can think of.

Improve this answer

1 Comment

Removing several null values from an array is not more costly than removing one value. You just need to make one scan through the array.
0

In case if the size of integers is less then pow (10,6). But if this is exceeded then it will give you segmentation error(since pow (10,6) is maximum size of the array). So size of array is big factor. We will not use this method for large size arrays. We should generally avoid this method.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.