can somebody explain me the code especially the part of the while loop and the b

Question

can somebody explain me the code especially the part of the while loop and the biog O runtime and memory usage

thanks
#include <iostream>

using namespace std;

void insertion_sort (int sort[], int size)
{
int key;
int i;

for(int j =1; j < size; j++)
{
key = sort[j];

i = j-1;

while(sort[i] > key && i >=0)
{
sort [i+1] = sort[i];
i--;
}

sort[i+1] = key;
}

}
int main()
{
int sort[7] = {2,6,7,4,5,1,3};

cout << "Non sorted list" << endl;

for(int i = 0; i < 7; i++)
{
cout << sort[i] << endl;
}



insertion_sort(sort, 7);

cout<<endl<<"SORTED LIST"<<endl;

for(int i = 0; i < 7; i++)
{
cout << sort[i] << endl;
}

return 0;
}

Explanation / Answer

While loop in the code mainly accounts for the insertion

suppose u have array elements as 12 15 24 28 17 35 21 43 3

Now , 12 15 24 28 is sorted.

Next, the array is sorted till 17

i.e, 28 > 17

Therefore , 17 is inserted so that array is sorted till that part.

And the values are pushed to the right ( This is what while loop in code does)

12 15 24 28 17 35 21 43 3 ----> 12 15 17 24 28 35 21 43 3

Observe that 24 and 28 pushed to the right (i.e, sort[i+1] = sort[i])

Time complexity:

Your code has :

for(j=1;j<size;j++){

....

while(sort[i]<key && i>=0){

....

}

Therefore, time = (number of times while loop runs when j=1) + (number of times while loop runs when j=2) + (number of times while loop runs when j=3) + ........

===> time = O(number of inversions)

In worst case, T(n) = O(n^2)

where n = sixe of array.

Space complexity:

Since , array is only used...

space used = size of array = O(n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.