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
# 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
# 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]);
}
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;
}
}
}
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;
}
}
}
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;
}
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);
}
