RSS Forums RSS
Please support our C++ advertiser: Programming Forums
Views: 1127 | Replies: 6
Reply
Join Date: Oct 2007
Posts: 5
Reputation: Malaisary is an unknown quantity at this point 
Rep Power: 0
Solved Threads: 0
Malaisary Malaisary is offline Offline
Newbie Poster

Question counting sort algorithm for 2 dim array

  #1  
Oct 28th, 2007
Hello,
I want to sort a 2dim array by columns, but there is an error in my code. It doesn't accept value of element from 2dim array into C[x]. Can anybody help please?
  1. static int counting_sortx( int** A[], int** B[], int k, int rows, int col){
  2. /*Array A[ ] stores the initial data to be sorted.
  3.   Array B[ ] is used to store the final, sorted, list.
  4.   Array C[ ] is used to count the occurrences of the data values
  5. */
  6. int i,j,C[k], T[rows];
  7. //The first for loop initialises C[] to zero.
  8. for (i=0; i<k; i++)
  9. C[i] = 0;
  10. //The second for loop increments the values in C[], according to their
  11. //frequencies in the data.
  12. for (j = 0; j < rows; j++)
  13. int x=[j][col];
  14. C[x] = C[x] + 1;
  15. //The third for loop adds all previous values, making C[] contain a cumulative
  16. //total.
  17. for (i = 1; i < k; i++)
  18. C[i] = C[i] + C[i-1];
  19. //The fourth for loop writes out the sorted data into array B[].
  20. for (j = 0; j < rows; j++){
  21. B[C[A[j][col]]] = A[j][col];
  22. C[A[j][col]] = C[A[j][col]] - 1;}
  23. return 0;
  24. };
AddThis Social Bookmark Button
Reply With Quote  
Join Date: Dec 2005
Posts: 3,894
Reputation: Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of 
Rep Power: 23
Solved Threads: 442
Colleague
Salem's Avatar
Salem Salem is offline Offline
Senior Poster

Re: counting sort algorithm for 2 dim array

  #2  
Oct 28th, 2007
What kind of arrays are you passing to the function to begin with?

I'm pretty sure your A and B parameters will need to be modified.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Reply With Quote  
Join Date: Oct 2007
Posts: 5
Reputation: Malaisary is an unknown quantity at this point 
Rep Power: 0
Solved Threads: 0
Malaisary Malaisary is offline Offline
Newbie Poster

Re: counting sort algorithm for 2 dim array

  #3  
Oct 28th, 2007
Originally Posted by Salem View Post
What kind of arrays are you passing to the function to begin with?

I'm pretty sure your A and B parameters will need to be modified.

I am passing dynamically allocated arrays:
  1. //create an array
  2. int** ARR = new int*[data_rows];
  3. int** A = new int*[data_rows];
  4. int** B = new int*[data_rows];
  5. for(i=0;i<data_rows;i++){
  6. ARR[i]=new int[data_columns];
  7. A[i]=new int[data_columns];
  8. B[i]=new int[data_columns];
  9. }
  10. //then
  11. while (j<data_columns) {
  12. for (i=0; i<data_rows; i++){
  13. A[i][data_columns]=ARR[i][data_columns];
  14. }
  15. k=fRow[data_columns]+1; //give k a value of max element in current column
  16. counting_sort::counting_sortx(ARR, B, k, data_rows, data_columns);
  17. };
Last edited by WaltP : Oct 28th, 2007 at 5:26 pm. Reason: Fixed code tags -- use the PREVIEW button
Reply With Quote  
Join Date: Dec 2005
Posts: 3,894
Reputation: Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of 
Rep Power: 23
Solved Threads: 442
Colleague
Salem's Avatar
Salem Salem is offline Offline
Senior Poster

Re: counting sort algorithm for 2 dim array

  #4  
Oct 28th, 2007
Then drop the [] from your function prototype, like so

static int counting_sortx( int** A, int** B, int k, int rows, int col)

Use "post preview" to make sure you've got the code tags right before pressing submit.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Reply With Quote  
Join Date: Oct 2007
Posts: 5
Reputation: Malaisary is an unknown quantity at this point 
Rep Power: 0
Solved Threads: 0
Malaisary Malaisary is offline Offline
Newbie Poster

Re: counting sort algorithm for 2 dim array

  #5  
Oct 30th, 2007
Hello,
I found that last loop has some problem, but couldn't figure out what exactly. I am trying this:
  1. for (int i=0; i<rows; i++)
  2. for (int j=0; j<col; j++){
  3. B[C[A[i][col]]][col] = A[i][col];
  4. C[A[i][col]] = C[A[i][col]] - 1;
  5. }
What is wrong here?
Reply With Quote  
Join Date: Dec 2005
Posts: 3,894
Reputation: Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of Salem has much to be proud of 
Rep Power: 23
Solved Threads: 442
Colleague
Salem's Avatar
Salem Salem is offline Offline
Senior Poster

Re: counting sort algorithm for 2 dim array

  #6  
Oct 30th, 2007
Do you have a clear idea of what a "before" and "after" array is supposed to look like?

Draw out on paper what the actions of your algorithm are supposed to do, then use a debugger to single-step through your code one statement at a time. When your code and your paper disagree, then you've found a bug.

Whether that bug is in your code or on your paper is for you to decide.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Reply With Quote  
Join Date: Oct 2007
Posts: 5
Reputation: Malaisary is an unknown quantity at this point 
Rep Power: 0
Solved Threads: 0
Malaisary Malaisary is offline Offline
Newbie Poster

Re: counting sort algorithm for 2 dim array

  #7  
Oct 30th, 2007
I have it working now. The only thing is hard for me, in step 4, it doesn't print all rows' values, only sorted column's values. I've tried to play with col instead of scol in B[][] and A[][], but it doesn't work.
  1. //scol - column by which I sort, col - total number of colums
  2. for (int j=0; j<rows; j++){
  3. B[(C[A[j][scol]]-1)][scol] = A[j][scol];
  4. C[A[j][scol]] = C[A[j][scol]] - 1;
  5. }
I am printing array A[][] from counting_sort file:
4 2 3 3
2 1 1 4
1 7 1 2
7 1 10 1
8 1 8 2
7 1 4 3
2 1 7 1
7 2 2 3
8 4 2 2
4 9 9 1
array C[] after step 1: 0 0 0 0 0 0 0 0 0 0 0
array C[] after step 2: 0 1 2 0 2 0 0 3 2 0 0
array C[] after step 3: 1 3 3 5 5 5 8 10 10 10
array B[][] after step 4:
1 0 0 0
2 0 0 0
2 0 0 0
4 0 0 0
4 0 0 0
7 0 0 0
7 0 0 0
7 0 0 0
8 0 0 0
8 0 0 0
Last edited by Malaisary : Oct 30th, 2007 at 6:21 pm.
Reply With Quote  
Reply

Only community members can participate in forum threads. You must register or log in to contribute.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

 

Thread Tools Display Modes
Forums | Blogs | Tutorials | Code Snippets | Whitepapers | RSS Feeds | Advertising
All times are GMT -4. The time now is 4:07 pm.
Newsletter Archive - Sitemap - Privacy Statement - Acceptable Use Policy - Contact Us
Forum system based on vBulletin Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
©2003 - 2008 DaniWeb® LLC