This asked me to implement Bubble sort and insertion sort using C++. What is the

Question

This asked me to implement Bubble sort and insertion sort using C++. What is the time complexity? It says run the code on dataset which i have. But how would i use the dataset to get the time complexity for each data?

#include <iostream>

using namespace std;

void swap(int &x, int &y)

{

int temp = x;

x = y;

y = temp;

}

void bubbleSort(int arr[], int n)

{

int i, j;

for (i = 0; i < n-1; i++)

for (j = 0; j < n-i-1; j++)

if (arr[j] > arr[j+1])

swap(arr[j], arr[j+1]);

}

void insertionSort(int arr[], int n)

{

int i, key, j;

for (i = 1; i < n; i++)

{

key = arr[i];

j = i-1;

while (j >= 0 && arr[j] > key)

{

arr[j+1] = arr[j];

j = j-1;

}

arr[j+1] = key;

}

}

void printArray(int arr[], int size)

{

for (int i=0; i < size; i++)

cout<<arr[i]<<" ";

cout<<endl;

}

int main()

{

//ifstream input("myfile");

int arr[] = {64, 34, 25, 12, 22, 11, 90};

int n = 7;

bubbleSort(arr, n);

cout<<"Sorted array: ";

printArray(arr, n);

return 0;

}

exec exec exec exec exec data0.1024 data0.2048 data0.4096 data0.8192 data0.16384 exec exec exec exec exec data0.32768 data1.1024 data1.2048 data1.4096 data1.8192 exec exec data1.16384 data1.32768

Explanation / Answer

TIme Complexity of Insertion Sort:

Time Complexity: O(n*n)

Auxiliary Space: O(1)

Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

Time Complexity of Bubble Sort:

Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.

Best Case Time Complexity: O(n). Best case occurs when array is already sorted.

Auxiliary Space: O(1)

Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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