Does this mean you can sort (positive) integer in O(n)?


  • 1
    B

    i checked the solution posted with swapping targets if target!=A[target-1]. And it claims this is done in O(n). By doing so, did he just find a new sorting algorithm for integers in O(n)?
    I never heard of this one before (not taught in algorithm classes at least). This is not the radix sort or anything i knew with integer sorting. But it works.

    To remind you what it is:

    for i in range(A):
          target=A[i]
          while target>0 and target<len(A)+1 and A[target-1]!=target:
                  new_target=A[target-1]
                  A[target-1]=target
                  target=new_target
    

    after one round, integer will be sorted because now for any i, j in A, if i>j, then i will be put after j.
    is this the best (positive) integer sorting algorithm ever or i am just stupid..
    thx.


  • 0
    C

    It can only sort array with no duplicated integers. For example

    input [1 5 3 2 2]

    your output is [1 2 3 2 5]

    More specific, it can sort the permutation of a array of continuous integers.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.