車輪の再発明をがんばらなくても、std::swapを使えばいいだけの話では?
それ以前に std::random_shuffle を使えば一瞬なのでは?