Fusion de tri de la mise en œuvre
Je suis novice en c++ et a essayé de développer un code pour la fusion et le tri. Je l'ai testé avec un exemple de tableau de taille 5 mais la réponse donnée par le code n'est pas bon. Je ne peux pas comprendre ce qui ne va pas. Voici mon code:
#include <iostream>
#include <cstring>
#include <sstream>
#include <fstream>
#include <iomanip>
using namespace std;
void merge(int, int, int, int*);
void merge_sort(int low, int high, int* p){
int pivot;
static int i(1);
if (high>low)
{
cout << "calling merge_sort: "<<i<<endl; i++;
pivot = low + ((high - low)/2);
cout << pivot << endl;
merge_sort(low, pivot, p);
merge_sort(pivot+1, high, p);
merge(low, pivot, high, p);
}
}
void merge(int l, int pi, int h,int* arr)
{
int start = l;
int mid = pi+1;
while((start<=pi)&&(mid <=h)){
if (arr[start] > arr[mid])
{
int temp = arr[mid];
arr[mid] = arr[start];
arr[start] = temp;
mid++;
}
else
start++;
}
}
int main()
{
int a[] = {2, 42, 3, 7, 1};
merge_sort(0, 4, a);
for (int i = 0; i<=4 ; i++)
cout << a[i] << endl;
return (0);
}
La sortie est comme suit:
calling merge_sort: 1
2
calling merge_sort: 2
1
calling merge_sort: 3
0
calling merge_sort: 4
3
1
3
7
2
42
J'ai vu certains codes de fusion de tri de la mise en œuvre sur stackoverflow mais ils utilisent un autre tableau temporaire, que je veux éviter.
Toute aide est grandement appréciée dans le tri de ce problème.
Si vous avez besoin d'une information sur les lieu de fusion et de mise en œuvre - stackoverflow.com/questions/2571049/...
OriginalL'auteur akash_c | 2013-08-09
Vous devez vous connecter pour publier un commentaire.
La logique dans votre fusion est faux. Lors de la fusion de la phase vous savez que vous avez 2 sections de tri des nombres. Lorsque vous comparez et swap
arr[start]
etarr[mid]
vous cassez le tri des meilleurs jeu de nombres siarr[start] > arr[mid+1]
. L'exemple montre un problème avec votre code 2 sera laissé au mauvais endroit:Afin de garder les 2 articles triée vous devez insérer
arr[start]
à la bonne place dans le top un ensemble de nombres qui ferait de la complexité de pire que deO(n lg n)
. C'est la raison pour laquelle un deuxième tableau est utilisé.Il y a la méthode qui utilisent des petits tableaux que l'original pour la fusion, ceux-ci ont leurs frais généraux, mais ne pas compromettre la complexité (ou de l'exactitude). Si vous souhaitez un
O(n lg n)
en place de tri puis quicksort ou heapsort est le chemin à parcourir.OriginalL'auteur DrYap
Ici est une mise en œuvre de la fusion de tri pour l'entier des tableaux:
Et si vous voulez l'utiliser pour d'autres types, vous pouvez l'utiliser en c++ modèles comme ceci:
Mais avec:
De sortie:
Espère que j'ai aidé un peu.
OriginalL'auteur Mr.Queries
Ces lignes semblent mal pour moi:
Pour la permutation de deux indices, que les deux doivent correspondre.
arr[mid]
au lieu dearr[mid-1]
je vais corriger le code de mon poste et de la version révisée de la sortie.Donc, maintenant vous avez un différent, mais toujours tort de sortie 🙂
Je vais essayer les suggestions posté ci-dessus.
OriginalL'auteur j4nSolo
Cette une a PARFAITEMENT fonctionné dans codeblocks (compilateur utilisé : mingw)
et pourquoi il devrait avoir une valeur constante ?
C++ a une certaine différence avec C. vous ne pouvez pas utiliser un tableau avant de définir la matrice en argument const. tester votre code en visual studio et de voir l'erreur.
N'ai-je pas déjà mentionné le fait que ce code fonctionne "parfaitement" dans codeblocks. Vous pouvez apporter des modifications si vous le souhaitez et de les rendre compatibles dans visual studio.
OriginalL'auteur harindersingh