Cree una función o programa que tome dos entradas:
- Una lista de enteros que se ordenarán (menos de 20 elementos)
- Un entero positivo
N
, que dice cuántas comparaciones debe tomar
La función se detendrá y generará la lista resultante de enteros después de las N
comparaciones. Si la lista está completamente ordenada antes de que N
se hagan las comparaciones, entonces la lista ordenada debería salir.
El algoritmo de clasificación de burbujas es bien conocido, y supongo que la mayoría de la gente lo sabe. El siguiente Pseudocódigo y animación (ambos del artículo vinculado de Wikipedia) deben proporcionar los detalles necesarios:
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember something changed */
swap( A[i-1], A[i] )
swapped = true
end if
end for
until not swapped
end procedure
La siguiente animación muestra el progreso:
Un ejemplo (tomado directamente del artículo vinculado de Wikipedia) muestra los pasos al ordenar la lista ( 5 1 4 2 8 )
:
Primer pase
1: ( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ) // Here, algorithm compares the first two elements,
// and swaps since 5 > 1.
2: ( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ) // Swap since 5 > 4
3: ( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ) // Swap since 5 > 2
4: ( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ) // Now, since these elements are already in order
// (8 > 5), algorithm does not swap them.
Segundo pase
5: ( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )
6: ( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ) // Swap since 4 > 2
7: ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
8: ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
Ahora, la matriz ya está ordenada, pero el algoritmo no sabe si está completa. El algoritmo necesita un pase completo sin ningún intercambio para saber que está ordenado.
Tercer pase
9: ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
10:( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
11:( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
12:( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
Casos de prueba:
Formato: Number of comparisons (N): List after N comparisons
Input list:
5 1 4 2 8
Test cases:
1: 1 5 4 2 8
2: 1 4 5 2 8
3: 1 4 2 5 8
4: 1 4 2 5 8
5: 1 4 2 5 8
6: 1 2 4 5 8
10: 1 2 4 5 8
14: 1 2 4 5 8
Input list:
0: 15 18 -6 18 9 -7 -1 7 19 19 -5 20 19 5 15 -5 3 18 14 19
Test cases:
1: 15 18 -6 18 9 -7 -1 7 19 19 -5 20 19 5 15 -5 3 18 14 19
21: -6 15 18 9 -7 -1 7 18 19 -5 19 19 5 15 -5 3 18 14 19 20
41: -6 9 -7 15 -1 7 18 18 -5 19 19 5 15 -5 3 18 14 19 19 20
60: -6 -7 -1 9 7 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20
61: -6 -7 -1 7 9 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20
81: -7 -6 -1 7 9 15 -5 18 18 5 15 -5 3 18 14 19 19 19 19 20
119: -7 -6 -1 -5 7 9 15 5 15 -5 3 18 14 18 18 19 19 19 19 20
120: -7 -6 -1 -5 7 9 15 5 15 -5 3 18 14 18 18 19 19 19 19 20
121: -7 -6 -1 -5 7 9 5 15 15 -5 3 18 14 18 18 19 19 19 19 20
122: -7 -6 -1 -5 7 9 5 15 15 -5 3 18 14 18 18 19 19 19 19 20
123: -7 -6 -1 -5 7 9 5 15 -5 15 3 18 14 18 18 19 19 19 19 20
201: -7 -6 -5 -1 -5 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20
221: -7 -6 -5 -5 -1 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20
- Sí, se permiten los algoritmos de clasificación de burbujas incorporados.
- No, no puede suponer solo enteros positivos o enteros únicos.
- La clasificación debe estar en el orden descrito anteriormente. No puedes comenzar al final de la lista
Respuestas:
Jalea , 25 bytes
Basado en mi respuesta en J.
Pruébalo en línea!
Verifique el número de comparaciones.
Explicación
El enlace auxiliar modifica la lista en el índice
[i-1, i]
al ordenarla, lo que produce el mismo resultado que la comparación de clasificación de burbujas.fuente
JavaScript (ES6),
10282808680 bytesCorrección de errores y 1 byte guardado gracias a @ edc65
La recursión
puede no serdefinitivamente noes probablemente el mejor enfoque, pero me estoy quedando con un bucle por ahora.Pruébalo:
Mostrar fragmento de código
fuente
f=(a,m,n=0,_,b=a[n+1])=>b+.5?m?f(a,m-1,n+1,a[n]>b?a[a[n+1]=a[n],n]=b:0):a:f(a,m,0)
.,0
1/b
lugar deb+.5
buscarundefined
Haskell,
838281 bytesEjemplo de uso:
[5,1,4,2,8] ! 5
->[1,4,2,5,8]
.En la función
%
y
realiza un seguimiento de los elementos visitados hasta ahora durante el pase actual,x
aún no se han examinado.a
yb
son los dos siguientes, es decir, los candidatos para intercambiar. Si se llega al final de la lista, comenzamos desde el principio:y%x = []%(y++x)
. Todos los pasos se almacenan en una lista donde la función principal selecciona eln
elemento th.Editar: las versiones anteriores no funcionaban para listas de elementos individuales, por suerte la nueva versión es aún más corta.
fuente
f=
antes de la segunda línea de la respuesta, luego agregue una tercera línea al programa que contienemain=print(f [5,1,4,2,8] 5)
. Eso debería hacerlo ejecutable.Python 3,
7774 bytes-3 bytes gracias a @Maltysen (init
j
en la declaración)Casos de prueba en ideone
Suele
sorted
hacer cada operación de comparación e intercambio, pero está realizando una clasificación de burbujas.Conjuntos
j=0
(el índice izquierdo), lleva a cabo luegon
comparar y permutas de elementos de la lista, al restablecer adyacentesj
a0
cada vez que esta ventana sale.Se
j*=j<len(l)-1
multiplicaráj
porFalse
(es decir0
) en ese punto, mientras que cada dos veces se multiplicaráj
porTrue
(es decir1
).(Todavía funcionará para una lista vacía también).
fuente
j
, puede usar%
eval
MATLAB debido a las asignaciones en línea.PowerShell v2 +,
135129 bytesEntonces. Muchos. Dólares
( Ahorró seis bytes al darse cuenta de que este desafío no incluye la optimización "gratuita" de omitir los últimos elementos en cada pase, ya que está garantizado ordenado, y en su lugar ejecuta un pase completo cada vez. Esto movió
$a.count
elfor
loop y eliminó la$z
variable ) .Tipo de burbuja recta, con un punto ingenioso, haciendo el intercambio en un solo paso:
$a[$_],$a[$_+1]=$a[$_+1],$a[$_]
La lógica existente se maneja a través de
if(!--$n){$a;exit}
Casos de prueba
(La matriz se muestra como separada por espacios aquí porque el Separador de campo de salida predeterminado para encadenar una matriz es un espacio. La secuenciación ocurre porque estamos concatenando con las etiquetas
"$_ -> "
).fuente
R,
132131112136 bytesEl programa recibe la entrada de la siguiente manera: primero
N
, luego el vector mismo. Por ejemplo, si quieresv = [5 1 4 2 8]
yn = 1
, la entrada que entra en elscan
es1 5 1 4 2 8
. Entonces, para ejecutar este programa, ejecuta la primera línea , alimenta los números uno por uno en la consola y luego ejecuta el resto (esta es una respuesta REPL).Entonces el siguiente código hace el truco:
Prueba:
Actualización: golfed 1 byte debido a Vlo .
fuente
Pyth,
3432 bytesUna traducción de la respuesta de Python de Jonathan Allan.
Pruébalo aquí!
fuente
JavaScript (ES6),
828079 bytesBasado en la respuesta original de @ ETHproduction. Editar: Guardado 2 bytes gracias a @JonathanAllan. Guardado 1 byte gracias a @ edc65.
fuente
J ,
6260 bytesEste es un verbo que toma dos argumentos: el número de comparaciones en el LHS y la lista de enteros en el RHS. Primero verifica si la longitud de la lista es mayor que uno. Si no es así, devuelve la lista sin modificar, de lo contrario, opera en ella realizando el número especificado de comparaciones antes de devolver el resultado.
Uso
Para el primer caso de prueba, los comandos adicionales se utilizan para formatear múltiples entradas / salidas. El segundo caso de prueba se muestra como entrada / salida única.
Explicación
Es difícil escribir código conciso en J que use mutabilidad, por lo que, en cambio, convierto el problema en reducir una lista en un conjunto de indicaciones. Creo que este código es desordenado, así que explicaré el trabajo de cada frase en lugar de cada primitiva. La primera parte toma la longitud de la lista y produce un rango. Luego, opere en cada infijo de tamaño 2 para emular una pasada de comparaciones.
Estas son las indicaciones iniciales de cada comparación. Si se realizan 7 comparaciones, modifíquelo para obtener la cantidad deseada. J analiza de derecha a izquierda, por lo que se reduce de derecha a izquierda, como doblar a la derecha. Agregue la lista inicial y revertirla.
Alternativamente, se puede hacer el rango [0, 7) y tomar cada valor módulo a lo largo de la lista menos 1 para crear el mismo rango.
La última parte es un verbo que toma una lista en el RHS y un índice en el LHS que marca el índice de inicio de la comparación. Seleccione los dos elementos que comienzan en ese índice, ordénelos, vuelva a conectarlos a la lista y devuélvalos.
fuente
Matlab,
9391 bytesAhorra 11 bytes al omitir
if l(i)>l(i+1);l(i:i+1)=l([i+1,i])
, y en su lugar solo ordena los dos elementos cada vez. Funciona para listas de longitud 1. Podría guardar un byte o dos usando elm--
operador de Octave , pero eso no es mucho.Guarda dos bytes más configurando
n=numel(l)-1;
, porque entonces puedo hacer enwhile n
lugar dewhile n>1
y eni=mod(i,n)+1
lugar dei=mod(i,n-1)+1
.Para el registro, esta respuesta se escribió muchas horas después de que se creó el desafío.
fuente
Groovy (101 bytes)
EDITAR: no necesitaba escribir mi propio cierre de intercambio, Groovy tenía esto incorporado.
Pruébalo aquí: https://groovyconsole.appspot.com/script/5104724189642752
Ejemplo de seguimiento de salida:
Implementación anterior (122 bytes)
Pruébelo aquí: https://groovyconsole.appspot.com/script/6316871066320896
fuente
php,
148145bytesNo estoy muy contento con la estructura del bucle, pero me gusta el cambio de lista y funciona, así que lo estoy publicando de todos modos. php7.1 me permitiría guardar al menos 4 bytes.
Con mejor formato:
Editar: Jörg Hülsermann me recordó unirme, en lugar de implosionar.
nota: debe estar en un archivo con un solo nombre de archivo de caracteres.
fuente
Ruby,
5250 bytesEspera ... no Ruby?
fuente