USA: +1 (725) 712-1730 
Sign in
![Please Dont forget to use C++ 7. You have to use c++ to solve this problem. Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the firstk characters and left the other as original. Restrictions: 1. The string consists of lower English letters only. 2. Length of the given string and k will in the range [1, 10000] Input: s-abcdefg, k = 2 Output: bacdfeg Please write your program with this class: class Solution public: string reverseStr(string s, int k) ( 8. Implement Bubble Sort and INSERTION-SORT using c++. What is the time complexity?](https://d2vlcm61l7u1fs.cloudfront.net/media%2F163%2F163f3f76-b384-4627-b979-fe9fd1f98fd6%2FphpEfM8DC.png)
Please Don’t forget to use C++ You have to use c++ to solve this problem. Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original. Restrictions: 1. The string consists of lower English letters only. 2. Length of the given string and k will in the range [1, 10000] Input: s = “abcdefg”, k = 2 Output: “bacdfeg” Please write your program with this class: class Solution { public: string reverseStr(string s, int k) { }: Implement Bubble Sort and INSERTION-SORT using c++. What is the time complexity?
Expert Answer
Solution:
Bubble Sort:
#include <stdio.h>
void swapFunction(int *ab, int *cd)
{
int t = *ab; // Swapping the values suing third variable
*ab = *cd;
*cd = t;
}
// Function for Bubbble Sort
void sortBubble(int array[], int a)
{
int m, n;
for ( int m = 0; m < a-1; m++)
// some values are already in place
for (n = 0; n < a-m-1; n++)
if (array[n] > array[n+1])
swapFunction(&array[n], &array[n+1]);
}
// Below function is for displaying the array
void displayArray(int array[], int length)
{
for (int i=0; i < length; i++)
printf(“%d “, array[i]);
printf(“n”);
}
// Main function is given below
int main()
{
int array[] = {15, 95, 25, 11, 63, 2, 5, 87}; // Array declaration with initialization
int a = sizeof(array)/sizeof(array[0]); // For calculating current size fo the given array
sortBubble(array, a); // Function of Bubble Sort is called here
printf(“Sorted array: n”); // Displaying the sorted array
displayArray(array, a);
return 0;
}
Output:
The time complexity of Bubble sort is T(n)= O(n^2), in the best case when the input array is sorted time time complexity T(n)= O(n).
Insertion sort:
// C program for insertion sort
#include <stdio.h>
#include <math.h>
/* Function to sort an array using insertion sort*/
void sortInsertion(int arr[], int a)
{
int m, key, n;
for (m = 1; m < a; m++)
{
key = arr[m];
n = m-1;
while (n >= 0 && arr[n] > key) // Move the items which are greater than the key to ahead of there position
{
arr[n+1] = arr[n];
n = n-1;
}
arr[n+1] = key; // When the pass(comparing key with complete array) is finished then assign next element to the key
}
}
void displayArray(int array[], int length) // To display the array
{
for (int i=0; i < length; i++)
printf(“%d “, array[i]);
printf(“n”);
}
// Main function is given below
int main()
{
int array[] = {15, 95, 25, 11, 63, 2, 5, 87}; // Array declaration with initialization
int a = sizeof(array)/sizeof(array[0]); // For calculating current size fo the given array
sortInsertion(array, a); // Function of Insertion Sort is called here
printf(“Sorted array: n”); // Displaying the sorted array
displayArray(array, a);
return 0;
}
Output:
Worst Case T(n)= O(n^2), and best case T(n)= O(n).
