MHB Intermediate Steps in Insertion Sort Algorithm

[Joystar77]

Sort with Insertion Sort Algorithms the following list:

329, 364, 373, 334, 320

Give the intermediate lists at each step.

Can somebody please tell me if this is correct for Insertion Sort Algorithms?

329, 364, 373, 334, 320

1. 329, 364, 373, 334, 320

2. 364, 329, 373, 334, 320

3. 329, 373, 364, 334, 320

If this is not correct, can somebody please explain in simpler terms other than saying "2nd number goes before 1st number in array, 3rd number goes imbetween 1st and 2nd number in array." I have a learning disability which is Epilepsy Seizures so its really hard for me to understand when saying something like this. Is there a way to say it in simpler terms?

 

[MarkFL]

We begin with the array:

329, 364, 373, 334, 320

It is my understanding of this algorithm that we begin with the second element, and compare it to the first. If it is less than the first, we swap them. In our case we have $329< 364$, so nothing is moved:

1.) 329, 364, 373, 334, 320

For the second step, we look at the third element, and seeing that $364<373$, nothing is done:

2.) 329, 364, 373, 334, 320

For the third step, we look at the fourth element, and we see that $334<373$ and $334<364$ but $329<334$ so we move the fourth element to the second position:

3.) 329, 334, 364, 373, 320

For the fourth and final step, we look at the fifth element and see that $320<373$, $320<364$, $320<334$, and $320<329$, so we move the fifth element to the first position:

4.) 320, 329, 334, 364, 373

Now the list is sorted.

 

[Evgeny.Makarov]

Even though Wikipedia says that "the common practice is to implement [insertion sort] in-place" (i.e., operating on one array), sometimes the algorithm is presented as operating on two lists: it removes head elements of the first list and inserts them into the correct position in the second list. Thus, the second list is always sorted. In this case, the two lists at each step are as follows.

Step  First list                Second list
 1    329, 364, 373, 334, 320   empty
 2    364, 373, 334, 320        329
 3    373, 334, 320             329, 364
 4    334, 320                  329, 364, 373
 5    320                       329, 334, 364, 373
 6    empty                     320, 329, 334, 364, 373

The OP should sheck which version of insertion sort is used in his/her sourses and provide more details if necessary.

 

[Joystar77]

Where did you give the intermediate lists at each step? Is it correct then in more simpler terms that in Insertion Sort your comparing the array to what is greater than or less than? Afterwards, then I compare the array and if it's less than/greater than the first array, then I swap them.

We begin with the array:

329, 364, 373, 334, 320

It is my understanding of this algorithm that we begin with the second element, and compare it to the first. If it is less than the first, we swap them. In our case we have $329< 364$, so nothing is moved:

1.) 329, 364, 373, 334, 320

For the second step, we look at the third element, and seeing that $364<373$, nothing is done:

2.) 329, 364, 373, 334, 320

For the third step, we look at the fourth element, and we see that $334<373$ and $334<364$ but $329<334$ so we move the fourth element to the second position:

3.) 329, 334, 364, 373, 320

For the fourth and final step, we look at the fifth element and see that $320<373$, $320<364$, $320<334$, and $320<329$, so we move the fifth element to the first position:

4.) 320, 329, 334, 364, 373

Now the list is sorted.

- - - Updated - - -

Where did you give the intermediate lists at each step? Is it correct then for me to understand this better that in Insertion Sort that if I am comparing the array and it's less than or greater than then I would swap the numbers?

Even though Wikipedia says that "the common practice is to implement [insertion sort] in-place" (i.e., operating on one array), sometimes the algorithm is presented as operating on two lists: it removes head elements of the first list and inserts them into the correct position in the second list. Thus, the second list is always sorted. In this case, the two lists at each step are as follows.

Step  First list                Second list
 1    329, 364, 373, 334, 320   empty
 2    364, 373, 334, 320        329
 3    373, 334, 320             329, 364
 4    334, 320                  329, 364, 373
 5    320                       329, 334, 364, 373
 6    empty                     320, 329, 334, 364, 373

The OP should sheck which version of insertion sort is used in his/her sourses and provide more details if necessary.

 

[Evgeny.Makarov]

I assume that after the line that says "Updated" in post #4 you are asking me and not Mark because that part contains my quote.

Where did you give the intermediate lists at each step?

In the table, which follows the word "Code:" in post #3.

Is it correct then for me to understand this better that in Insertion Sort that if I am comparing the array and it's less than or greater than then I would swap the numbers?

One cannot compare an array because it consists of many numbers. One can compare a single number to another number. You also did not say which array (or list) you are talking about because my algorithm works with two lists. Finally, you did not say to what you compare the array and which numbers you swap. For these reasons, I am having difficulties understanding your question.

Edit: Perhaps you are asking Mark after all.

 

[MarkFL]

Where did you give the intermediate lists at each step? Is it correct then in more simpler terms that in Insertion Sort your comparing the array to what is greater than or less than? Afterwards, then I compare the array and if it's less than/greater than the first array, then I swap them...

The numbered lines in my post are the intermediate steps.

I used Wikipedia's description of the algorithm:

Insertion sort - Wikipedia, the free encyclopedia

 

[Joystar77]

Thank you MarkFL!

- - - Updated - - -

Thank you Evgeny.Makarov!