Clasificación de gnomos

Gnome Sort, también llamado Stupid sort, se basa en el concepto de un gnomo de jardín que clasifica sus macetas. Un gnomo de jardín clasifica las macetas con el siguiente método:  

• Mira la maceta a su lado y la anterior; si están en el orden correcto, avanza un bote; de ​​lo contrario, los cambia y retrocede un bote.
• Si no hay bote anterior (él está al comienzo de la línea de bote), da un paso adelante; si no hay una olla a su lado (está al final de la línea de la olla), está acabado.

Entrada –  

Array- arr[]  
Elementos totales – n

¿Cómo funciona la ordenación de gnomos?

Consideremos un ejemplo: arr[] = {34, 2, 10, -9}

• Los elementos subrayados son el par en consideración.
• son el par que necesita ser intercambiado.
• El resultado del intercambio se colorea como «azul»

 

Pasos del algoritmo:

• Si está al comienzo de la array, vaya al elemento correcto (de arr[0] a arr[1]).
• Si el elemento de array actual es más grande o igual que el elemento de array anterior, vaya un paso a la derecha

 if (arr[i] >= arr[i-1])
 i++;

• Si el elemento de array actual es más pequeño que el elemento de array anterior, intercambie estos dos elementos y retroceda un paso

 if (arr[i] < arr[i-1])
{
swap(arr[i], arr[i-1]);
 i-;
} 

• Repita los pasos 2) y 3) hasta que ‘i’ llegue al final de la array (es decir, ‘n-1’)
• Si se llega al final de la array, se detiene y se ordena la array.

A continuación se muestra la implementación del algoritmo.

// A C++ Program to implement Gnome Sort
#include <iostream>
using namespace std;
  
// A function to sort the algorithm using gnome sort
void gnomeSort(int arr[], int n)
{
    int index = 0;
  
    while (index < n) {
        if (index == 0)
            index++;
        if (arr[index] >= arr[index - 1])
            index++;
        else {
            swap(arr[index], arr[index - 1]);
            index--;
        }
    }
    return;
}
  
// A utility function ot print an array of size n
void printArray(int arr[], int n)
{
    cout << "Sorted sequence after Gnome sort: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << "\n";
}
  
// Driver program to test above functions.
int main()
{
    int arr[] = { 34, 2, 10, -9 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    gnomeSort(arr, n);
    printArray(arr, n);
  
    return (0);
}

// Java Program to implement Gnome Sort
  
import java.util.Arrays;
public class GFG {
    static void gnomeSort(int arr[], int n)
    {
        int index = 0;
  
        while (index < n) {
            if (index == 0)
                index++;
            if (arr[index] >= arr[index - 1])
                index++;
            else {
                int temp = 0;
                temp = arr[index];
                arr[index] = arr[index - 1];
                arr[index - 1] = temp;
                index--;
            }
        }
        return;
    }
  
    // Driver program to test above functions.
    public static void main(String[] args)
    {
        int arr[] = { 34, 2, 10, -9 };
  
        gnomeSort(arr, arr.length);
  
        System.out.print("Sorted sequence after applying Gnome sort: ");
        System.out.println(Arrays.toString(arr));
    }
}
  
// Code Contributed by Mohit Gupta_OMG

# Python program to implement Gnome Sort
  
# A function to sort the given list using Gnome sort
def gnomeSort( arr, n):
    index = 0
    while index < n:
        if index == 0:
            index = index + 1
        if arr[index] >= arr[index - 1]:
            index = index + 1
        else:
            arr[index], arr[index-1] = arr[index-1], arr[index]
            index = index - 1
  
    return arr
  
# Driver Code
arr = [ 34, 2, 10, -9]
n = len(arr)
  
arr = gnomeSort(arr, n)
print "Sorted sequence after applying Gnome Sort :",
for i in arr:
    print i,
  
# Contributed By Harshit Agrawal

// C# Program to implement Gnome Sort
using System;
  
class GFG {
      
    static void gnomeSort(int[] arr, int n)
    {
        int index = 0;
  
        while (index < n) 
        {
            if (index == 0)
                index++;
            if (arr[index] >= arr[index - 1])
                index++;
            else {
                int temp = 0;
                temp = arr[index];
                arr[index] = arr[index - 1];
                arr[index - 1] = temp;
                index--;
            }
        }
        return;
    }
  
    // Driver program to test above functions.
    public static void Main()
    {
        int[] arr = { 34, 2, 10, -9 };
          
        // Function calling
        gnomeSort(arr, arr.Length);
  
        Console.Write("Sorted sequence after applying Gnome sort: ");
  
        for (int i = 0; i < arr.Length; i++)
            Console.Write(arr[i] + " ");
    }
}
  
// This code is contributed by Sam007

<?php
// PHP Program to implement
// Gnome Sort
  
// A function to sort the 
// algorithm using gnome sort
function gnomeSort($arr, $n)
{
    $index = 0;
  
    while ($index < $n) 
    {
        if ($index == 0)
            $index++;
        if ($arr[$index] >= $arr[$index - 1])
            $index++;
        else 
        {
            $temp = 0;
            $temp = $arr[$index];
            $arr[$index] = $arr[$index - 1];
            $arr[$index - 1] = $temp;
            $index--;
        }
    }
    echo "Sorted sequence ", 
         "after Gnome sort: ";
    for ($i = 0; $i < $n; $i++)
        echo $arr[$i] . " ";
    echo "\n"; 
}
  
// Driver Code
$arr = array(34, 2, 10, -9);
$n = count($arr);
  
gnomeSort($arr, $n);
  
// This code is contributed
// by Sam007
?>

<script>
  
// Javascript Program to implement Gnome Sort
  
   function gnomeSort(arr, n)
    {
        let index = 0;
    
        while (index < n) {
            if (index == 0)
                index++;
            if (arr[index] >= arr[index - 1])
                index++;
            else {
                let temp = 0;
                temp = arr[index];
                arr[index] = arr[index - 1];
                arr[index - 1] = temp;
                index--;
            }
        }
        return;
    }
  
// Driver Code
      
        let arr = [34, 2, 10, -9 ];
    
        gnomeSort(arr, arr.length);
    
        document.write("Sorted sequence after applying Gnome sort: ");
        document.write(arr.toString());
            
</script>

Sorted sequence after Gnome sort: -9 2 10 34 

Complejidad de tiempo: como no hay un bucle anidado (solo un tiempo), puede parecer que se trata de un algoritmo de tiempo lineal O (N). Pero la complejidad del tiempo es O(N^2).

Esto es porque: 

• La variable – ‘índice’ en nuestro programa no siempre se incrementa, también se reduce. 
• Sin embargo, este algoritmo de clasificación es adaptable y funciona mejor si la array ya está parcialmente ordenada.

Espacio auxiliar: este es un algoritmo en el lugar. Entonces se necesita espacio auxiliar O(1) .

Echa un vistazo al curso de autoaprendizaje de DSA

Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.