# Sorting an array using shifting insertion sort.

Page 1 of 1

## 6 Replies - 262 Views - Last Post: 03 February 2018 - 12:22 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=409093&amp;s=d24eb05ca2a364ff2c7726f7718fa985&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 mdalala

Reputation: 0
• Posts: 4
• Joined: 03-February 18

# Sorting an array using shifting insertion sort.

Posted 03 February 2018 - 09:52 AM

Hello everyone... I've spent like 15 hours trying to write this method and I just can't get it done... Basically I have to do the following

1. Create a Scanner.
2. Create an array A, ask how many items there should be (user chooses it with a Scanner), and fill it up with numbers. ( with a Scanner aswell)
3. Create the array B which should be twice bigger(-1) than the array A.
4. Put the first value of the array A to the middle of the array B.
5. Copy the numbers from the array A to the array B but in a proper order. ( from the lowest value to the highest value )
6. To free space for the element A[i] in the array B one thing should be done ( depending on which of the following operations is going to require less shifting )
*all the elements that are smaller than A[i] should be shifted one position to the left
*all the elements that are larger than A[i] should be shifted one position to the right

I've run the code through a debugger several times and to me it looks like there is some problem with my else block and there is no free space being created in the array B for A[i] element. Here is my code atm: ( tried to explain it as best as I could, there probably is a lot of unnecessary things or things that don't make much sense because I've tried a lot and probably made it messy.. )

https://pastebin.com/CAFcSjaE

Here is how the method should work visually:

https://i.imgur.com/lx7uXDM.jpg

Thanks!

https://i.imgur.com/6EAtWEl.jpg

Here is how it should look like... Wrong like and I can't format my post for some reason..

Is This A Good Question/Topic? 0

## Replies To: Sorting an array using shifting insertion sort.

### #2 NormR

• D.I.C Lover

Reputation: 691
• Posts: 5,267
• Joined: 25-December 13

## Re: Sorting an array using shifting insertion sort.

Posted 03 February 2018 - 10:38 AM

Please post the code here so we can see it. Be sure to wrap the code in code tags.

### #3 mdalala

Reputation: 0
• Posts: 4
• Joined: 03-February 18

## Re: Sorting an array using shifting insertion sort.

Posted 03 February 2018 - 10:47 AM

```public class Eg {
static int[] a, b;
static int c, l, r, i, j, N;

static Scanner input = new Scanner(System.in);

public static void main(String[] args) {

}

public static void firstMethod(int[] a) {

System.out.println("The amount of elements in the array A.");
N = input.nextInt(); // N IS THE AMOUNT OF ELEMENTS IN THE ARRAY A

a = new int[N];

System.out.println("The values of the array A.");

for (i = 0; i < a.length; i++) { // FILLING THE ARRAY A WITH VALUES
a[i] = input.nextInt();
}

input.close();
System.out.println(Arrays.toString(a)); // PRINTING OUT THE ARRAY A TO CHECK

b = new int[2 * N - 1]; // CREATING TWICE BIGGER[-1] ARRAY B

l = N - 1; // ASSIGNING AS A MIDDLE ELEMENT
r = N - 1; // ASSIGNING AS A MIDDLE ELEMENT

b[r] = a[0]; // THE FIRST VALUE OF THE ARRAY B IS NOW IN THE MIDDLE OF THE ARRAY B

for (i = 1; i < N; i++) { // LOOP THROUGH THE ARRAY

if (b[l] > a[i]) { // IF THE LEFT VALUE IS BIGGER THAN a[i] THEN DECREMENT LEFT AND ASSIGN a[i] TO THE LEFT VALUE
l--;
b[l] = a[i];

} else if (b[r] < a[i]) { // IF THE LEFT VALUE IS BIGGER THAN a[i] THEN INCREMENT RIGHT AND ASSIGN a[i] TO THE RIGHT VALUE

r++;
b[r] = a[i];
} else { // ( I GUESS THE PROBLEM IS HERE)

for (j = l; j < r; j++) { // LOOP THROUGH THE ARRAY B
if (b[j] >= a[i]) { // IF THE LEFT VALUE IS BIGGER THAN a[i]

if (j - l <= r - j) { IF THERE ARE LESS ELEMENTS ON THE LEFT SIDE

for (int k = b[l]; k <= b[j - 1]; k++) { // SHIFT ALL ELEMENTS ONE POSITION TO THE LEFT
b[k - 1] = b[k];
}
l--;
b[j - 1] = a[i];
}

if (j - l >= r - j) { IF THERE ARE LESS ELEMENTS ON THE RIGHT SIDE
for (int k = b[r]; k >= b[j]; k--) { // SHIFT ALL ELEMENTS ONE POSITION TO THE RIGHT
b[k + 1] = b[k];
}
r++;
b[j] = a[i];

}
}
}

if (b[j] <= a[i]) { // NOT SURE IF THIS ONE IS EVEN NEEDED BUT BASICALLY DO THE SAME THING IF VALUE IS SMALLER THAN a[i]
if (j - l <= r - j) {

for (int k = b[l]; k <= b[j - 1]; k++) {
b[k - 1] = b[k];
}
l--;
b[j - 1] = a[i];
}

if (j - l >= r - j) {
for (int k = b[r]; k >= b[j]; k--) {
b[k + 1] = b[k];
}
r++;
b[j] = a[i];

}
}
}
}

System.out.println(Arrays.toString(B)/>); // PRINT OUT THE ARRAY B

}

```

### #4 mdalala

Reputation: 0
• Posts: 4
• Joined: 03-February 18

## Re: Sorting an array using shifting insertion sort.

Posted 03 February 2018 - 11:09 AM

Something is definitely way off... If my input is [5, 34, 22, 21, 3, 18, 15, 33] then the output I get is [0, 0, 0, 0, 0, 0, 3, 5, 34, 0, 0, 0, 0, 0, 0]

### #5 NormR

• D.I.C Lover

Reputation: 691
• Posts: 5,267
• Joined: 25-December 13

## Re: Sorting an array using shifting insertion sort.

Posted 03 February 2018 - 11:54 AM

One problem with the code is too many variable names are made of a single letter.
That makes the code very hard to read and understand.
Also searching the code for where "a" is used can find lots of occurrences of "a" that are not the variable.

Variable names should describe the contents of the variable.

A suggestion for testing: use a small number of values while debugging to make it easier to to follow the code and see what is happening.

Note: The main() method is empty. How do you execute the code for testing?
The posted code can not be executed with the java command.

This post has been edited by NormR: 03 February 2018 - 11:56 AM

### #6 mdalala

Reputation: 0
• Posts: 4
• Joined: 03-February 18

## Re: Sorting an array using shifting insertion sort.

Posted 03 February 2018 - 12:05 PM

NormR, on 03 February 2018 - 11:54 AM, said:

One problem with the code is too many variable names are made of a single letter.
That makes the code very hard to read and understand.
Also searching the code for where "a" is used can find lots of occurrences of "a" that are not the variable.

Variable names should describe the contents of the variable.

A suggestion for testing: use a small number of values while debugging to make it easier to to follow the code and see what is happening.

Note: The main() method is empty. How do you execute the code for testing?
The posted code can not be executed with the java command.

Sorry , I use
```public static void main(String[] args) {
firstMethod(B)/>;
for (int number : B)/> {
System.out.println(number);
}

}

```

### #7 NormR

• D.I.C Lover

Reputation: 691
• Posts: 5,267
• Joined: 25-December 13

## Re: Sorting an array using shifting insertion sort.

Posted 03 February 2018 - 12:22 PM

Please post the actual contents of the main() method that you use to execute and test the program.
The code in post#6 would not work.

Can you post an example of a small number of input values
and show the steps the program should take as it processes each value?

How are you debugging the code? I use print statements so the output on the console can be copied and pasted here to show what the code is doing. It's not possible to post the debugger's output.