バケツソート
(sort/bucket-sort.hpp)

• View this file on GitHub
• Last update: 2022-11-29 19:12:01+09:00
• Include: #include "sort/bucket-sort.hpp"
• Link: View error logs on GitHub Actions

Verified with

• verify/AOJ-ALDS1_6_A.test.cpp

Code

#pragma once
void bucketSort(vector<int> &target){
  int n = target.size();
  int mx = *max_element(target.begin(), target.end());
  assert(mx < 100000000);
  vector<int> bucket(mx+1, 0);
  for(int &t: target) ++bucket[t];

  int cur = 0;
  for(int i = 0; i <= mx; ++i){
    for(int j = 0; j < bucket[i]; ++j){
      target[cur] = i;
      ++cur;
    }
  }
}

#line 2 "sort/bucket-sort.hpp"
void bucketSort(vector<int> &target){
  int n = target.size();
  int mx = *max_element(target.begin(), target.end());
  assert(mx < 100000000);
  vector<int> bucket(mx+1, 0);
  for(int &t: target) ++bucket[t];

  int cur = 0;
  for(int i = 0; i <= mx; ++i){
    for(int j = 0; j < bucket[i]; ++j){
      target[cur] = i;
      ++cur;
    }
  }
}

Back to top page