Lily's Homework

  • + 0 comments

    I see a lot of people confused by this one. The trick is to not worry about the specific sorting method, you will never get the correct number of swaps with quicksort.

    The second trick is to avoid reversing the SORTED list. You have to reverse the ORIGINAL data. C++20 implementation

    auto countSwaps(std::vector<int> data, bool reverseData = false) {
      auto sorted(data);
      sort(sorted.begin(), sorted.end());
    
      if (reverseData)
        reverse(data.begin(), data.end());
    
      std::unordered_map<int, int> indexArray;
      transform(data.begin(), data.end(), inserter(indexArray, indexArray.end()),
        [idx = 0](int value) mutable {return std::make_pair(value, idx++); }
      );
    
      auto counter = 0;
      for (auto i = 0; i < sorted.size(); ++i) {
        auto expected = sorted[i]; // This is the value I would normally expect to find in data if it was sorted
        auto& original = data[i]; // Reference to the original data item in position [i]
        if (expected == original)
          continue;
        auto expectedPos = indexArray[expected];
        indexArray[original] = expectedPos;
        std::swap(original, data[expectedPos]);
        ++counter;
      }
      return counter;
    };
    int lilysHomework(std::vector<int> arr) {
      return std::min(countSwaps(arr), countSwaps(arr, true));
    }