Bead Sort

Aspecte teoretice:

Algoritmul Bead Sort/Gravity Sort (Sortarea cu ajutorul mărgelelor) este un algoritm de sortare, dezvoltat de Joshua J. Arulanandham, Cristian S. Calude și Michael J. Dinneen în anul 2002, apoi publicat în ”The Bulletin of the European Association for Theoretical Computer Science”. Etapele acestui algoritm sunt următoarele:

• Etapa 1 : Mărgelele sunt suspendate pe stâlpi verticali.

• Etapa 2: Mărgelele sunt lăsate să cadă.

Operația de sortare prin metoda mărgelelor poate fi comparată cu modul în care mărgelele alunecă pe stâlpi paraleli, exact cum ar fi pe un abac. Cu toate acestea, fiecare stâlp poate avea un număr distinct de mărgele. La început, poate fi util să ne imaginăm mărgelele suspendate pe stâlpi verticali. La pasul 1, un astfel de aranjament este afișat pentru n=5 rânduri de mărgele pe m=4 stâlpi verticali. Numerele din dreapta fiecărui rând indică numărul mărgelelor de pe fiecare rând. Astfel rândurile 1 și 2 sunt reprezentate fiecare cu numărul întreg 3 (pentru că ele conțin fiecare trei mărgele), în timp ce rândul de sus este reprezentat de numărul întreg 2 (deoarece conține doar două mărgele). Dacă permitem apoi mărgelelor să cadă, vom avea apoi, aceleași numere întregi într-o ordine sortată. Rândul 1 conține cel mai mare număr din set, în timp ce rândul n conține pe cel mai mic. Acțiunea de a permite mărgelelor să cadă, a permis valorilor mai mari din rândurile superioare să se propage pe rândurile inferioare.

Mecanismul acestei metode de sortare este asemănător cu cel al metodei de sortare prin numărare (Counting Sort).

Complexitate:

Acest algoritm are particularitatea că în cazul cel mai defavorabil, are complexitatea O(nlogn), astfel având cea mai rapidă performanță posibilă pentru o sortare prin comparație, în cazul cel mai defavorabil.

Implementare:

Cod Sursa C++

// BeadSortCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
//this algorithm only works with positive, whole numbers.
//O(2n) time complexity where n is the summation of the whole list to be sorted. 
//O(3n) space complexity.
 
#include <iostream>
#include <vector>
 
using namespace std;
using std::cout;
using std::vector;
 
int v[20];
 
void distribute(int dist, vector<int> &List) 
{
	//*beads* go down into different buckets using gravity (addition).
	if (dist > List.size() )
		List.resize(dist); //resize if too big for current vector
 
	for (int i=0; i < dist; i++)
		List[i]++;
}
 
vector<int> beadSort(int *myints, int n) 
{
	vector<int> list, list2, fifth (myints, myints + n); 
	//cout << "#1 Beads falling down: ";
	for (int i=0; i < fifth.size(); i++)
		distribute (fifth[i], list);
	cout << '\n';
 
	//cout << "\nBeads on their sides: ";
	for (int i=0; i < list.size(); i++)
		//cout << " " << list[i];
	cout << '\n';
 
	//cout << "#2 Beads right side up: ";
	for (int i=0; i < list.size(); i++)
		distribute (list[i], list2);
	cout << '\n';
 
	return list2;
}
 
int main(void)
 {
	 int i;
	 int len;
 
	 cout<<"Dati numarul de elemente din vector: ";
	 cin>>len;
	 for (i=0; i<len; i++)
	 {
		 cout<<"v["<<i<<"]=";
		 cin>>v[i];
	 }
 
	 vector<int> sorted = beadSort(v, sizeof(v)/sizeof(int));
	 cout<<"vectorul sortat este: ";
	 for (i=0; i<sorted.size(); i++)
	 cout<<sorted[i]<<" ";
	 system("pause");
 }

 

Cod Sursa PHP

<?php

 
function columns($my_array) {
    if (count($my_array) == 0)
        return array();
    else if (count($my_array) == 1)
        return array_chunk($my_array[0], 1);
    
    array_unshift($my_array, NULL);
    // array_map(NULL, $my_array[0], $my_array[1], ...)
    $transpose = call_user_func_array('array_map', $my_array);
    return array_map('array_filter', $transpose);
}
 
function bead_sort($my_array) {
    foreach ($my_array as $e)
        $poles []= array_fill(0, $e, 1);
    return array_map('count', columns(columns($poles)));
}
 
 
$test_array = array(3, 2, 5, 4, 1, 100);
echo "\nVector Original: \n";
echo implode(', ',$test_array );
echo "\nVector Sortat: \n";
echo implode(', ',bead_sort($test_array)). PHP_EOL;
sleep(10);
?>

Rezultat: