Per il mio progetto ho una tabella hash con bucket 1M (a volte più).
Ogni bucket contiene molti valori e vengono memorizzati ordinati in un array dinamico.
Sto cercando un modo abbastanza semplice per memorizzare tutti i valori in un file (anche printf lo farà), ma in modo ordinato.
C'è un modo per farlo in meno complessità N * N (ad esempio unendo tutti gli array / bucket 1M)
Credo che la seconda metà dell'algoritmo del mergesort sia ciò che stai cercando, dal momento che la prima metà sta dividendo i numeri in subranges, e la seconda metà sta unendo quei subranges. Il Mergesort nel suo complesso ha una complessità di O (n log n), e credo che anche la seconda metà di per sé sarebbe O (n log n).
Per iniziare, ecco un'implementazione ragionevolmente breve e leggibile di mergesort in C, tratta da link
#include<stdio.h>
#define MAX 50
void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);
int main(){
int merge[MAX],i,n;
printf("Enter the total number of elements: ");
scanf("%d",&n);
printf("Enter the elements which to be sort: ");
for(i=0;i<n;i++){
scanf("%d",&merge[i]);
}
partition(merge,0,n-1);
printf("After merge sorting elements are: ");
for(i=0;i<n;i++){
printf("%d ",merge[i]);
}
return 0;
}
void partition(int arr[],int low,int high){
int mid;
if(low<high){
mid=(low+high)/2;
partition(arr,low,mid);
partition(arr,mid+1,high);
mergeSort(arr,low,mid,high);
}
}
void mergeSort(int arr[],int low,int mid,int high){
int i,m,k,l,temp[MAX];
l=low;
i=low;
m=mid+1;
while((l<=mid)&&(m<=high)){
if(arr[l]<=arr[m]){
temp[i]=arr[l];
l++;
}
else{
temp[i]=arr[m];
m++;
}
i++;
}
if(l>mid){
for(k=m;k<=high;k++){
temp[i]=arr[k];
i++;
}
}
else{
for(k=l;k<=mid;k++){
temp[i]=arr[k];
i++;
}
}
for(k=low;k<=high;k++){
arr[k]=temp[k];
}
}
Output di esempio:
Enter the total number of elements: 5
Enter the elements which to be sort: 2 5 0 9 1
After merge sorting elements are: 0 1 2 5 9
Si noti che il suggerimento di ratchet freak è fondamentalmente l'algoritmo di heapsort, che è anche O (n log n), in modo che anche uno vada bene.
Puoi creare un min-heap in cui archiviare tutti i bucket ordinati per il primo elemento.
Quindi fai un pop di un elemento dal primo bucket e ri-heapify.
Se non ti è permesso cambiare i bucket, tieni un indice per bucket di quale elemento deve ancora essere estratto da esso.
Da quello che hai scritto, non vedo una ragione per cui debbano essere usate le informazioni originali sull'hashtable e sui bucket - solo un eccesso di complessità delle cose.
Quindi appiattisci tutti i bucket in una lista (complessità O (N)) e applica un algoritmo di ordinamento arbitrario con complessità O (N * log (N)), ad esempio, ordinamento rapido o ordinamento di unione. Quindi scrivi i risultati in un file.