In his study of Kazhdan-Lusztig cells in affine type A, Shi has introduced an affine analog of Robinson-Schensted correspondence. We generalize the Matrix-Ball Construction of Viennot and Fulton to give a more combinatorial realization of Shi's algorithm. As a byproduct, we also give a way to realize the affine correspondence via the usual Robinson-Schensted bumping algorithm. Next, inspired by Honeywill, we extend the algorithm to a bijection between the extended affine symmetric group and collection of triples $(P, Q, r)$ where $P$ and $Q$ are tabloids and $r$ is a dominant weight.