Gnome sort

Algoritmo similiar ao Insertion sort com a diferença que o Gnome sort leva um elemento para sua posição correta, com uma seqüencia grande de trocas assim como o Bubble sort

O algoritmo percorre o vetor comparando seus elementos dois a dois, assim que ele encontra um elemento que está na posição incorreta, ou seja, um número maior antes de um menor, ele troca a posição dos elementos, e volta com este elemento até que encontre o seu respectivo lugar.

Características

Complexidade de tempo: Θ(n²)

Implementações

Código em Python

# coding: utf-8

def gnome(lista):
  pivot = 0
  lista_length = len(lista) 
  while pivot < lista_length - 1:
    if lista[pivot] > lista[pivot + 1]:
      lista[pivot + 1], lista[pivot] = lista[pivot], lista[pivot + 1]
      if pivot > 0:
        pivot -= 2
    pivot += 1

# Paulo Sérgio dos Santos Araujo
# Bacharelando em Ciência da Computação - Ufcg

Código em C

# include <stdio.h>
# include <stdlib.h>
# include <ctype.h>
# include <string.h>
# include <stdbool.h>

# define MAX 100001

int VectorSort[MAX];
int size = 0;

void swap(int * ,int *);
void GnomeSort();

int main (void){
 while(scanf("%d",&VectorSort[size]),VectorSort[size] >= 1)
 size++;

 GnomeSort();

 return 0;
}

void swap(int *A, int *B){
 int C = *A;
* A = *B;
* B = C;
}

void GnomeSort(){
 int next = 0, previous = 0;
 int i = 0;

 for(i = 0; i < size ; i++) {
 if(VectorSort[i] > VectorSort[i + 1]) {
  previous = i;
  next = i + 1;
  while(VectorSort[previous] > VectorSort[next])  {
 swap(&VectorSort[previous],&VectorSort[next]);
 if(previous > 0)
    previous--;
 if(next > 0) 
    next--;
  }
 }
 }

 for(i = 0; i < size; i++) printf("%d\n",VectorSort[i]);
}

Código em C++ versão 1

template<class T>
void gnome_sort( std::vector<T> &lista )
{
  std::vector<T>::size_type i = 1;

  while( i < lista.size() )
  {
    if( i == 0 || lista.at( i-1 ) <= lista.at( i ) )
    {
      i++;
    }
    else
    {
      std::swap( lista[ i - 1 ], lista [ i ] );
      --i;
    }
  }
}

Código em C++ versão 2

template<class T>
void gnome_sort( std::vector<T> &lista )
{
  std::vector<T>::iterator elem = lista.begin()+1;

  while( elem != lista.end() )
  {
    if( elem == lista.begin() || *(elem-1) <= *elem )
    {
      ++elem;
    }
    else
    {
      std::iter_swap( elem-1, elem );
      --elem;
    }
  }
}

Código em Java

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
* Implementa e executa o algoritmo Gnome Sort
*
* @author Dielson Sales, Marcos Paulo J. Melo Silva
*/
public class GnomeSort<E extends Comparable<? super E>> {

    /**
* Ordena uma coleção de dados comparáveis usando o Gnome Sort.
* @param vector uma lista de dados comparáveis
* @return uma lista com os dados ordenados
*/
    public Collection<E> sort(Collection<E> vector) {

        int i = 1;
        List<E> result = new ArrayList<E>(vector);

        while (i < result.size()) {

            if (i == 0 || result.get(i - 1).compareTo(result.get(i))<= 0) {
                i++;
            } else {
                E temp = result.get(i - 1);

                result.set(i - 1, result.get(i));

                result.set(i, temp);
                i--;
            }
        }

        return result;
    }

    /**
* Execução do algoritmo de ordenação Gnome Sort.
*/
    public static void main(String[] args) {

        GnomeSort<Integer> gnomeSort = new GnomeSort<Integer>();

        final int size = 50;

        final Random random = new Random();

        List<Integer> list = new ArrayList<Integer>(size);

        for (int i = 0; i < size; i++) {
            list.add(random.nextInt());
        }

        // Lista com os dados já ordenados.
        Set<Integer> sortedList = new HashSet<Integer>(gnomeSort.sort(list));
    }
}

/**
* Exemplo de código em Java
* Autores: Marcos Paulo J. de Melo Silva e Dielson Sales de Carvalho;
* Instituição: Universidade Federal de Alagoas (UFAL);
*/

Código em Java

/*
* Autor: Felipe da Silva Travassos
* Graduando em Ciência da Computação - UFCG
*/
public static Integer[] gnomeSort(Integer[] array){
  int pivout = 0;
  int aux;
  while(pivout<(array.length-1)){
    if(array[pivout]>array[pivout+1]){
      aux = array[pivout];
      array[pivout] = array[pivout+1];
      array[pivout+1] = aux;
      if(pivout>0){
        pivout-=2;
      }
    }
    pivout++;
  }
  return array;
}

Código em C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace gnome_sort
{
    class Program
    {
        static void Main(string[] args)
        {
            int men = 1;
            int[] vetor = new int[19];
            Random r = new Random(50);
            while (men != 0)
            {
                Menu();
                ImprimeVetor(vetor);
                Console.WriteLine();
                Console.WriteLine("Opcao:");
                men = int.Parse(Console.ReadLine());
                CaseMenu(men, vetor, r);
                Console.Clear();
            }
        }
        /* Case do Menu */
        private static void CaseMenu(int men, int[] vetor, Random r)
        {
            switch (men)
            {
                case 1: NovoVetor(vetor, r);
                    break;
                case 2: GnomeSort(vetor);
                    break;
                case 0: break;
                default: Console.WriteLine("INVALIDO! Digite 1 ou 2");
                    break;
            }
        }
        /* Imprime o Vetor */
        private static void ImprimeVetor(int[] vetor)
        {
            foreach (var item in vetor)
            {
                Console.Write(item);
                Console.Write(" ");
            }
        }

        /* Gera os os números aleatórios no vetor */
        private static void NovoVetor(int[] vetor, Random r)
        {
            for (int i = 0; i < vetor.Length; i++)
            {
                vetor[i] = r.Next(1, 100);
            }
        }

        /* Menu do programa */
        static void Menu()
        {
            Console.WriteLine("***************** MENU *******************");
            Console.WriteLine("                                          ");
            Console.WriteLine("1 - Gerar um conjunto de números aleatório");
            Console.WriteLine("2 - Utilizar o algoritmo para a ordenação ");
            Console.WriteLine("                                          ");
            Console.WriteLine("0 - Sair                                  ");
            Console.WriteLine("******************************************");
        }

        /* Algoritmo de Ordenação */
        static void GnomeSort( int[] array )
        {
            for ( int i = 1, temp_value; i < array.Length; )
            {
                if ( array[i-1] <= array[i] )
                i += 1;
                else
                {
                    temp_value = array[i-1];
                    array[i-1] = array[i];
                    array[i] = temp_value;
                    i -= 1;
                    if ( i == 0 )
                    i = 1;
                }
                Console.Clear();
                Console.WriteLine("Ordenando...");
                ImprimeVetor(array);
                System.Threading.Thread.Sleep(10);
            }
        }
    }
}

Código de um programa em C#. Gera números aleatórios e ordena com o Gnome Sort
Autor: Marcos Latchuk
Universidade: UNICENTRO      Guarapuava - Pr

Código em PHP

function gnomeSort($arr){
	$i = 1;
	$j = 2;
	while($i < count($arr)){
		if ($arr[$i-1] <= $arr[$i]){
			$i = $j;
			$j++;
		}else{
			list($arr[$i],$arr[$i-1]) = array($arr[$i-1],$arr[$i]);
			$i--;
			if($i == 0){
				$i = $j;
				$j++;
			}
		}
	}
	return $arr;
}
$arr = array(3,1,6,2,9,4,7,8,5);
echo implode(',',gnomeSort($arr));

Código em Fortran:

program example
 
  implicit none
 
  integer :: array(8) = (/ 2, 8, 6, 1, 3, 5, 4, 7 /)
 
  call Gnomesort(array)
  write(*,*) array
 
contains
 
subroutine Gnomesort(a)
 
  integer, intent(in out) :: a(:)
  integer :: i, j, temp
 
  i = 2
  j = 3
  do while (i <= size(a))
    if (a(i-1) <= a(i)) then
      i = j
      j = j + 1
    else
      temp = a(i-1)
      a(i-1) = a(i)
      a(i) = temp
      i = i -  1
      if (i == 1) then
        i = j
        j = j + 1
      end if
    end if
  end do
 
end subroutine Gnomesort
 
end program example

Código em Rust:

fn gnome_sort<T: PartialOrd>(a: &mut [T]) {
    let len = a.len();
    let mut i: usize = 1;
    let mut j: usize = 2;
    while i < len {
        if a[i - 1] <= a[i] {
            // for descending sort, use >= for comparison
            i = j;
            j += 1;
        } else {
            a.swap(i - 1, i);
            i -= 1;
            if i == 0 {
                i = j;
                j += 1;
            }
        }
    }
}
 
fn main() {
    let mut v = vec![10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6];
    println!("before: {:?}", v);
    gnome_sort(&mut v);
    println!("after:  {:?}", v);
}

• Portal das tecnologias de informação