Dzień dobry! Ostatnio obudziłem się z pewnym pomysłem na algorytm sortujący. Ciekaw jestem czy ktoś z was spotkał się z czymś podobnym i czy w ogóle może mieć to jakieś zastosowanie.
Z moich testów wynikło, że przy większej ilości liczb do posortowania, działa szybciej niż quick sort. Aktualnie program ma zakres od 1 do "dowolnej liczby" (w odpowiednim zakresie dla zmiennej oczywiście). Myślę, że można by również dodać liczby ujemne, ale nie o to chodzi. Niestety nie da się sortować liczb zmienno-przecinkowych.
Zasada programu jest banalnie prosta:
- Program pobiera dane wejściowe i losuje liczby do posortowania,
- Algorytm tworzy drugą tabelkę i wpisuje do danej komórki ilość występowania konkretnej liczby,
- później wypisuje w kolejności do tabelki pierwotnej liczby.
Kod algorytmu:
(*tab- tabela zawierająca nieposortowane dane, n- liczba liczb z- maksymalny zakres)
void sortowanie (int *tab, int n, int z)
{
//inicjowanie tablicy do zapisu ilosci liczb
int *wew_tab;
wew_tab = new int [z+1] {0};
//wpisanie wartosci do tablicy
for (int i=0; i<n; i++)
{
wew_tab[tab[i]]+=1;
}
//zapis posortowanych danych do tablicy glownej
int j=0;
for (int i=0; i<z;i++)
{
if (wew_tab[i]>0)
{
tab[j]=i;
wew_tab[i]-=1;
j++;
i--;
z++;
}
//koniec dzialania algorytmu po osiagnieciu max
if (j==n)
{
break;
}
}
delete [] wew_tab;
}
Przykładowy wynik:
Kod programu porównującego algorytm do quick sorta:
#include <iostream>
#include <time.h>
#include <windows.h>
using namespace std;
int ile, zakres;
clock_t start,stop;
double czas;
void sortowanie (int *tab, int n, int z);
void quicksort(int *tablica, int lewy, int prawy);
int main()
{
cout<<"Ile losowych liczb w tablicy: ";
cin>>ile;
cout<<"Jaki ma byc maksymalny zakres losowania liczb. 1-";
cin>>zakres;
//dynamiczne alokowanie pamieci
int *tablica;
tablica=new int [ile];
int *tablica_q;
tablica_q=new int [ile];
//inicjowanie generatora
srand(time(NULL));
//wczytywanie losowych liczb do tablicy
for(int i=0; i<ile; i++)
{
tablica[i] = rand()%zakres+1;
tablica_q[i] = tablica[i]; //przepisywanie tablicy do tablicy q
}
/* cout<<"\nPrzed posortowaniem: "<<endl;
for(int i=0; i<ile; i++)
{
cout<<tablica[i]<<" ";
}
*/
cout<<"\n\nSortuje teraz 'tab sort'. Prosze czekac!";
start = clock();
sortowanie(tablica,ile,zakres);
stop = clock();
czas = (double)(stop-start) / CLOCKS_PER_SEC;
cout<<endl<<"Czas sortowania 'tab sort': "<<czas<<" s"<<endl;
cout<<endl<<"Sortuje teraz algorytmem quicksort. Prosze czekac!";
start = clock();
quicksort(tablica_q, 0, ile-1);
stop = clock();
czas = (double)(stop-start) / CLOCKS_PER_SEC;
cout<<endl<<"Czas sortowania quicksort: "<<czas<<" s"<<endl;
/* cout<<"\nPo posortowaniu tab sort: "<<endl;
for(int i=0; i<ile; i++)
{
cout<<tablica[i]<<" ";
}
cout<<"\nPo posortowaniu quick sort: "<<endl;
for(int i=0; i<ile; i++)
{
cout<<tablica_q[i]<<" ";
}
*/
cout<<endl;
delete [] tablica;
delete [] tablica_q;
return 0;
}
void sortowanie (int *tab, int n, int z)
{
//inicjowanie tablicy do zapisu ilosci liczb
int *wew_tab;
wew_tab = new int [z+1] {0};
//wpisanie wartosci do tablicy
for (int i=0; i<n; i++)
{
wew_tab[tab[i]]+=1;
}
//zapis posortowanych danych do tablicy glownej
int j=0;
for (int i=0; i<z;i++)
{
if (wew_tab[i]>0)
{
tab[j]=i;
wew_tab[i]-=1;
j++;
i--;
z++;
}
//koniec dzialania algorytmu po osiagnieciu max
if (j==n)
{
break;
}
}
delete [] wew_tab;
}
void quicksort(int *tablica, int lewy, int prawy)
{
int v=tablica[(lewy+prawy)/2];
int i,j,x;
i=lewy;
j=prawy;
do
{
while(tablica[i]<v) i++;
while(tablica[j]>v) j--;
if(i<=j)
{
x=tablica[i];
tablica[i]=tablica[j];
tablica[j]=x;
i++;
j--;
}
}
while(i<=j);
if(j>lewy) quicksort(tablica,lewy, j);
if(i<prawy) quicksort(tablica, i, prawy);
}
