#include <bits/stdc++.h> using namespace std; vector<string> split_string(string

Question

#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;
}

Step 1: Divide Choose some pivot element, p, and partition your unsorted array,arr, into three smaller arrays: le ft, right, and equal, where each element in left p, and each element in equal = p. For example: Assume arr = [5, 7, 4, 3, 8] The pivot is at arro 5 arr is divided into left-(43), equal = {5), and right-(7, 8} Putting them all together,you get (4, 3,5,7,83.Another valid solution is (3, 4, 5, 8,7 Given arr and p = arlol, partition arr into left, right, and equal using the Divide instructions above. Then print each element in le ft followed by each element in equal, followed by each element in right 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 n, the size of the array arr. The second line contains n space-separated integers describing arr (the unsorted array). The first integer (corresponding to ar(0]) is your pivot element, p. Constraints 1000 1n .-1000 ai 1000, ai E ar, 0

Explanation / Answer

Hello there I am providing answer for Step 1 and Implementation of QuicSort():

[1] Solution for step 1: Divide==>

#include<iostream>

#include<vector>

using namespace std;

vector<int> divide(vector<int> &v,int piv)
{

   int temp;
   vector<int> L;
   vector<int> R;
   int equal = piv;

   for(int i = 0; i<v.size();++i)
   {
       if(v[i]<piv)
       {
           L.push_back(v[i]);
       }
       if(v[i]>piv)
       {
           R.push_back(v[i]);
       }

   }
        for(int i=0;i<L.size();++i)
   {
      v[i] = L[i];
   }  
   v[L.size()] = equal;
        for(int i=0;i<R.size();++i)
   {
      v[L.size()+i+1] = R[i];
   }  
   return v;
}  

int main() {
    vector<int> v;
    int n;
    cin >> n;
    int temp;
    for(int i=0;i<n;++i)
    {
        cin >> temp;
        v.push_back(temp);
    }
    v=divide(v,v[0]); // You can pass any pivote value
    for(auto i=v.begin();i!=v.end();++i)
    {
        cout << *i << endl;
    }
    return 0;

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

[2] Implementation of QuickSort():

Here I used two function more to implement QuickSort,

vector<int> swap(vector<int> &v, int x, int y) {
    int temp = v[x];
    v[x] = v[y];
    v[y] = temp;
    return v;
}
vector<int> quickSort1(vector<int> &vec, int Left, int Right) {
    int i, j, mid, piv;
    i = Left;
    j = Right;
    mid = Left + (Right - Left) / 2;
    piv = vec[mid];

    while (i<Right || j>Left) {
        while (vec[i] < piv)
            i++;
        while (vec[j] > piv)
            j--;

        if (i <= j) {
            swap(vec, i, j);
                i++;
                j--;
        }
        else {
            if (i < Right)
                quickSort1(vec, i, Right);
            if (j > Left)
                quickSort1(vec, Left, j);
        return vec;
        }
    }
}

// Here is your quickSort

vector<int> quickSort(vector<int> &arr)

{
   arr= quickSort1(arr,0,arr.size());

   return arr;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Feel free to ask queries regarding above solution, I am always here to help you!!!

Thank You!!!

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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