CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    Join Date
    Jun 2014
    Posts
    2

    Swap algorithm for arrays O(N)

    Hello everybody!

    I would like to ask some help regarding one swap algorithm I am doing. The algorithm need to swap all elements of the array with every possible combination of the elements of it. I am stuck trying to get the best possible time complexity for this algorithm, but I cannot do better than O(N raised to 2). I am running out of ideas. The algorithm I have is the following:

    Code:
    import java.math.*;
    
    
    class SwapAlgo {
        public int main(int[] A) {
            int l=0,k=0;
            
    
    
                //Swap algorithm
                for (l=0 ; l < A.length ; l++){
                    for (k = l+1 ; k < A.length ; k++){
    
    
                        int [] A_aux = A;
                        int num_aux = A_aux[l];
                        A_aux [l] = A_aux[k];
                        A_aux[k]=num_aux;
                        
                 }
         }
    }
    My question is, is there any swap algorithm with better time complexity? In this case O(N).

    Thank you very much!

  2. #2
    Join Date
    Jun 2014
    Posts
    2

    Re: Swap algorithm for arrays O(N)

    I will clarify more what I am asking. What I ment about "swap all elements of the array with every possible combination of the elements of it" is, for example, having array [3,-6,2,1]

    I want to swap every element with in every possible way, that means:

    Swap element in the position 0 with element in the position 1 (3,-6)
    Swap element in the position 0 with element in the position 2 (3, 2)
    Swap element in the position 0 with element in the position 3 (3, 1)
    Swap element in the position 1 with element in the position 2 (-6, 2)
    Swap element in the position 1 with element in the position 3 (-6, 1)
    And the last swap element in the position 2 with element in the position 3 (2, 1)

    For that I need to do two loops in order to check the array (like I am doing in the program). What Im asking if there is any more optimal way in order to achieve a O(N) time complexity (mine is O(N2) because the two loops for.

    Thanks

  3. #3
    Join Date
    Jun 2011
    Posts
    12

    Re: Swap algorithm for arrays O(N)

    You are doing a swap to the right of the active array element. My understanding of the "swap all elements of the array with every possible combination of the elements of it" should give the result (given input array 012):
    012
    021
    102
    120
    201
    210

    Your algorithm gives me
    102
    201
    210

    Is that the way you intended it to work?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured