Question

Use QuickSort pivot method, provide time complexity analysis.

You go to the market and you see that a store selling fruits has baskets filled with fruits for people to take kept right in front of their store. The fruits are delicious and soon you see that there are many baskets with no fruits. To ensure the store can easily replenish baskets with empty fruits, these baskets have to be kept closer to the door. Otherwise the store owner takes his time to find these empty baskets and then fill them. Come up with an algorithm that will help more the empty baskets closer to the door of the store.

Eg: Street …………. Basket_16, Basket_0, Basket_18, Basket_2, Basket_13, Basket_0, Basket_4, Basket_0, Basket_10 ……..Door

You want ,

Street ……….. Basket_16, Basket_18, Basket_2, Basket_13, Basket_4, Basket_10, Basket_0, Basket_0, Basket_0………… Door

Answer 1

Let's denote the quantity of each basket in the form of an integer array so all we have to do is move all the zeroes to end while maintaining the order of rest of the element.

C++ code using Quick sort pivot method.

#include <bits/stdc++.h>
using namespace std;

int main(){

int n;
cin >> n;
vector<int> arr(n);
for(int i=0; i<n; i++){
cin >> arr[i];
}
  
int cnt = 0;
for(int i=0; i<n; i++){
if(arr[i]!=0){
arr[cnt++] = arr[i];
}
}

for(int i=cnt; i<n; i++){
arr[i] = 0;
}

for(int i=0; i<n; i++){
cout << arr[i] << " ";
}

return 0;
}

The time complexity for this algorithm will be O(n) where n is number of baskets because we traverse all the array elements only once. This algorithm is also one pass algotrithm.

Code pic

  

Sample Input given in question

Sample Output