Gnome Sort

Aspecte teoretice:

Gnome Sort este un algoritm de sortare propus inițial de către Dr. Hamid Sarbazi-Azad (Profesor de ingineria calculatoarelor la Sharif University of Technology) în anul 2000. Mai târziu acesta a fost descris de către Dick Grune, dându-i-se numele de Gnome Sort. Este un algoritm de sortare asemănător cu Insertion Sort, doar că etapa de mutare a unui element pe poziția corectă este însoțită de o serie de interschimbări, ca la bubble sort. În principiu, este un algoritm simplu, având complexitatea (O(n^2)), dar tinde spre O(n) dacă lista inițială este aproape sortată.

Gnome Sort este bazat pe metoda de aranjare a unor ghivece de flori a unui gnom. Acesta se uita la ghiveciul din stânga lui și la cel din dreapta lui. Dacă sunt în ordinea corecta, merge mai departe, dacă nu le schimbă și merge mai departe.

Exemplu:

Vector	Etapa
[5, 3, 2, 4]	a[pos] < a[pos-1], swap:
[3, 5, 2, 4]	a[pos] >= a[pos-1], increment pos:
[3, 5, 2, 4]	a[pos] < a[pos-1], swap and pos > 1, decrement pos:
[3, 2, 5, 4]	a[pos] < a[pos-1], swap and pos <= 1, increment pos:
[2, 3, 5, 4]	a[pos] >= a[pos-1], increment pos:
[2, 3, 5, 4]	a[pos] < a[pos-1], swap and pos > 1, decrement pos:
[2, 3, 4, 5]	a[pos] >= a[pos-1], increment pos:
[2, 3, 4, 5]	a[pos] >= a[pos-1], increment pos:
[2, 3, 4, 5]	pos == length(a), finished.

Implementare

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace GnomeSortCS
{
    class Program
    {
        public static void gnomeSort(ref int[] a, int len)
        {
            int i = 1;
            int j = 2;
            while (i < len)
            {
                if (a[i - 1] <= a[i])
                {
                    i = j;
                    j++;
                }
                else
                {
                    int tmp = a[i - 1];
                    a[i - 1] = a[i];
                    a[i--] = tmp;
                    i = (i == 0) ? j++ : i;
                }
            }
        }
 
        static void Main(string[] args)
        {
            int[] v = new int[100];
            int i;
            int len;
            Console.Write("Dati numarul de elemente din vector: ");
            len = Convert.ToInt32(Console.ReadLine());
            for (i = 0; i < len; i++)
            {
                Console.Write("v[" + i + "]=");
                v[i] = Convert.ToInt32(Console.ReadLine());
            }
            gnomeSort(ref v, len);
            for (i = 0; i < len; i++)
                Console.Write(v[i] + " ");
            Console.ReadLine();
        }
    }
}

Cod Sursa PHP

<?php

 
function gnome_Sort($my_array){
	$i = 1;
	$j = 2;
	while($i < count($my_array)){
		if ($my_array[$i-1] <= $my_array[$i]){
			$i = $j;
			$j++;
		}else{
			list($my_array[$i],$my_array[$i-1]) = array($my_array[$i-1],$my_array[$i]);
			$i--;
			if($i == 0){
				$i = $j;
				$j++;
			}
		}
	}
	return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "Vector Original :\n";
echo implode(', ',$test_array );
echo "\nVector Sortat :\n";
echo implode(', ',gnome_Sort($test_array)). PHP_EOL;
sleep(10);
?>

Rezultat