Counting sort in C apparently works but binarysearch doesn't
I am looking for help regarding the implementation of a counting sort function in the CS50 Course in week 3.
An int Array has to be sorted. I tested various unsorted arrays and my counting sort function seems to sort the array just correctly, yet my search functions won't work on the sorted array after. Could someone give me a hint?
void countsort( int array[], int size) {
int count=0;
int zahl=0;
int max=65536;
int countarr [max];
int finalarr [size];
memset (countarr, 0, sizeof(countarr));
for(int i=0;i<size;i++) {
zahl=array[i];
countarr[zahl]++;
}
for(int i=0;i<max;i++) {
while(countarr[i]>0) {
finalarr[count]=i;
countarr[i];
count++;
}
}
array=finalarr;
for(int i=0;i<size;i++){
printf(" %i ",array[i]);
}
}
This is my search algorithm used after the array is sorted, it works with sort algorithms from other people.
bool binarysearch(int value, int values[], int n){
int start=0,
end=n,
mid=0,
midpos=0;
while(end>0) {
midpos=(start+end)/2;
mid=values[midpos];
if(mid==value) return true;
if(mid<value) start=++midpos;
if(mid>value) end=midpos;
}
return false;
}
1 answer

In
binarysearch
, the loop conditionwhile(end>0)
is wrong. If we search for a value which is greater than at least one of the elements of the array,end
will never be zero. Try changing it towhile(end>=start)
, which literally means that the considered interval is nonempty.In
countsort
, the linearray=finalarr;
does not copy the whole array. Instead, the local variablearray
becomes a pointer tofinalarr
. The contents of the original array remain unchanged, and the sorted array is gone when you exit the function. This explains why your binary search works (better) with other sort functions.
Try changingfinalarr[count]=i;
toarray[count]=i;
and get rid offinalarr
completely, putting the values intoarray
right away. Alternatively, you can usememmove
instead of that line.
See also questions close to this topic

C program to find the line with least characters and the one with the most in a file
So I have this big assigment for school and I'm strugling to write this little piece of code(even though I managed to write 80 % of the program).So the program has to open a file(my example is "text.txt") and find the line with the least characters and the one with the most characters in it(without \t \n and spaces).First I wrote it down for the line with the least characters and its all good but when I try to print every line with every character(just to see how it works) I get this badboi  https://pasteboard.co/GY2wLq7.jpg. Here is the program:
#include <stdio.h> #include <stdlib.h> void lineCount(); int main(){ lineCount(); return 0; } void lineCount() { FILE *fp; fp = fopen("text.txt", "r"); if (fp == NULL) { printf("Could not open file \n"); exit(1); } int lineNO = 1; int mostLine, currCount, mostCount = 0; int leastCount[512]; int c; int leastLine[512]; while (!feof(fp)) { c = getc(fp); if (c == '\n') { currCount = 0; lineNO++; leastLine[lineNO]=lineNO; } if (c != '\n' && c != '\t' && c!= ' ') { currCount++; leastCount[lineNO]=currCount; } } int i; for(i=0;i<lineNO;i++){ if(leastCount[0]>leastCount){ leastCount[0]=leastCount; leastLine[0]=leastLine; } printf("The line with the least characters is %d=%d characters\n",leastLine[i],leastCount[i]); } fclose(fp); return ; }
PS* I get the least line when I move this badboi
printf("The line with the least characters is %d=%d characters\n",leastLine[0],leastCount[0]);
under thefor
loop.The problem is that if I reverse the sign<
to>
(means if I want to get the biggest number) this strange input is failing my program to find the largest num and line.So where is my mistake? 
need to write a program that receives very long number in a weird format
I need to write a program in C which receives: a+b= (while a,b are 2 numbers that can be longer than int type or even long long type. Input example: 333333333333333333333333333+3333333333333333333333333=) and the program needs to return if the sum %3==0; So how do I do that? I mean, how do I receive such input using
scanf
? The rest is not a problem. 
Returning NULL value from a function to a pointer in C
I have a school assignment where I am supposed to create three functions. The functions are printFirstWord(), skipWords() and printWord().
Albeit not perfectly written, I have managed to make the printFirstWord function work and the other two functions mostly work fine.
However, in skipWords() I am supposed to return a pointer value of NULL if the amount of words that you wish to skip is greater than the amount of words in the string you input. This is my code:
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h> //Call the functions void printFirstWord(char inputString[]); char* skipWords(char sentence[], int words); void printWord(char sentence[], int wordNumber); int main() { printWord("I like to eat bunnies", 0); //Prints I printWord("I like to eat bunnies", 1); //Prints like printWord("I like to eat bunnies", 2); //etc printWord("I like to eat bunnies", 3); printWord("I like to eat bunnies", 4); printWord("I like to eat bunnies", 5); //This should return NULL printWord("I like to eat bunnies", 6); //This should return NULL return 0; } //Function that prints only the first word of a string void printFirstWord(char inputString[]) { int i = 0; //Removes initial nonalpha characters, if any are present while (!isalpha(inputString[i])) i++; //Checks if the next input is alphabetical or is the character '' while (inputString[i] != ' ') { printf("%c", inputString[i]); i++; } } char* skipWords(char sentence[], int words) { int i = 0, wordCount = 0; for(i = 0; wordCount < words; i++) { if(sentence[i] == ' ') { wordCount++; } } //Can't get this to work, not sure how to return NULL in a function if (words >= wordCount) return NULL; else return &sentence[i]; } void printWord(char sentence[], int wordNumber) { char *sentencePointer; sentencePointer = skipWords(sentence, wordNumber); if (sentencePointer != NULL) printFirstWord(sentencePointer); else if (sentencePointer == NULL) printf("\nError. Couldn't print the word.\n"); }
Initially my problem was that the program constantly crashed but I added the last part of the printWord function and it stopped crashing. I expect this output:
Iliketoeatbunnies Error. Couldn't print the word. Error. Couldn't print the word.
This is the output I am receiving:
Error. Couldn't print the word. Error. Couldn't print the word. Error. Couldn't print the word. Error. Couldn't print the word. Error. Couldn't print the word. Error. Couldn't print the word.
Pointers are my weak side and I feel like I have missed something crucial, I have been looking online and I haven't found any solution that fits me yet or atleast that I feel doesn't fit me.

Designing an Algorithm That Pulls Interesting Facts from a Data Set
In the book The Pragmatic Programmer they discuss an algorithm that may be useful for a sports reporter. The algorithm would pull interesting sports facts from a wide data set of baseball statistics, enabling the reporter to discuss on air only the most interesting facts provided.
This is a design I want to employ in a Java project utilizing a SQL database. What would that design look like? As well, if there is a name for this "field of study" please provide it as finding information for such a design is difficult.
Thank you

How to check if 2 numbers have same digits and length?
Following are 2 algorithms I have written to ascertain if 2 numbers have the same digits and length. They're selfexplanatory but if anything is not clear, please comment and I will add more details.
Question is this: Is there a better way to do this check ? Better in any aspect: efficiency (time and/or space), code readability, corner cases handling etc. For example, first approach has the risk of integer overflow but could be an OK approach as long as numbers are not large, because timecomplexity is linear. Appreciate the feedback.
Hash with primes:
public static boolean haveSameDigitsAndLengthPrimes(int a, int b) { int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; int hashA=1, hashB=1; while (a > 0) { hashA *= primes[a%10]; a /= 10; } while (b > 0) { hashB *= primes[b%10]; b /= 10; } return (hashA == hashB); }
Count digits approach:
public static boolean haveSameDigitsAndLength(int a, int b) { int[] digits = new int[10]; for (int i=a; i>0; i=i/10) { ++digits[i%10]; } for (int i=b; i>0; i=i/10) { digits[i%10]; } for (int digit : digits) { if (digit != 0) { return false; } } return true; }
2.b. Count digits approach: implementation improved:
public static boolean haveSameDigitsAndLength(int a, int b) { if ((a == 0  b == 0) && a != b) { return false; } int[] digits = new int[10]; int i=a, j=b; for (; i>0 && j>0; i/=10, j/=10) { ++digits[i%10]; digits[j%10]; } if (i != 0  j != 0) { return false; } for (int digit : digits) { if (digit != 0) { return false; } } return true; }
Test Cases:
 12, 12 => true
 12, 21 => true
 123, 132 => true
 123, 1234 => false
 10, 1 => false

Method for obtaining speed up on computer decision in C
I'm trying to figure out the algorithms to play Gomoku(5 by 5 version of tictactoe) with computers. In this case, I found that the most commonly used algorithms are Minmax(or Alphabeta) but these are too hard for me to handles.. So I decided to use following codes which are quite easy to understand but time consuming. It shows how a computers make its reasonable choice.
// // computer_move() checks for all legal moves in the current  // position. then for each of them it calls the dfs_search()  // function to get the moves' score. And finally it returns  // the move with the best score.  // int computer_move() // { int best_move; // best move so far int best_score = 100; // best score so far int score; // current score int i; for (i = 0; i < 16; ++i) { // if (pos[i] == EMPTY) { // if a legal move can be made pos[i] = COMPUTER; // mark the move score = dfs_search(HUMAN); // pos[i] = EMPTY; // take back the move if (score > best_score) { best_score = score; best_move = i; } } } printf("Computer's move: %d\n", best_move); return best_move; // return the best move found } // // dfs_search() gets the side to move, find all legal moves  // for him, and for each move, it recursively calls itself.  // It returns a score for the position.  // This recursive function continues on each variation until  // the game's end is found in that variation. Which means  // that the variation continues until check_result() returns  // a value other than CONTINUE.  // Note that this can be done in tictactoe, since it's a  // deterministic game. For games like chess or checkers we  // can't continue the variation until reaching the game's end  // so we have to cut the variation at some point.  // int dfs_search(int player) // { int best_score = 100; int score; int result; int i; result = check_result(player); if (result != CONTINUE) return result; // return the result for (i = 0; i < 16; ++i) { if (pos[i] == EMPTY) { pos[i] = player; score = dfs_search(CHANGE_PLAYER(player)); // pos[i] = EMPTY; if (score > best_score) best_score = score; } } return best_score; // return the best score }
For 3 by 3 matrix, it works pretty well. For 4 by 4, however, it takes too long to leave a next stone. Since the reason of long time consuming is the first three or four decisions, I thought that just making the computer to search for best points only around the human's last choice(point) would be a solution. After the first three or four decisions, above formal algorithm will work well for the few remaining points. How do you think about it? And give some advices to modify the current algorithm.

Parallel mergesort with parallel merge
how can I make a parallel mergesort with parallel merge? I didn't found any pseudocode on internet,I know only how to parallelize the first part of mergesort by spawn two thread for left and right,but how can I parallelize the merge? This is the code of the merge I need to parallelize.
public static int[] merge(int[] left, int[] right, int[] array) { int i = 0; int j = 0; int k = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { array[k] = left[i]; i++; } else { array[k] = right[j]; j++; } k++; } while (i < left.length) { array[k] = left[i]; i++; k++; } while (j < right.length) { array[k] = right[j]; j++; k++; } return array;

Qucksort gets StackOverflowError for 100000 elements but mergesort does not in Java
According to this SO post:
The common cause for a stack overflow is a bad recursive call.
Then why does it run for 10000 elements but get StackOverflowError for 100000 elements?
Quicksort:
public static void quicksort(int[] data, int low, int high) { if (low < high) { int p = partition(data, low, high); quicksort(data, low, p); quicksort(data, p + 1, high); } } public static int partition(int[] data, int low, int high) { int pivot = data[low]; int i = low  1; int j = high + 1; while (true) { do { i++; } while (data[i] < pivot); do { j; } while (data[j] > pivot); if (i >= j) return j; int temp = data[i]; data[i] = data[j]; data[j] = temp; } }
Mergesort:
public static void mergesort(int[] data, int left, int right) { if (left < right){ int middle = (left + right) / 2; mergesort(data, left, middle); mergesort(data, middle+1, right); merge(data, left, middle, right); } } private static void merge(int[] data, int left, int middle, int right) { int n1 = middle  left + 1; int n2 = right  middle; int[] dataLeft = new int[n1]; int[] dataRight = new int[n2]; for (int i = 0; i < n1; i++) dataLeft[i] = data[left+i]; for (int i = 0; i < n2; i++) dataRight[i] = data[middle+1+i]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (dataLeft[i] <= dataRight[j]) { data[k] = dataLeft[i]; i++; } else { data[k] = dataRight[j]; j++; } k++; } while (i < n1) { data[k] = dataLeft[i]; i++; k++; } while (j < n2) { data[k] = dataRight[j]; j++; k++; } }
For mergesort, it runs pretty well.
What is the reason? Would anyone please explain it?

Sorting a list of dictionaries in Python 3
I am trying to sort a list of dictionaries. My goal is to sort dictionaries with multiple (possibly the same) keys in the same way, even if the dictionaries are in a different order or if the keys are in the dictionary in a different order.
In Python 2, I have used the following:
a = [{1: 2, 7: 8}, {7: 8, 3: 4}, {5: 6}] b = [{3: 4, 7: 8}, {7: 8, 1: 2}, {5: 6}] a.sort() b.sort() a Out[20]: [{5: 6}, {1: 2, 7: 8}, {3: 4, 7: 8}] b Out[21]: [{5: 6}, {1: 2, 7: 8}, {3: 4, 7: 8}]
This succeeds in my goal of creating two sorted dictionaries that look exactly the same.
I am trying to do the same thing in Python 3, where .sort() does not work for a list of dictionaries.
I have tried different ways.
1.
sorted(a, key=lambda d: max(d.keys()))
This does not work:
a = [{1: 2, 7: 8}, {3: 4, 7: 8}, {5: 6}] b = [{3: 4, 7: 8}, {1: 2, 7: 8}, {5: 6}] a2 = sorted(a, key=lambda d: max(d.keys())) b2 = sorted(b, key=lambda d: max(d.keys())) a2 Out[1]: [{5: 6}, {1: 2, 7: 8}, {7: 8, 3: 4}] b2 Out[2]: [{5: 6}, {3: 4, 7: 8}, {7: 8, 1: 2}]
2.
a2 = sorted([list(zip(x.keys(),x.values())) for x in a]) a3 = [{k: v for (k,v) in x} for x in a2]
This does not work:
a = [{1: 2, 7: 8}, {7: 8, 3: 4}, {5: 6}] b = [{3: 4, 7: 8}, {7: 8, 1: 2}, {5: 6}] a2 = sorted([list(zip(x.keys(),x.values())) for x in a]) a3 = [{k: v for (k,v) in x} for x in a2] b2 = sorted([list(zip(x.keys(),x.values())) for x in b]) b3 = [{k: v for (k,v) in x} for x in b2] a3 Out[1]: [{1: 2, 7: 8}, {5: 6}, {7: 8, 3: 4}] b3 Out[2]: [{3: 4, 7: 8}, {5: 6}, {7: 8, 1: 2}]
Does anyone have an idea how I can get the Python 2 result in Python 3??

When operating game using a 2d array in C it goes in the improper direction
I was creating a game of fifteen and it wouldn't work due to the fact when I iterate in the move method both of the if statements make it go up instead of up and down. Due to this I cannot proceed and add further complexity to the program. Sorry if the question ends up being easy I'm new to coding and am trying to improve but some little things catch me here and there. Thank you for your time, and here is the code: (Although the problem lies in the Move() method (IMO) )
/** * fifteen.c * * Implements Game of Fifteen (generalized to d x d). * * Usage: fifteen d * * whereby the board's dimensions are to be d x d, * where d must be in [DIM_MIN,DIM_MAX] * * Note that usleep is obsolete, but it offers more granularity than * sleep and is simpler to use than nanosleep; `man usleep` for more. */ #define _XOPEN_SOURCE 500 #include <cs50.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <string.h> // constants #define DIM_MIN 3 #define DIM_MAX 9 // board int board[DIM_MAX][DIM_MAX]; // dimensions int d; // prototypes void clear(void); void greet(void); void init(void); void draw(void); bool move(int tile); bool won(void); int main(int argc, string argv[]) { // ensure proper usage if (argc != 2) { printf("Usage: fifteen d\n"); return 1; } // ensure valid dimensions d = atoi(argv[1]); if (d < DIM_MIN  d > DIM_MAX) { printf("Board must be between %i x %i and %i x %i, inclusive.\n", DIM_MIN, DIM_MIN, DIM_MAX, DIM_MAX); return 2; } // open log FILE *file = fopen("log.txt", "w"); if (file == NULL) { return 3; } // greet user with instructions greet(); // initialize the board init(); // accept moves until game is won while (true) { // clear the screen clear(); // draw the current state of the board draw(); // log the current state of the board (for testing) for (int i = 0; i < d; i++) { for (int j = 0; j < d; j++) { fprintf(file, "%i", board[i][j]); if (j < d  1) { fprintf(file, ""); } } fprintf(file, "\n"); } fflush(file); // check for win if (won()) { printf("ftw!\n"); break; } // prompt for move printf("Tile to move: "); int tile = get_int(); // quit if user inputs 0 (for testing) if (tile == 0) { break; } // log move (for testing) fprintf(file, "%i\n", tile); fflush(file); // move if possible, else report illegality if (!move(tile)) { printf("\nIllegal move.\n"); usleep(500000); } // sleep thread for animation's sake usleep(500000); } // close log fclose(file); // success return 0; } /** * Clears screen using ANSI escape sequences. */ void clear(void) { printf("\033[2J"); printf("\033[%d;%dH", 0, 0); } /** * Greets player. */ void greet(void) { clear(); printf("WELCOME TO GAME OF FIFTEEN\n"); usleep(2000000); } /** * Initializes the game's board with tiles numbered 1 through d*d  1 * (i.e., fills 2D array with values but does not actually print them). */ void init(void) { int c = (d*d)  1; if (d % 2 == 0) { for (int i = 0; i<d; i++) { for (int j = 0; j<d; j++) { board[i][j] = c; /* if (i == d1 && j == d1) { board[i][j] = 0; } */ if (c == 2) { board[i][j] = 1; } else if (c == 1) { board[i][j] = 2; } c; } } } else { for (int i = 0; i<d; i++) { for (int j = 0; j<d; j++) { board[i][j] = c; c; } } } } /** * Prints the board in its current state. */ void draw(void) { string empty = " _ "; for (int i = 0; i<d; i++) { for (int x = 0; x<d; x++) { /* if (d % d > 0 && x == d1 && i == d1) { printf("_"); } else { */ //printf("%d \n", board[i][x]); if (board[i][x] != 0) { printf("%2i", board[i][x]); printf("");} else { printf("%s", empty); } if (x == d1) { printf("\n"); } } } } //All Good Above! /** * If tile borders empty space, moves tile and returns true, else * returns false. */ bool move(int tile) { int change; printf("Up , down, right , left?"); string movement = get_string(); //does not move when it is exchanging with blnk //also does not move if beyond range of array > for (int i = 0; i<d; i++) { //rows for (int x = 0; x<d; x++) //cols { if (tile == board[i][x] && (strcmp(movement,"Up")  strcmp(movement,"up"))) { change = board[i][x]; board[i][x] = board[i1][x]; board[i1][x] = change; return true; } else if (tile == board[i][x] && (strcmp(movement,"Down")  strcmp(movement,"down"))) { change = board[i][x]; board[i][x] = board[i+1][x]; board[i+1][x] = change; return true; } } } return false; } /** * Returns true if game is won (i.e., board is in winning configuration), * else false. */ bool won(void) { //not done //dont worry about int c = 0; for (int i = 0; i < d; i++) { for (int x = 0; x<d; x++) { c++; if (board[i][x] == c) { return true; } else { return false; } c++; } } return false; }

Withdraw all data from a SQL table to my Python code
This might seem obvious but I can't find how I can use the SELECT statement to withdraw all the data from a table to a list in my python code..
This is what I need: my table is called history and it has 7 columns, so I need to get every value for later show it on my html code
This is my code so far:
portfolio = db.execute("SELECT * FROM history WHERE id=:user_id;", user_id=session["user_id"]) symbol = portfolio[[0]'symbol'] name = portfolio[[0]'name'] share = portfolio[[0]'shares'] price = portfolio[[0]'price'] total = portfolio[[0]'total'] . . . return render_template("portfolio.html", search = search, total = total, share = share, share_tot = share_total, trade = trade)
Error:
symbol = portfolio['symbol']
TypeError: list indices must be integers or slices, not str

CS50 "Fifteen" Game Failing All Checks and Board not Printing
My code compiled but won't go through any of the checks because the board wont even compile and I don't understand why. Please let me know what I can do—at this point it's a mes... any help is appreciated, thank you so much. Maybe the issue is that I also used xvalues and yvalues to try and create the board, but that was such a big part of my code I'm not sure if I can even salvage it at this point or if I should just dropout.
/** * fifteen.c * * CS50 AP * Fifteen * * Implements Game of Fifteen (generalized to d x d). * * Usage: fifteen d * * whereby the board's dimensions are to be d x d, * where d must be in [DIM_MIN,DIM_MAX] * * Note that usleep is obsolete, but it offers more granularity than * sleep and is simpler to use than nanosleep; `man usleep` for more. * * Extra features including printing an actual grid to make it look more * tilelike, and using ANSI color sequences for some additional customizing */ #define _XOPEN_SOURCE 500 #include <cs50.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> // constants #define DIM_MIN 3 #define DIM_MAX 9 // ansi escape sequence to print grid color // replace the number between [ and m with 31 for red, 32 for green, 33 for brown, // 34 for blue, 35 for purple, 36 for cyan, 37 for gray #define COLOR "\033[32m" // board int board[DIM_MAX][DIM_MAX]; // dimensions int d; int yspace; int xspace; // saved locations of the blank tile int blank_row; int blank_col; // prototypes void clear(void); void greet(void); void init(void); void draw(void); bool move(int tile); bool won(void); void swap(int *a, int *b); void print_grid_row(int d); void print_tile(int tile); int main (int argc, string argv[]) { // ensure proper usage if (argc != 2) { printf("Usage: fifteen d\n"); return 1; } // ensure valid dimensions d = atoi(argv[1]); if (d < DIM_MIN  d > DIM_MAX) { printf("Board must be between %i x %i and %i x %i, inclusive.\n", DIM_MIN, DIM_MIN, DIM_MAX, DIM_MAX); return 2; } // open log FILE *file = fopen("log.txt", "w"); if (file == NULL) { return 3; } // greet user with instructions greet(); // initialize the board init(); // accept moves until game is won while (true) { // clear the screen clear(); // draw the current state of the board draw(); // log the current state of the board (for testing) for (int i = 0; i < d; i++) { for (int j = 0; j < d; j++) { fprintf(file, "%i", board[i][j]); if (j < d  1) { fprintf(file, ""); } } fprintf(file, "\n"); } fflush(file); // check for win if (won()) { printf("ftw!\n"); break; } // prompt for move printf("Tile to move: "); int tile = get_int(); // quit if user inputs 0 (for testing) if (tile == 0) { break; } // log move (for testing) fprintf(file, "%i\n", tile); fflush(file); // move if possible, else report illegality if (!move(tile)) { printf("\nIllegal move.\n"); usleep(500000); } // sleep thread for animation's sake usleep(50000); } // close log fclose(file); // success return 0; } /** * Clears screen using ANSI escape sequences. */ void clear(void) { printf("\033[2J"); printf("\033[%d;%dH", 0, 0); } /** * Greets player. */ void greet(void) { clear(); printf("WELCOME TO GAME OF FIFTEEN\n"); usleep(2000000); } /** * Initializes the game's board with tiles numbered 1 through d*d  1 * (i.e., fills 2D array with values but does not actually print them). */ void init(void) { int bonk = 0; for(int j = 0; j < d; j++) { for(int i = 0; i <= d; i++) { bonk = ((j + 1) * d)  (i + 1); switch (bonk) { case 1 : { if(d % 2 == 1) board[i][j] = bonk; else if(d % 2 == 0) board[i][j] = 2; break; } case 2 : { if(d % 2 == 1) board[i][j] = bonk; else if(d % 2 == 0) board[i][j] = 1; break; } default : { board[i][j] = bonk; break; } } } } } /** * Prints the board in its current state. */ void draw(void) { for(int j = d  1; j >= 0; j) { for(int i = 0; i < d; i++) { if (board[i][j] >= 100) { printf("%d",board[i][j]); } else if (board[i][j] >= 10) { if (d*d>101) printf("%d ", board[i][j]); if (d*d<101) printf("%d", board[i][j]); } else if (board[i][j] <= 10) { if (board[i][j] == 0) printf(" "); else if(board[i][j] > 0) { if (d*d>101) printf("%d ", board[i][j]); if (d*d>101) printf("%d ", board[i][j]); } } // else if(board[i][j] == 0) // { // printf(" "); // } } printf("\n"); } } /** * If tile borders empty space, moves tile and returns true, else * returns false. */ bool move(int tile) { int bonk = 0; int xval = 0; int yval = 0; for(int j = d  1; j >= 0; j) { for(int i = 0; i < d; i++) { if (board[i][j] == tile) { xval = i; yval = j; } if (board[i][j] == 0) { xspace = i; yspace = j; } } } //bonk++; //printf("%d,%d\n",xval,yval); if(xval  1 == xspace && yval == yspace) { bonk = board[xval][yval]; board[xval][yval] = 0; board[xspace][yspace] = bonk; return true; } if(xval + 1 == xspace && yval == yspace) { bonk = board[xval][yval]; board[xval][yval] = 0; board[xspace][yspace] = bonk; return true; } if(yval  1 == yspace && xval == xspace) { bonk = board[xval][yval]; board[xval][yval] = 0; board[xspace][yspace] = bonk; return true; } if(yval + 1 == yspace && xval == xspace) { bonk = board[xval][yval]; board[xval][yval] = 0; board[xspace][yspace] = bonk; return true; } // checks that tile is adjacent to the empty space: if it is then it copies it's value to that space and clears it's original space return false; } /** * Returns true if game is won (i.e., board is in winning configuration), * else false. */ bool won(void) { int bonk = 0; for(int j = d  1; j >= 0; j) { for(int i = 0; i < d; i++) { bonk++; if(bonk == d * d) bonk = 0; if(board[i][j] != bonk) return false; } } return true; }

Not getting correct sorted array with a counting sort
I am working on the Counting Sort Algorithm currently. I have set up two temporary arrays
C
andB
.C
is to count the number of times a number in the original array appears. It then uses the elements inC
to place the elements inA
(original array) into the correct location inB
. I have mycountingSort
function print outC
after each loop to ensure that it has the correct values in it (which it does, I'm testing it with a small sample size). The problem occurs when I go to insert the elements ofA
intoB
with the help ofC
.Here is my function for
countingSort
:Note: I pass an array of 10 integers
2 0 3 2 5 4 3 6 10
to the function,the temporary arrayB
, themaximum
value (so I know what size to makeC
) and the size of arrayA
void countingSort(int A[], int B[], int k, int size){ int C[k + 1]; cout << "K: " << k << endl; for(int i = 0; i < k + 1; i++){ C[i] = 0; } for(int i = 0; i < k + 1; i++){ cout << C[i] << " "; } for(int i = 0; i < size; i++){ C[A[i]] = C[A[i]] + 1; } cout << endl; for(int i = 0; i < k + 1; i++){ cout << C[i] << " "; } for(int i = 0; i < k + 1; i++){ C[i] = C[i] + C[i  1]; } cout << endl; for(int i = 0; i < k + 1; i++){ cout << C[i] << " "; } for(int i = size + 1; i > 0; i){ B[C[A[i]]] = A[i]; C[A[i]] = C[A[i]]  1; } cout << endl; for(int i = 0; i < size; i++){ cout << B[i] << " "; } }
As you can see I print out
C
after each loop, so after the first loop it should show thatC
is0 0 0 0 0 0
, which it does print out correctly. After the next for loop itC
should be2 1 2 2 1 1 1
, which it also prints out correctly. Next it adds the elements ofC
up to get2 3 5 7 8 9 10
, which is also printed out correctly. Now my issue arises here when I try to put the elements ofA
intoB
. It is supposed to print0 0 1 2 2 3 3 4 5 6
, but it prints0 0 0 1 0 2 3 3 4 5
instead.I have tried playing around with my indexes on the last for loop, but just cant seem to figure out what is causing
B
to be incorrect. How could I fix this issue? My overall goal is to get the count sort to work for a randomly generated array of size40
with numbers between 1 and 25.Edit: Main Function where I call
countingSort
:int sizeCount1 = 10; int countOne[10] = {2, 0, 3, 2, 5, 4, 3 ,6, 1, 0}; cout << "Counting Sort Version 1 (Pre Sort)" << endl; for(int i = 0; i < sizeCount1; i++){ cout << countOne[i] << " "; } cout << endl; for(int i = 0; i < sizeCount1; i++){ countTemp[i] = 0; } int max = 0; for(int i = 0; i < sizeCount1; i++){ if(countOne[i] > max){ max = countOne[i]; } } cout << "Max: " << max << endl; countingSort(countOne, countTemp, max, sizeCount1); cout << endl; cout << "Counting Sort Version 1 (Post Sort)" << endl; for(int i = 1; i < 10; i++){ cout << countTemp[i] << " "; } cout << endl << endl;

Counting sort in pyspark
I have an RDD consisting of over 140 million keyvalue pair. With my analysis, I found that there are only around 500 unique keys. I have to sort this RDD.
I tried to use groupByKey() to group all the keyvalue pairs based on the key and then use sortBy() to sort all the keys. After sorting, I use map() to output the sorted keyvalue pairs. With this approach, I am getting this error in spark
Container killed by YARN for exceeding memory limits. 6.3 GB of 6 GB physical memory used. Consider boosting spark.yarn.executor.memoryOverhead.
This error is because there are some keys holding 10 million values after the groupByKey().
Since the number of keys is very very small visavis the number of keyvalue pairs, so we can implement something similar to count sort.
Is there a way to implement it in pyspark?

Why counting sort is not preffered for sorting strings
As given in the wikipedia about the counting sort that it is an integer sorting algorithm.i want to know that why cant we use it for sorting strings.