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.

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++;
}
}
```

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.

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
}
}
```

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.

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.