Clasificando permutaciones con varias operaciones tiene aplicaciones en genética y redes de interconexión de computadoras donde una operación está especificada por su conjunto generador. Un árbol de transposición es un árbol de expansión sobre vértices . denota una operación en la que cada borde es un generador. Un valor asignado a un vértice se llama o un . Los marcadores en los vértices y solo se pueden intercambiar si el par . La configuración inicial consiste en una biyección del conjunto de vértices al conjunto de marcadores . El objetivo es la configuración inicial de , es decir, una permutación de entrada, aplicando el número mínimo de intercambios o en . Algoritmos óptimos computacionalmente viables para ordenar permutaciones solo se conocen para algunas clases de árboles de transposición. Estudiamos una clase de árboles de transposición llamada y su variación a . Un es un árbol obtenido uniendo el vértice central de una estrella con uno de los dos vértices hoja de un grafo de ruta. Un es una extensión de una escoba simple donde el vértice central de una segunda estrella está conectado al vértice terminal de la ruta en una escoba simple. Proponemos un algoritmo simple y eficiente para obtener una secuencia de intercambio óptima para ordenar permutaciones con el árbol de transposición escoba y un nuevo algoritmo óptimo para ordenar permutaciones con una escoba doble. También introducimos una nueva clase de árboles llamada y demostramos que produce un límite superior más ajustado para ordenar permutaciones con un árbol de milpiés equilibrado en comparación con . Los algoritmos y están diseñados previamente.