Блог пользователя LongQuan

Sort any array in time O(n) ???
Автор LongQuan, история, 8 лет назад, По-английски

I try sort any number array with complexity O(n). I have adjusted Counting sort. 1. I divide input into 2 case: negative array case and positive array case 2. I sort and combine 2 array in 2 case 3. get output

=> complexity O(n)

- GIVE ME YOUR BUG?

code here: my Code

  • Проголосовать: нравится
  • -34
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

I used really amazing and awesome randomized input generator and I think your code doesn't work for this input.

1
1000000000
→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank kalimm, your bug is correct! Your bug is not working because memory is limited. I am not able to store array with size greater than 10000000. As result, In my code with array C[] (temporary storage) not work when maximum element of array K > 10000000 and going on... :( ex in my code: for (int i = 0; i <= K; i ++) // K is maximum element of array C[i] = 0; But omit this error, are u think my idea is correct and complexity is O(n)?

    → Ответить