PROBLEM: A . The performance of the bubble sort can be improved if we stop sorti

Question

PROBLEM:

A. The performance of the bubble sort can be improved if we stop sorting process as soon as we find that in an iteration no swapping of elements takes place. Write a function than implements bubble sort algorithm using this fact.

B. Using the algorithm that you designed in part (a), find the number of iterations that are needed to sort the list: 65, 14, 52, 43, 75, 25, 80, 90, and 95.

Requirements: Start by analyzing the problem; use an IPO chart and pseudocode (or flowchart) to brainstorm the logic prior to start coding.

QUESTIONS:

1. How would the searching and sorting algorithms handle duplicates?

2.Think about alternate searching methods to sequential and binary search. What other search techniques exist? How do they compare with sequential and binary search in terms of performance?

Explanation / Answer

PROBLEM:

A. The performance of the bubble sort can be improved if we stop sorting process as soon as we find that in an iteration no
swapping of elements takes place. Write a function than implements bubble sort algorithm using this fact.

B. Using the algorithm that you designed in part (a), find the number of iterations that are needed to sort the list: 65, 14, 52, 43, 75, 25, 80, 90, and 95.

Requirements: Start by analyzing the problem; use an IPO chart and pseudocode (or flowchart) to brainstorm the logic prior to start coding.

#include<iostream>
using namespace std;
int bubble_sort(int a[], int k)
{
int count =0;
    for (int i = k-1; i > 0; --i)
    {
        bool is_swapped = false;
        for (int j = 0; j < i; ++j)
        {
            if (a[j + 1] < a[j])
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                is_swapped = true;
                count++;
            }
        }
        if (!is_swapped) break;
    }
    return count;
}
int main()
{
int a[] = {65, 14, 52, 43, 75, 25, 80, 90,95};
cout << " number of swaps " << bubble_sort(a,9) << endl;
return 0;
}


QUESTIONS:

1. How would the searching and sorting algorithms handle duplicates?

once array is sorted all duplicates will come side by side. thus making job easier to find and delete them (if required.)

2.Think about alternate searching methods to sequential and binary search.
What other search techniques exist? How do they compare with sequential and binary search in terms of performance?

sequential search takes O(n) comparisons in worst case but can be operated on any list (no need to be sorted)
binary search takes O(log2 n) comparisons in worst case but can be operated only on sorted list.
another technique is hashing but that is not directly related to search. but a faster way to search.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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