Welcome to our community

Be a part of something great, join today!

Insertion Sort Algorithms

Joystar1977

Active member
Jul 24, 2013
119
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

Administrator
Staff member
Feb 24, 2012
13,775
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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.

Code:
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.
 

Joystar1977

Active member
Jul 24, 2013
119
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.

Code:
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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

Administrator
Staff member
Feb 24, 2012
13,775
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
 

Joystar1977

Active member
Jul 24, 2013
119
Thank you MarkFL!

- - - Updated - - -

Thank you Evgeny.Makarov!