The quality control for real-time video applications, such as the very-low-bit-rate video conferencing or the high quality video entertainment, usually absents from many traditional fast block motion estimators. In this paper, a novel block-matching algorithm for fast motion estimation named adjustable partial distortion search algorithm (APDS) is proposed. It is a new normalized partial distortion comparison method with adjustability on the prediction accuracy against the searching speed using a quality factor k. When k is set to 0, APDS could act as the normalized partial distortion search algorithm (NPDS). When k is set to 1, APDS perform as the conventional partial distortion search algorithm (PDS) and could give the best quality as obtained in Full Search algorithm (FS). In addition, it uses halfway-stop technique with progressive partial distortion (PPD) to increase the chance of early rejection of impossible candidate motion vectors at very early stages. Simulations with PPD show that 24-62 times computational reduction with 0.31-0.83 dB PSNR performance degradation, as compared to the FS algorithm. Experimental results show that APDS could provide PSNR performance very close to full search algorithm with speedup ratios 18 times, and to NPDS with 32 times, respectively, as compared to FS algorithm.