C++ :: Merge Sort Implementation Giving Incorrect Output
Oct 25, 2014
I've implemented the merge sort algorithm and used the 'merge' part for counting the number of split-inversions in an array as part of an assignment for an online course. How ever, the out put array is not a sorted version of the input array and as a result the number of split inversions obtained is wrong. I think that there is some thing wrong in the way I am indexing arrays.
I've used ' cout ' to print the values of indexes to see exactly what values are being passed in during the recursions.
Code:
#include <iostream>
using namespace std;
int length=0,mid=0,inv=0;
void mergesort(int arr[], int first, int last) {
cout << "first: " << first << " " << "last: " << last;
cout << endl;
I have written my program and it works when I keep everything in the header files, and then have my main. I am now splitting them up into implementation files, but Eclipse keeps giving me errors. It gives me error at every opening brace of the constructor and functions. It says on all of them "Redefinition of (name of constructor or method), Previously declared here." What am I doing wrong, because it works in the header file?
I am writing a program where I read in data from a file into an array and a 2D array. However, when I cout that data to insure that it was all read in correctly, I get only the first full line of that input file(where there are actually 25 rows and 12 columns).
What am I doing wrong or should be doing differently?
ifstream fin; //open the input file fin.open("store_data.txt"); //If input file was opened, read input file data into array and 2d array if(fin){
Code: /* Mergesort: Use merge() to sort an array of size n */ #include <stdio.h> #include <stdlib.h> void mergesort(int key[], int n) { int j, k, m, *w; for (m = 1; m < n; m *= 2)
[Code] .....
Question : Modify mergesort() so that it can be used with an array of any size, not just with a size that is a power of two. Recall that any positive integer can be expressed as a sum of powers of two. For example,
27 = 16 + 8 + 2 + 1
Consider the array as a collection of subarrays of sizes that are powers of two. Sort the subarrays and then use merge() to produce the final sorted array.
I tried so many algorithms and all failed!! What i dont know is how to create subarrays ?
Were are to implement a method countValue() that counts the number of times an item occurs in a linked list. Remember to use the STL <list>
int countValue(list<int> front ,const int item);
Generate 20 random numbers in the range of 0 to 4, and insert each number in the linked list. Output the list by using a method which you would call writeLinkedList which you would add to the ListP.cpp.
In a loop, call the method countValue() , and display the number of occurrences of each value from 0 to 4 in the list.
Remember that all the above is to be included in the file ListP.ccp
I tried to keep the coding style as similar as possible. I tested these with 4 million (4x1024x1024) 64 bit unsigned integers, Visual Studio 2005, 64 bit mode, Win XP X64, Intel 2600K 3.4ghz cpu. The average time for top down = 3.7 seconds, bottom up = 3.5 seconds.
Code: // tsorttd.h - top down merge sort template <class T> T * TopDownMergeSort(T a[], T b[], size_t n) { TopDownMergeSortAtoA(a, b, 0, n);
Code: typedef vector<int> LIST; // LIST can be a vector of any comparable type static LIST merge_sort(LIST &linp){ size_t i, width; LIST lout(linp.size()); // second list for output
I'm trying to implement the Merge-Sort algorithm. I only had the pseudocode for it and have some problems coding this into C.
I have only covered pointers recently and I tried using them, which did not work. I started with the code for the merge algorithm and only used a 10 element array, which was already divided into two sorted subarrays:
Code: #include <stdio.h>#include <stdlib.h> int main() { int a[5]={1,5,6,10,13}, b[5]={4,8,9,10,14},c[10], *i,*j,k;
[Code].....
This is the result that I get:
Code: 1 4 5 6 8 9 10 10 13 0
So I think the problem occurs because in the second to last loop i is incremented again, but the end of the array is already reached, and the compiler has no element a[6] to compare with *j in the last run of the loop. Is there generally a better way to implement Merge?
// mergefile2norecreation.cpp : definisce il punto di ingresso dell'applicazione console. // // Filemerge.cpp : definisce il punto di ingresso dell'applicazione console. //
#include "stdafx.h" int _tmain(int argc, _TCHAR* argv[]) {
There is a smart way to make a merge sort between 2 file already ordered? I had try it ,and above there is my result,it works but i think that it's possible to do it in a smart way...
I am looking for a function or algorithm to best merge and sort similar content between two lists of unordered strings each in individual files (very large files ~200mb each).
For example, these files have a common first string and are merged based on them:
File 1: red, apple green, truck blue, car yellow, ball orange, candy
File 2:
gold, necklace green, tree yellow, sticker blue, water red, bag
I am looking for the following output:
Output:
red, apple, bag green, truck, tree blue, car, water yellow, ball, sticker orange, candy gold, necklace
I would like to place the first column in one array and second in another. I am using the merge sort and merge algorithm from my book to sort the first column (x-coord) in descending order and the second column (y-coord) in ascending order. The output would look like this.
I am ignoring the where(line number) for now. The error I get is: cannot convert 'points_struct*' to 'int*' for argument '1' to 'int mergesort(int*, int, int)'.
So my question is how to get my points_struct arrays to work with the algorithm I have from book. Here is what I have so far.
#include<iostream> #include<fstream> using namespace std;
My loop is outputting data incorrectly. I have inbound web data that come in sets of 7. I am trying to in insert the 7 records into a vector and then display the vector content followed by a new line.
This is in response to the bubble sort and selection sorts for linked lists. On my system, (Intel 2600K, 3.4ghz), it sorts a list with 4,194,304 nodes containing 64 bit unsigned integers in about 1.05 seconds.
Code: #define NUMLISTS 32 /* number of lists */ typedef unsigned long long UI64; typedef struct NODE_{ struct NODE_ * next; UI64 data;
I have created a program that first sorts a series of numbers that are input dynamically then an option is given to either use a sequential search or a Binary search. my sequential search works fine but the merge sort coupled with the binary search has a small bug that I just can't seem to figure how to eliminate. I first used my own merge sort but it was really in efficient so a I took a more efficient example and incorporated it in my program but I cant seem to get rid of this bug I'm dealing with. and it seems to be causing a further problem with the Binary seach.
Code: #include <iostream> #include <cmath> using namespace std; const int N = 10;
This program has to convert an unsigned binary number into a decimal number. No matter what binary number I enter, however, it always outputs that the decimal number is 0.
My code is as follows:
#include <iostream> #include <cmath> #include <algorithm> using namespace std; int main() { string binarynumber; cout << "Enter an unsigned binary number up to 32 bits." << endl;
[Code] ....
And my output:
Enter an unsigned binary number up to 32 bits. 00001111 That number in decimal is 0
The output should have shown the binary number in decimal to be 15, and I cannot find my error.
I am trying to retrieve information from a website [URL] .... and have written a C code as follows:
Code: #include <stdlib.h>#include <stdio.h> #include <string.h> #include <curl/curl.h> int main(int argc, char* argv[]) { /* Exit status to return */ int exitStatus = 0;
[Code] .....
The output of this program should be: From To 4504111 B0LPF3 4504111 P62993
The first print option [printf("%s", url)] gives the url output as [URL] .... which on being manually pasted in any web-browser gives the correct output but the program fails to give the output.
I'm trying to write a code that takes two arrays from the user (presumably in ascending order) and then passes the sizes of both arrays and a pointer to each to a separate "int* mergeArrays" function that will merge sort the two. I've written a lot of the code, but I can't get it to compile. I get errors: lab6.c: In function "main":
lab6.c:31:14: error: expected expression before "int" mergeArrays(int* firstArray, int size1, int* secondArray, int size2); ^ lab6.c:31:14: error: too few arguments to function "mergeArrays"
