Execute these using C++ language. You are to do the following: 4. Modify the bub
ID: 3688184 • Letter: E
Question
Execute these using C++ language.
You are to do the following:
4. Modify the bubble-sort function such that the outer loop stops iterating as soon as there have been no swaps in the inner loop. That is, as soon as the array is already sorted.
5. Modify each function such that you count the number of comparisons between array elements that they perform. Each function will output the final sorted array and the number of comparisons the function has performed.
In each of the following questions you are given two functions A and B.
You need to find an array for each case such that function A outperforms function B (i.e. number of comparisons function A performs / number of comparisons function B performs is minimized: the smaller this number higher your score).
You may write a separate C++ program (or program segment, or function) for each case. Make sure that THE ORGINAL ARRAY YOU FIND (INPUT) (this input is to be hard-coded in your submission), the final sorted array, number of comparisons, and ratio of number of comparisons are printed for each case.
Note that to be able to answer this question you should understand how each algorithm works, and works best on what kind of input, while other alternate algorithms do not perform similarly well (perform much worse as much as possible).
a) A=Selection Sort, B=Insertion Sort
b) A=Selection Sort, B=Modified Bubble Sort
c) A=Insertion Sort, B=Selection Sort
d) A=Insertion Sort, B=Modified Bubble Sort
e) A=Modified Bubble Sort, B=Insertion Sort
f) A=Modified Bubble Sort, B=Selection Sort
Selection Sort:
void selection(int a[], int l, int r)
{ for (int i = l; i < r; i++)
{ int min = i;
for (int j = i+1; j <= r; j++)
if (a[j] < a[min]) min = j;
exch(a[i], a[min]);
} }
Insertion Sort:
void insertion(int a[], int l, int r)
{ int i; for (i = r; i > l; i--) compexch(a[i-1], a[i]);
for (i = l+2; i <= r; i++)
{ int j = i; int v = a[i];
while (v < a[j-1])
{ a[j] = a[j-1]; j--; }
a[j] = v; }
}
Bubble Sort:
void bubble(int a[], int l, int r)
{ for (int i = l; i < r; i++)
for (int j = r; j > i; j--) compexch(a[j-1], a[j]);
}
Explanation / Answer
4)
def modifiedBubbleSort(numlist):
exchanges = True
passnum = len(numlist)-1
while passnum > 0 and exchanges:
exchanges = False
for i in range(passnum):
if numlist[i]>numlist[i+1]:
exchanges = True
temp = numlist[i]
numlist[i] = numlist[i+1]
numlist[i+1] = temp
passnum = passnum-1
numlist=[1,2,3,4,5,6,7,8,9];
modifiedBubbleSort(numlist);
print(numlist);
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.