We study jump-penalized estimators based on least absolute deviations which are often referred to as Potts estimators. They are estimators for a parsimonious piecewise constant representation of noisy data having a noise distribution which has heavier tails or which leads to many severe outliers. We consider real-valued data as well as circle-valued data which appear, for instance, as time series of angles or phase signals. We propose efficient algorithms that compute Potts estimators for real-valued scalar as well as for circle-valued data. The real-valued version improves upon the state-of-the-art solver w.r.t. to computational time. In particular for quantized data, the worst case complexity is improved. The circle-valued version is the first efficient algorithm of this kind. As an illustration, we apply our method to estimate the steps in the rotation of the bacterial flagella motor based on real biological data, and to the estimation of wind directions.