Algoritmos de intercambio de bloques

En algoritmos informáticos , los algoritmos de intercambio de bloques intercambian dos regiones de elementos de una matriz . Es sencillo intercambiar dos regiones no superpuestas de una matriz de igual tamaño. Sin embargo, no es tan sencillo intercambiar dos regiones contiguas de una matriz de tamaños desiguales (los algoritmos que realizan este intercambio se denominan algoritmos de rotación ). Algunos algoritmos conocidos pueden lograr esto: el algoritmo de malabarismo de Bentley (también conocido como algoritmo delfín ^{[ 1 ]} ), la rotación de Gries-Mills ^{[ 1 ]} , el algoritmo de triple inversión , el algoritmo de triple inversión conjunta (también conocido como rotación de la trinidad ) y la rotación sucesiva . ^{[ 1 ] [ 2 ]}

El algoritmo de triple inversión es el más sencillo de explicar, ya que utiliza rotaciones. Una rotación consiste en invertir in situ los elementos de un array. Este método intercambia dos elementos de un array desde fuera hacia dentro dentro de un rango. La rotación funciona tanto para un número par como impar de elementos del array. El algoritmo de inversión utiliza tres rotaciones in situ para realizar un intercambio de bloques in situ:

• Rotar la región A
• Rotar la región B
• Rotar la región AB

Donde A y B son regiones adyacentes de una matriz que juntas forman la región AB.

Los algoritmos de Gries-Mills y de reversión funcionan mejor que el método de Bentley, debido a su comportamiento de acceso a la memoria que favorece el uso de la caché .

El algoritmo de triple inversión se paraleliza bien, porque las rotaciones se pueden dividir en subregiones, que se pueden rotar independientemente de las demás.