can you complete this code? Step 1: Divide Choose some pivot element, , and part

Question

can you complete this code?

Step 1: Divide
Choose some pivot element, , and partition your unsorted array, , into three smaller arrays: , , and , where each element in , each element in , and each element in .

For example: Assume  
The pivot is at  
is divided into , , and .
Putting them all together, you get . Another valid solution is .

Given and , partition into , , and using the Divide instructions above. Then print each element in followed by each element in , followed by each element in on a single line. Your output should be space-separated and does not have to maintain ordering of the elements within the three categories.

Input Format

The first line contains , the size of the array .
The second line contains space-separated integers describing (the unsorted array). The first integer (corresponding to ) is your pivot element, .

Constraints
1<= n <= 1000
-1000 <=a <= 1000, 0<= i < n
All elements will be unique.
Output Format

On a single line, print the partitioned numbers (i.e.: the elements in , then the elements in , and then the elements in ). Each integer should be separated by a single space.

Sample Input

5
4 5 3 7 2
Sample Output

3 2 4 5 7

We then print the elements of left, followed by equal, followed by right, we get: 3 2 4 5 7.

You don't need to maintain ordering, so another valid solution would be 2 3 4 5 7.

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the quickSort function below.
vector<int> quickSort(vector<int> arr) {

}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

int n;
cin >> n;
cin.ignore(numeric_limits<streamsize>::max(), ' ');

string arr_temp_temp;
getline(cin, arr_temp_temp);

vector<string> arr_temp = split_string(arr_temp_temp);

vector<int> arr(n);

for (int i = 0; i < n; i++) {
int arr_item = stoi(arr_temp[i]);

arr[i] = arr_item;
}

vector<int> result = quickSort(arr);

for (int i = 0; i < result.size(); i++) {
fout << result[i];

if (i != result.size() - 1) {
fout << " ";
}
}

fout << " ";

fout.close();

return 0;
}

vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});

input_string.erase(new_end, input_string.end());

while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}

vector<string> splits;
char delimiter = ' ';

size_t i = 0;
size_t pos = input_string.find(delimiter);

while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));

i = pos + 1;
pos = input_string.find(delimiter, i);
}

splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

return splits;
}

Explanation / Answer

Below is the C++ code I hope that i have provided sufficient comments for your better understanding Note that I have done proper indentation but this code is automatically left alligned on this interface

vector<int> quickSort(vector<int> arr)
{
int low=0,high=arr.size()-1;
int pivot,i,j,temp;

//base condition
if(low<high)
{
pivot=low;
i=low;
j=high;
while(i<j)
{

//place all elements smaller then the pivot to its left
while(arr[i]<=arr[pivot]&&i<=high)
i++;

//place all elements larger then the pivot to its right
while(arr[j]>arr[pivot]&&j>=low)
j--;

//swap if necessary
if(i<j)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
temp=arr[j];
arr[j]=arr[pivot];
arr[pivot]=temp;

//recursively call the functin for each left and right subarray
quicksort(arr,low,j-1);
quicksort(arr,j+1,high);
}
return arr;
}

Hope i have answered your question satisfactorily.Leave doubts in comment section if any.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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