Tipos de algoritmos de clasificación en la programación R

Hay varias formas en que los datos se pueden ordenar en el lenguaje R. Depende del analista de datos considerar el método más adecuado en función de la estructura de los datos. Hay varios algoritmos para realizar la clasificación de los datos en el lenguaje de programación R. A continuación se han discutido diferentes tipos de función de clasificación. Se utiliza una muestra de 10 números aleatorios entre 1 y 100 de una array. Vamos a discutir el siguiente algoritmo de clasificación:

• Ordenamiento de burbuja
• Tipo de inserción
• Clasificación de selección
• Ordenar por fusión
• Ordenación rápida

Ordenamiento de burbuja

En este algoritmo, dos elementos adyacentes se comparan y se intercambian si se cumplen los criterios. En la clasificación de burbujas, en cada iteración, el elemento más grande se lleva al final de la array (en caso de aumento) mediante el intercambio de elementos, por lo que el nombre del algoritmo es clasificación de burbujas. Para comprender el algoritmo de clasificación de burbujas en detalle, consulte Clasificación de burbujas .

# function to sort the array using bubble sort
bubble_sort <- function(x)
{
    # calculate the length of array
    n <- length(x)
             # run loop n-1 times
        for (i in 1 : (n - 1)) {
              # run loop (n-i) times
            for (j in 1 : (n - i)) {
                  # compare elements
                if (x[j] > x[j + 1]) {
                    temp <- x[j]
                      x[j] <- x[j + 1]
                      x[j + 1] <- temp
                }
            }
        }
      x
}
 
# take 10 random numbers between 1 - 100
arr <- sample(1 : 100, 10)
 
# sort the array and store the result
# in sorted_array
sorted_array <- bubble_sort(arr)
 
# print sorted_array
sorted_array

Producción:

[1]  2 19 26 68 74 76 80 81 82 91

Tipo de inserción

En este algoritmo de ordenación, se comparan los elementos ordenados y no ordenados, y el elemento no ordenado se coloca en su posición correcta después de cada iteración. En este algoritmo, se supone que el primer elemento está ordenado y el segundo elemento se almacena por separado como un elemento clave que debe ordenarse. A continuación, la clave se compara con el elemento ordenado. Si el elemento ordenado es mayor que el elemento clave, sus lugares se intercambian y el elemento clave se convierte en el primer elemento. Para comprender el algoritmo de ordenación por inserción en detalle, consulte Ordenación por inserción.

# insertion sort function to sort array
insertion_sort <- function(x)
{
      # calculate the length of array
    n <- length(x)
      # outer loop
    for (i in 2 : (n))
    {
          # store first element as key
        key = x[i]
        j   = i - 1
          # compare key with elements for
          # its correct position
        while (j > 0 && x[j] > key)
        {
          x[j + 1] = x[j]
          j = j - 1
        }
      # Place key at its correct position
      x[j + 1] = key
    }
      # return sorted array
    x
}
 
# take sample array
arr <- sample(1 : 100, 10)
 
# call insertion sort function
sorted_arr <- insertion_sort(arr)
 
# print sorted array
sorted_arr

Producción:

[1] 10 27 30 41 58 77 80 89 90 85

Clasificación de selección 

Este algoritmo de clasificación se usa ampliamente en el lenguaje R. Aquí, el elemento más pequeño de la lista desordenada se coloca al principio de la lista en cada iteración. Para comprender el algoritmo de clasificación de selección en detalle, consulte Clasificación de selección .

# function to sort array using selection sort
selection_sort <- function(x)
{
      # length of array
    n <- length(x)
      for (i in 1 : (n - 1))
    {
          # assume element at i is minimum
        min_index <- i
          for (j in (i + 1) : (n))
        {
              # check if element at j is smaller
              # than element at min_index
            if (x[j] < x[min_index]) {
                  # if yes, update min_index
                min_index = j
            }
        }
          # swap element at i with element at min_index
        temp <- x[i]
          x[i] <- x[min_index]
          x[min_index] <- temp
    }
    x
}
 
# take sample input
arr <- sample(1 : 100, 10)
 
# sort array
sorted_arr <- selection_sort(arr)
 
# print array
sorted_arr

Producción

[1] 6 16 21 28 31 48 57 73 85 99

Ordenar por fusión 

Este es un algoritmo divide y vencerás. Dividimos la array en dos partes desde la mitad, ordenamos esas dos arrays y las fusionamos. Todo el proceso se realiza de forma recursiva. Para entender el algoritmo Merge sort en detalle, consulte Merge Sort .

# function to merge two sorted arrays
merge <- function(a, b) {
      # create temporary array
    temp <- numeric(length(a) + length(b))
   
      # take two variables which initially points to
      # starting of the sorted sub arrays
      # and j which points to starting of starting
      # of temporary array
    astart <- 1
      bstart <- 1
      j <- 1
    for(j in 1 : length(temp)) {
         # if a[astart] < b[bstart]
        if((astart <= length(a) &&
            a[astart] < b[bstart]) ||
            bstart > length(b)) {
              # insert a[astart] in temp and increment
              # astart pointer to next
            temp[j] <- a[astart]
            astart <- astart + 1
        }
      else {
            temp[j] <- b[bstart]
            bstart <- bstart + 1         
        }
    }
    temp
}
 
# function to sort the array
mergeSort <- function(arr) {
   
      # if length of array is greater than 1,
      # then perform sorting
    if(length(arr) > 1) {
       
          # find mid point through which
          # array need to be divided
        mid <- ceiling(length(arr)/2)
       
          # first part of array will be from 1 to mid
        a <- mergeSort(arr[1:mid])
       
         # second part of array will be
          # from (mid+1) to length(arr)
        b <- mergeSort(arr[(mid+1):length(arr)])
       
          # merge above sorted arrays
        merge(a, b)
    }
  # else just return arr with single element
  else {
        arr
    }
}
 
# take sample input
arr <- sample(1:100, 10)
 
# call mergeSort function
result <- mergeSort(arr)
 
# print result
result

Producción

[1] 6 8 16 19 21 24 35 38 74 90

Ordenación rápida 

Este es un algoritmo divide y vencerás. Selecciona un elemento como pivote y divide la array dada alrededor del pivote elegido. El pivote puede ser aleatorio. Para comprender en detalle el algoritmo de clasificación por combinación, consulte Clasificación rápida .

# function to sort the values
quickSort <- function(arr) {
   
  # Pick a number at random
  random_index <- sample(seq_along(arr), 1);
  pivot <- arr[random_index]
  arr <- arr[-random_index]
   
  # Create array for left and right values.
  left <- c()
  right <- c()
   
  # Move all smaller and equal values to the
  # left and bigger values to the right.
  # compare element with pivot
  left<-arr[which(arr <= pivot)]
  right<-arr[which(arr > pivot)]
   
  if (length(left) > 1)
  {
    left <- quickSort(left)
  }
  if (length(right) > 1)
  {
    right <- quickSort(right)
  }
   
  # Return the sorted values.
  return(c(left, pivot, right))
}
 
# take sample array
arr <- sample(1:100, 10)
 
# call quickSort function
result <- quickSort(arr)
 
# print result
result

Producción:

[1] 13 18 21 38 70 74 80 83 95 99