algorithm - filas - ¿Cómo ordenar una matriz en un solo bucle?

ordenar matriz excel

Question

Así que estaba pasando por diferentes algoritmos de clasificación. Pero casi todos los algoritmos de clasificación requieren 2 bucles para ordenar la matriz. La complejidad de tiempo de la clase de ordenación e inserción de burbuja es O (n) para el mejor caso pero es O (n ^ 2) como el peor caso, que de nuevo requiere 2 bucles. ¿Hay alguna manera de ordenar una matriz en un solo bucle?

Answer 1

Aquí, un Bubble Sort de un solo ciclo en Python:

def bubbly_sortish(data):
    for _ in xrange(len(data)**2):
        i, j = _/len(data), _%len(data)
        if i<j and data[i] > data[j]:
            data[i], data[j] = data[j], data[i]

A = [5, 1, 2, 3, 5, 6, 10]
bubbly_sortish(A)

print A            

Por supuesto esto es una broma. Pero esto muestra que el número de bucles tiene poco que ver con la complejidad del algoritmo.

Ahora, si está preguntando si es posible ordenar una matriz con comparaciones O (n), no, no es posible . El límite inferior es Ω (n log n) para los algoritmos de clasificación basados ​​en la comparación.

Answer 2

Single Loop Bubble Ordenar usando C ++

int a[7]={5,7,6,2,4,3,1};

int temp = 0;

int j = 0;

for(int i = 0 ; i<a[]-1 ; i++)
{
    int flag = 0;
    if(a[i]>a[i+1])
    {
        temp = a[i];
        a[i] = a[i+1];
        a[i+1] = temp;
        flag = 1;
    }       
    if(i == 7-2-j)
    {
        if(!flag) break;
        i = -1;
        j++;
    }
}

Answer 3

Single for loop para ordenar por inserción:

function insertionSort (array) {
    for(var i = 1 ; i < array.length ;){
        if(array[i] < array[i-1]){
            var temp = array[i]
            array[i] = array[i -1]
            array[i -1] = temp
            i--
        } else{i++}
    }
    return array
}

Answer 4

Aquí hay una versión de trabajo para su ejemplo dado:

Una manera muy eficiente y lógica de hacer el problema funciona si conoce el rango de los valores a clasificar, por ejemplo 0 <= val <= 100 donde val es entero.

Luego puede hacerlo con una sola operación de lectura y escritura en solo dos bucles ... uno para leer la matriz, y otra para escribirlo:

Use una segunda matriz donde los índices representen los valores 0-100, almacene en ella la cantidad de veces que se encuentra cada valor 0-100, por ejemplo val = 100 podría existir 234 veces en su matriz objetivo ...

Solo hay un ciclo de lectura y un ciclo de escritura, que es computacionalmente tan eficiente como un ciclo que haría tanto la lectura como la escritura y más rápido que un ciclo que usa comparación ... Si insistes, puedes hacerlo en un solo bucle dos veces más largo que la longitud de la matriz objetivo y restablecer valor a cero en la nueva operación de escritura de matriz.

El segundo ciclo simplemente escribe para el recuento de cada valor encontrado en la primera matriz.

Answer 5

En el caso general, tiene O (n lg n) como promedio.

Pero en casos particulares, el mejor caso es O (n), que considero lo suficientemente cercano a lo que llamaría "solo un ciclo", aunque la implementación puede mostrar más de una instancia de la palabra clave for . Y las buenas noticias con eso, es que no dependes de la suerte para hacer realidad tu mejor caso. Siempre que conozca algunas propiedades sobre sus datos, puede elegir algunos algoritmos específicos. Por ejemplo :

• El servicio rápido de 3 vías se ejecuta muy cerca de O (n) cuando tiene muchos elementos con solo unas pocas claves de clasificación distintas (piense en las entradas del registro del servidor como elementos y las fechas como claves).
• El recuento de ordenaciones se ejecuta en O (n + k) si las claves son fácilmente indexables (como un conjunto de caracteres o enteros pequeños), y el índice tiene un límite superior conocido k.
• Burstsort se ejecutará en O (wn) si se trata de cadenas de longitud máxima w.

Esos son solo tres ejemplos. Hay muchos más, demasiados para recordar desde lo más alto de mi cabeza, para muchos tipos de conjuntos de datos restringidos. Si tiene a mano un caso de la vida real donde O (n lg n) no es lo suficientemente bueno, vale la pena realizar una investigación adecuada, siempre que haya identificado algunas propiedades interesantes en sus datos .

Answer 6

Tipo de arreglo de bucle único:

for(int i = 0, j=i+1; i < arr.length && j<arr.length;)
    {       
        if(arr[i] > arr[j])
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;              
            i=0;
            j=i+1;
        } 
        else
        {
            i++;
            j++;
        }
    }