2 way insertion sort, sorts but not as efficient as expected

The two-way insertion sort is a bi-directional insertion sort that sorts the array from the center out towards the ends.  My sort works but it is very inefficient.  We are tracking the amount of data moves as well as the amount of comparisons.

Expected approximate results
2-way insertion     4176550     4177731          72

my results (about 5x bigger)
2-way insertion         22862384    29116084             1531


The two-way insertion sort algorithm is:

do
    if (A[left] > A[right])
        swap A[left] and A[right]

    starting with with A[right] and moving to the left, use insertion sort
    algorithm to insert the element at A[right] into the correct location
    between A[left+1] and A[right-1]

    starting with A[left] and moving to the right, use the insertion sort
    algorithm to insert the element at A[left] into the correct location
    between A[left+1] and A[right-1]

    left--, right++
until left has gone off the left edge of A and right has gone off the right
      edge of A

Any ideas?

JOe K.
/*The two-way selection sort is a bi-directional insertion sort that 
 * sorts the array from the center out towards the ends.  The 
 * two-way insertion sort algorithm is:
 * 
 * do
 * 
    if (A[left] > A[right])
        swap A[left] and A[right]

    starting with with A[right] and moving to the left, use insertion sort 
    algorithm to insert the element at A[right] into the correct location 
    between A[left+1] and A[right-1]

    starting with A[left] and moving to the right, use the insertion sort 
    algorithm to insert the element at A[left] into the correct location 
    between A[left+1] and A[right-1]

    left--, right++
until left has gone off the left edge of A and right has gone off the right 
      edge of A
 */		
	public static <E extends Comparable<E>> void twoWayInsertSort(E[] A) { 
		if (A.length%2!=0){
			throw new IllegalArgumentException();
		}
		int left = A.length/2-1;
 		int right = A.length/2+1;
 		int N = A.length/2;
 		int j = 0;
 		E tmpLeft, tmpRight;
 		//until left has gone off the left edge of A and right has gone off the right 
 	    //edge of A
		
			
		//starting with with A[right] and moving to the left, use insertion sort 
		//algorithm to insert the element at A[right] into the correct location 
		//between A[left+1] and A[right-1]
		for (int i = 1; i < N; i++){
			for (int r = right; r > left; r--){
				if(A[left].compareTo(A[right]) > 0){
					swap(A, left, right);
				}
				
				dataMove++;
				tmpRight = A[r];
				j = r - 1;
				while ((j >= left) && (A[j].compareTo(tmpRight) > 0)) {
					dataMove++;
					A[j+1] = A[j]; // move one value over one place to the right
					j--;
				}
				dataMove++;
				A[j+1] = tmpRight;    // insert kth value in correct place relative
			}
			
			for (int l = left; l < right; l++){
				dataMove++;
				tmpLeft = A[l];
				j = l + 1;
				while ((j <= right) && (A[j].compareTo(tmpLeft) < 0)) {
					dataMove++;
					A[j-1] = A[j]; // move one value over one place to the right
					j++;
				}
				dataMove++;
				A[j-1] = tmpLeft;    // insert kth value in correct place relative
				
			}
			left--;
			right++;
		}						
	}

Open in new window

ClaudeWalkerAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

SuperdaveCommented:
This is an O(n^3) algorithm, very inefficient.  That is, your while loops are nested inside two for loops, so they are getting executed a lot, and (correctly) counting up
dataMove each time.  You really need some kind of tree structure to do this sort of thing efficiently; inserting by sliding elements up means your doing an awful lot of moving.
0
ClaudeWalkerAuthor Commented:
I have the original down pat which less efficient in it's compares but more efficient in it's data moves.

I just have no idea on how to increment these rights and lefts without that outer loop.
public static <E extends Comparable<E>> void insertionSort(E[] A) {
		int k, j;
		E tmp;
		int N = A.length;

		for (k = 1; k < N; k++) {
			dataMove++;
			tmp = A[k];
			j = k - 1;
			while ((j >= 0) && (A[j].compareTo(tmp) > 0)) {
				dataMove++;
				A[j+1] = A[j]; // move one value over one place to the right
				j--;
			}
			dataMove++;
			A[j+1] = tmp;    // insert kth value in correct place relative 
			// to previous values
		}
	}

Open in new window

0
Dave BaldwinFixer of ProblemsCommented:
When I had to do this, I made an index of the elements.  I swapped the index elements and never moved the data elements themselves.  It's a lot less moving.  When you're done, write out the data elements in index order.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
SuperdaveCommented:
If the index elements were a linked list, so you could insert by changing a couple pointers (constant time instead of O(n)), then it would be much faster.  Doing the final exchanging using the index would be doable but tricky to make sure it's not too slow in itself.
Also, although it would be a lot of work, the while loop on line 10 that's doing the comparisons could be replaced with a binary search (since you're searching the sorted part) and that would lower the time-complexity.
Of course this looks like an assignment to me, and I don't have a good guess as to what they're actually expecting from you.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.