Algoritmo similiar ao Insertion sort com a diferença que o Gnome sort leva um elemento para sua posição correta, com uma sequência 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; 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); }
Categoria:Algoritmos de ordenação