{ comparisons = 0; movements = 0; for (int i = 0; i < numberOfElements-1; i++) {
ID: 3617141 • Letter: #
Question
{
comparisons = 0;
movements = 0;
for (int i = 0; i < numberOfElements-1; i++) {
for (int j = 0; j < numberOfElements-1-i; j++) {
// compare neighboring elements, and swap if required
comparisons++;
if (elements[j] > elements[j+1]) {
swap(elements[j], elements[j+1]);
movements += 3;
}
}
}
ordered = true; // KNOWN to be ordered
}
void AList::InsertionSort(int& comparisons, int& movements)
//Precondition: none
//Postcondition: elements have been sorted using Insertion Sort algorithm
{
comparisons = 0;
movements = 0;
int i;
int hold;
for (int next = 1; next < numberOfElements; next++) {
movements++;
hold = elements[next];
for (i = next-1; i >= 0; i--) {
comparisons++;
if (elements[i] > hold) {
movements++;
elements[i+1] = elements[i];
} else {
break;
}
}
movements++;
elements[i+1] = hold;
}
ordered = true; // KNOWN to be ordered
}
Explanation / Answer
in bubble sort each element is checked with the next one andif the first element is grearter then second one than both areswaped. for example 25,12,14,18,52,13 25 and 12 are checked 25 is greater than 12 so they willswap 12,25,14,18,52,13 12,25,14,18,52,13 next 25 and 14 are checked, 25 is also greater than 14,swap 12,14,25,18,52,1312,14,25,18,52,13 now 25 and 18 are checked, 25 is greater than 18, swap onceagain 12,14,18,25,52,13
12,14,18,25,52,13 now 25 and 52 are checked, 25 is not greater than 52,no swap 12,14,18,25,52,13 now 52 and 13 are checked and swap will takeplace. 12.14.18.25.13.52
One element (52) is sorted now start next iteration ofloop.
in insertion sort, we select one element and thenchecks backward to its and where it fits we place ittheir. if you play cards than you use insertion sort to sortcards in your hands.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.