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?
 
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
 
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
 
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.