-
June 11th, 2014, 03:57 AM
#1
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!
-
June 12th, 2014, 04:03 AM
#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
-
June 15th, 2014, 06:17 AM
#3
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|