C++ :: Radix Sort Not Working - Implementation Using Two Tables
Jun 13, 2014
I'm trying ultimately to do a radix sort. I'm going with the implementation using two tables. One will initially hold the unsorted values then hold the partially sorted values thereafter. The other will be an array of linked lists which will be where the radix sort is done. Here is my code thus far:
Main
#include <iostream>
#include <fstream>
#include "radix.h"
#include "radix.cpp"
using namespace std ;
int main ( int argc , char * argv [ ] ) {
ifstream input ( argv [ 1 ] ) ;
[Code] ....
It appears to be crashing during void insert_into_sorted ( int to_insert , int place ) ; and I'm not sure why.
View 2 Replies
ADVERTISEMENT
May 11, 2014
I'm having trouble implementing my radix sort program on the main .cpp file. Here is what the radix header file looks like::
#include <vector>
#include <queue>
using namespace std;
void distribute(const vector<int> &v, queue<int> digitQueue[], int pwr) {
int i;
for(int i=0; i < v.size(); i++)
digitQueue[(v[i]/pwr) % 10].push(v[i]);
[Code] .....
Here is what my main looks like:
#include <iostream>
#include <cstdlib>
#include <vector>
#include <queue>
#include "radix.h"
[Code] ....
My output:
sorted array is:
0 0 0 0 0 0 0 0 0 0
View 1 Replies
View Related
Aug 19, 2013
Example radix sort function to sort an array of 64 bit unsigned integers. To allow for variable bin sizes, the array is scanned one time to create a matrix of 8 histograms of 256 counts each, corresponding to the number of instances of each possible 8 bit value in the 8 bytes of each integer, and the histograms are then converted into indices by summing the histograms counts. Then a radix sort is performed using the matrix of indices, post incrementing each index as it is used.
Code:
typedef unsigned long long UI64;
typedef unsigned long long *PUI64;
PUI64 RadixSort(PUI64 pData, PUI64 pTemp, size_t count) {
size_t mIndex[8][256] = {0};
/* index matrix */
PUI64 pDst, pSrc, pTmp;
size_t i,j,m,n;
UI64 u;
[Code]....
View 9 Replies
View Related
Apr 10, 2013
why we use radix sort.
View 2 Replies
View Related
Sep 2, 2013
I was just going through Radix Sort algorithm. Though I got the logic and the concept used in it, I am still pretty much confused about the space complexity being O(k+n) for this algorithm. (where, k is the max no of digits in a number, and n is the no. of inputs to be sorted).
View 1 Replies
View Related
Apr 12, 2014
I'm attempting to build a column based database, and I'm new to C++ (just wanted to play around with building a column base database "for the fun of it"). I want to construct a very fast radix sort, that would allow me to quickly sort groups of columns based on integer values. My general preference is to take up more RAM to get more performance.
I'd like to build the radix sort by allowing 256 "buckets" to drop values in as I'm sorting. This allows me to sort through a group of 4 byte integers in only 4 passes. But assuming I'm trying to sort a large group of values (say 50+ million), I'm not sure what type of container to use for these. Also note I'm pretty unfamiliar with the "standard library", so below are my thoughts:
Vectors:
-Pros: Easy to use, and very fast for sequential and random access inserts / reads
-Cons: If they have to dynamically resize because a given vector wasn't large enough, this can apparently really slow performance. Unless I make another pass over the numbers before I start sorting, I wouldn't know how big to make individual the individual vectors. This means I either have to make them "too big" and waste space, or pay a performance price for either resizing, or scanning data first.
Lists:
-Pros: Seems like I wouldn't have to specify size ahead of time, so I could just easily insert values to a given list. Also, since I don't need random access reads (I'll ready the "0" list sequentially, then the "1" list, etc. they should work fine.
-Cons: I don't really know much about lists, but I'm not sure how easy it is to append a new value to the end of a list. I've read that standard library lists include both "forward" and "backward" pointers, which I don't need. Also, I find it hard to believe that there isn't some time taken up with memory allocation. If I build a list and append x million records in it, is it calling memory allocation routines x million times?
Or maybe there's another container type I should learn?
Again, my goal is to make this "fast", not "memory efficient". But having said that, the fastest way I could think of (use 256 vectors, each sized equal to the total number of members to be sorted) is just too much memory to burn - 256 times a vector big enough to hold millions of elements is too much.
View 4 Replies
View Related
Dec 18, 2014
I am creating 5 different tables each one has 20000 more elements more than the previous when i try to sort them with the sort algorithm quick sort for the first table tha has 20000 elements runs grate then it throws this exception how is this fixable ?
Exception : terminate called after throwing an instanceof 'std::bad_alloc' this application has Requested the Runtime to terminate it in an unusual way. Please contact the applications's support team for more information. Process returned 255(0xFF) . here is the code that gives this return :
Code:
#include<time.h>
#include<stdlib.h>
#include <string.h>
#include <ctime>
using namespace std;
int * Create_Table(int table[],int N);
[Code] .....
View 10 Replies
View Related
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;
[code].....
View 5 Replies
View Related
Jun 20, 2014
I am having trouble sorting out a list of names in c. I have code for sorting the names, but when I go to print them out they still are in the same order as they were at the beginning so something isnt right. So the function that I need is the sort_data function.
Code:
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_STRING_LEN 25
void insert_data(char **strings, const char* filename, int size);
void allocate(char ***strings, int size);
[Code] ....
The list that I am reading in is as follows:
matt
susan
mark
david
aden
phil
erik
john
caden
mycah
So I need to get this list in alphabetical order, but when I run my code and print out this list after I run the sort function, they are still in this order.
View 5 Replies
View Related
Apr 9, 2015
I am trying to sort an array of strings but when I pass it through my bubbleSort function, it gives me a segmentation fault. By print checking, I know that there are strings in the array "f" but it doesn't get sorted.
Note: The file I am putting into this program is a text file with 1000 lines
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
[Code].....
View 1 Replies
View Related
Feb 11, 2015
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
class Player {
private:
char name[20];
int score;
[Code] .....
View 5 Replies
View Related
Jun 3, 2013
For my homework I need to create a hash table with a size of 7. I also need to create a queue that holds 3 names maximum for each table position
View 1 Replies
View Related
Mar 7, 2014
I need to run some basic statistics on about ~150 tables that are currently in dBase format. Rather than use excel to do them all individually, i was told to use s+ and write a code to loop through them, but I have never written any code and my experience with spotfire s+ is limited (the stat software i have available) ....
View 4 Replies
View Related
May 23, 2014
In my code I have lots of structures. I try to make tables of structures and then get access to elements of the structures to use them all along my code: here is an example to clarify things
typedef struct {
Fabric **closfabric;
}Network;
Net is part of another structure called Switch and Fabric itself is a composed structure. I have done the following
aSwitch->net.closfabric = (Fabric **)malloc(3* sizeof(Fabric *));
aSwitch->net.closfabric[0] = (Fabric *)malloc(m * sizeof(Fabric ));
aSwitch->net.closfabric[1] = (Fabric *)malloc(k * sizeof(Fabric ));
aSwitch->net.closfabric[2] = (Fabric *)malloc(m * sizeof(Fabric ));
The compilation returns a segmentation fault because aSwitch->net.closfabric is NULL (0) .
Surprisingly, in other codes the same analogy of using tables made of double pointers works perfectly with no problems and I have no problem of core dumped and NULL pointers.
Why am I getting this problem. It is the case whenever I try to use large dimension tables (tab *** struct for example)...
View 2 Replies
View Related
Feb 8, 2014
I have to write a program to display multiplication tables. I have written the following code:
Code:
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
[Code] ....
View 2 Replies
View Related
Jul 23, 2014
i'm trying to update multiple table values with same column using one query.
Here's what i've tried so far:
mySql.CommandText = "Update tbl_employees,tbl_emp_additional_info,tbl_allocated_deductions,tbl_benefits,
tbl_cashadvances,tbl_deduction_history,"+
"tbl_dtr,tbl_empabsences,tbl_empstatus,tbl_otherdeductions
,tbl_ots,tbl_payroll_history,tbl_rdcomments,tbl_reversed_deductions,tbl_reversed_deduction_paid "+
"set tbl_employees.emp_id=@newemp_id,tbl_emp_additional_info.emp_id=@newemp_id,tbl_allocated_deductions.
[code]...
I've also tried removing all the other "and" operators but still no luck.It doesn't throw in exception yet it doesn't update my tables column values.
View 14 Replies
View Related
Dec 17, 2013
Currently I have to manually look up values on several different tables in different locations. I have 8 or 10 tables with 100 to 500 parts.
I would like to write a program so if I enter a value it will return the corresponding correct answers from the tables.
If I entered 2.5 for a value it would return the following three items from the tables since they all meet the requirement.
Table 2
Part min max
235 2.4 2.9
Table 6
Part min max
589 2.3 2.5
Table 7
Part min max
12 2.3 2.7
What would the best method be for setting up and accessing tables like this? Is C++ good at representing something like this or should I be looking at a different language?
View 3 Replies
View Related
Dec 5, 2014
i have stuck in a join and i cant figure out where the problem is, i have those tables
public class Themes
{
[PrimaryKey, AutoIncrement]
public int Id { get; set; }
[Code].....
View 12 Replies
View Related
Nov 10, 2014
The problem is that the data table doesn't show at all. Here is the code:
<%@ Page Title="" Language="C#" MasterPageFile="~/LB/MasterPage.master" AutoEventWireup="true" CodeFile="InsertedInfo.aspx.cs" Inherits="LB_InsertedInfo" %>
<asp:Content ID="Content1" ContentPlaceHolderID="head" Runat="Server">
[Code]....
View 5 Replies
View Related
May 8, 2014
Basically I have a few tables in my Database.
So I have one table that is like so:
Item_ID, Name, Parent ID.
1 , jeff , 5
and another table like this:
Parent_ID, parent_Name
5,jackson
What I would like to happen, when I run my code is that I'll get the following
Item_ID, Name, parent_Name
1 , jeff , jackson
DataSet DS = new DataSet();
if (this.OpenConnection() == true) {
mySqlDataAdapter = new MySqlDataAdapter("select Item_ID, NAME, Parent_ID from table1, table2", connection);
mySqlDataAdapter.Fill(DS);
dataGridView1.DataSource = DS.Tables[0];
//close connection
this.CloseConnection();
}
So this spit out parent ID = 5.
I've not worked with Dataset before and I was just wondering what is the best approach? Can this be done via a SQL command or will I have to replace the value(5) with the string(jackson) using a large IF loop to search and replace.
View 1 Replies
View Related
Aug 14, 2012
I'm having a bit of trouble with something. What I'm trying to do is create a new Access table by combining other already existing Tables.
For instance, let's consider Table1 (with columns A, B and C), Table2 (with columns A, D and E) and Table3 (with columns A, F and G), where Table1.A = Table2.A = Table3.A.
From these, I want to create a new table TableResult, with columns A, B, C, D, E, F and G, with all the data contained in them. There's one catch: I want the code to get the names of the other columns, apart from column A.
I've thought about using Union, but I need to actually create a new table by combining the previous tables.
View 11 Replies
View Related
Apr 2, 2014
i have 2 tables with primary and foreign key
Customer Details
EID - Primary Key
PurchaseDetails
PNo-Primary Key
PDate,
EID- Foreigh Key
NetAmount
Report Query written in c#
SELECT DISTINCT P.PNo, P.PDate, P.PM, P.DisAmt, P.LT, P.NT, P.EID, P.PTime, C.EName FROM PurchaseDetails AS P INNER JOIN CustomerDetails AS C ON P.EID = C.EID
In Report Automattically linked based key.
but report data not showing
View 1 Replies
View Related
Apr 25, 2014
I have downloaded this project from here -->> [URL] ....
This one works fine and it's a great commented code to understand even for beginners like myself, but it only works with one table per sheet. Once I add second table in sheet, it throws an error that something is wrong in one of the columns in my spreadsheet: It says: " Error occurs! The error message is: Cannot find column 4. "
Basically, I have this type of tables in my spreadsheet:
So I want that my program would export those two tables in a single .XML file (just read them both). And those two tables should be separated in two XML childs: the upper one should be Order-Header and the lower one - Line-Items, like this:
<ROOT>
<Order-Header>
.....
</Order-Header>
<Line-Items>
.....
</Line-Items>
</ROOT>
ConvertExcelToXML.cs:
[Code] ....
I copied all the code because I think it is the easier way to spot where to change it, to read those two tables in one spreadsheet and export them both in one XML file. How could I achieve this kind of functionality.
View 14 Replies
View Related
Apr 28, 2015
I need to show in a comboBox thats shows infor from Entity framework but i need to select a specific colum in the tables..
All in C# visual studio xaml form
So I created a var but i get and output: name of programe.NLHEntities
using (var context = new NLHEntities()) {
var blog = context.EtagesChambres
.Where(b => b.TypeChanbre == "Prive")
.FirstOrDefault();
textBox2Type.Text = Convert.ToString(blog);// i put a text box to see what the output would be..
}
View 14 Replies
View Related
Mar 22, 2013
how to sort a 1D array using function sort().but if i have a 2D array how do i sort only 1 row of it (or column)?
View 2 Replies
View Related
Feb 19, 2014
You will write a program that uses a multidimensional array having 3 rows and 8 columns and sorts each of the rows using both a bubble sort and a selection sort.
You must declare the array inside of main. You will have a for loop containing the calls to bubbleSort and selectionSort. You need to pass into function bubbleSort and selectionSort the following: 1) each column of the multidimensional array, 2) the size of the column, and 3) a particular row number of the multidimensional array to be used for printing out the "pass" shown on the following pages.
I keep getting an error that the identifier for bubbleSort and selectionSort is not found. (Error C3861) Also, I feel like I'm missing something in int main() to get it to sort properly.
# include <iostream>
using namespace std;
int main()
{
[Code].....
View 14 Replies
View Related
