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

Getchar() infinite loop
I’m starting to learn from "The C Programing Language" and one of the codes in the book is not working for me. This code suppose to count the number of characters using
getchar()
.Here is my code:
#include <stdio.h> int main() { long nc; nc = 0; while (getchar() != EOF) ++nc; printf("%1d\n", nc); return 0; }
I try to run it and write some characters but when I press
ENTER
, it only starts a new line. It's like it’s never getting out of the loop. 
Failed to optimize a version of QuickSort with one recursive call
I'm trying to implement the QuickSort but with just one recursive call in its code. many Tests are applied to the program. There is a file where it compares it to the real qsort function in order to verify whether the new version of qsort works or not. So it does a lot of tests from 8 integers for the array to 2048 integers.
So when I execute the program, it's supposed to write "OK" at every succesful test like this:
Test with 8 integers OK Test with 16 integers OK Test with 32 integers OK Test with 64 integers OK Test with 128 integers OK Test with 256 integers OK Test with 512 integers OK
The code is shown below
The code to find the median of three
void median(int t[], int n){ int m = ((n  1) / 2); if (t[0] > t[n  1]) { /* t[0] > t[n  1] */ if (t[m] > t[0]); /* t[m] > t[0] > t[n  1] */ else if (t[n  1] > t[m]) /* t[0] > t[n  1] > t[m] */ swap(t[0], t[n1]); else /* t[0] >= t[m] >= t[n  1] */ swap(t[0], t[m]); } else { /* t[0] <= t[n  1] */ if (t[m] < t[0]) ; /* t[m] < t[0] <= t[n  1] */ else if (t[n  1] < t[m]) /* t[0] <= t[n  1] < t[m] */ swap(t[0], t[n1]); else /* t[0] <= t[m] <= t[n + 1] */ swap(t[0], t[m]); } }
The function for partitioning
int partition( int t[], int n) { int l = 0, r = n, tmp; median(t, r); while(1) { do ++l; while(l < n && t[l] < t[0]); // l <= n1 do r; while(t[r] > t[0]); // r >= 0 if( l >= r ) break; tmp = t[l]; t[l] = t[r]; t[r] = tmp; } tmp = t[0]; t[0] = t[r]; t[r] = tmp; return r; }
And the code of QuickSort
void version2(int t[], int size) { int m, l = 0, r = size ; while((r  l) > 1) { m = partition( t + l, r); if( (m  l) < (r  m)){ version2(t + l, m); l = m + 1; } else{ version2(t + m + 1, r); r = m; } } }
When I try to execute it I get only this
Test with 8 integers
As it was in an infinite loop

Getting program to run on command
I'm new here so sorry if this is a dumb/bad question but I just cannot figure out how to do it for the life of me.
So how would one go about linking a c program to a command. For example lets say I had helloworld.c and I entered make helloword and then wanted to run the command helloworld to run helloworld anywhere on the system. How would I go about this (not using bash aliases).

Inserting node in linked list
I'm trying to insert a node dynamically between two indices which hold struct of type Node. The first element in array is head pointer and second element is tail.
I'm trying to dynamically grow the double linkedlist between the two indices of the array. Following is the code I've tried so far.
I could have created head and tail as an node dynamically as well but as per the requirement I've to do like this.
It is guarenteed to have the node which is to be inserted
data
value in between the value ofqllentry[0].data
andqllentry[1].data
#include <stdio.h> #include <stdlib.h> #include <limits.h> struct Node { int data; struct Node *qprev; struct Node *qnext; }Node; struct Node qllentry[2]; int main() { struct Node head, tail; head.data = INT_MAX; tail.data = INT_MIN; head.qnext = &tail; tail.qprev = &head; head.qprev = NULL; tail.qnext = NULL; qllentry[0] = head; qllentry[1] = tail; int key = 20; struct Node *curr ; struct Node *prev; curr= &qllentry[0]; while(curr>qnext != NULL && curr>data >= key) { curr = curr>qnext; } prev = curr>qprev; struct Node *new_node = (struct Node*)malloc(sizeof(struct Node)); new_node>data = key; new_node>qnext = prev>qnext; prev>qnext = new_node; new_node>qprev = prev; if (new_node>qnext != NULL) new_node>qnext>qprev = new_node; return 0; }
The insertion of the new node isn't happening between the head and tail indices as expected. I've added few print statements for debugging
Any help is appreciated.

2D Array consecutive elements algorithm
I have had a task given to me which requires me to ask user for a size of 2D Array, we need to create a 2D array with the specified size, so if user opted for 8 as the size, we make an
8x8
array and we randomly fill it with either'X'
or'O'
.Now the main task is to find number of
group
s in that 2D array.4 or more 'X' which are connected (horizontally
OR
verticallyNOT
diagonally) are what makes agroup
.For example, there are 3 groups on the following photo:
My question is if there is (there probably is) an algorithm that deals with similar problems, so please do provide reading material if you have any.

hard geometry task from interview
You have a convex hull with n points inside and you should build a rectangle with the biggest square inside them so that there was no point inside the rectangle. For better understanding look at the picture:
Time complexity is N*logN

Sort the data using pandas  sort on first column conditional on values in other columns
I tried to get the below input data with
awk, sort, sed
. I am feeling it might be too complicated to handle them using those unix utilities. Proabablypandas
might be good.These are the conditions for sorting the data.
 first sort the column #1 in increasing order.
 now, within each column #1 group the data based on same keys in column #3 (sort order not important).
Now, sort the column #2 based only on the very smallest value for each group in col#3.
For eg:
for group4 (in col#3) the smallest value in col2 is 15882592 which is << group5 (in col#3) smallest value 15883889; So group4 should be on top of group5.
Similarly, for group5 (in col3) smallest value is in col2 15883889 << group1 (in col3) smallest value 15885010; So group5 should be on top of group1.
So, finally I have to group col#1 first and then column#2 conditional (grouped) on col#3.
Input Data:
2 15881989 6 2 15882091 6 2 15882148 6 2 15882328 6 2 15882364 6 2 15882451 8 2 15882454 8 2 15882493 8 2 15882592 4 2 15882601 4 2 15882607 4 2 15883765 4 2 15883782 4 2 15883783 4 2 15883785 4 2 15883861 4 2 15883862 4 2 15883889 5 2 15883894 5 2 15883904 5 2 15884457 5 2 15884525 5 2 15884546 4 2 15884550 4 2 15884582 4 2 15884613 4 2 15884649 4 2 15884742 4 2 15884965 4 2 15885010 1 2 15885024 1 2 15885061 4 2 15896126 4 3 15896174 4 3 15896152 4 3 15896128 3 3 15896224 3 3 15896258 3 3 15896406 3
Expected output:
2 15881989 6 2 15882091 6 2 15882148 6 2 15882328 6 2 15882364 6 2 15882451 8 2 15882454 8 2 15882493 8 2 15882592 4 2 15882601 4 2 15882607 4 2 15883765 4 2 15883782 4 2 15883783 4 2 15883785 4 2 15883861 4 2 15883862 4 2 15884546 4 2 15884550 4 2 15884582 4 2 15884613 4 2 15884649 4 2 15884742 4 2 15884965 4 2 15885061 4 2 15896126 4 2 15896128 4 2 15896152 4 2 15883889 5 2 15883894 5 2 15883904 5 2 15884457 5 2 15884525 5 2 15885010 1 2 15885024 1 3 15896128 3 3 15896224 3 3 15896258 3 3 15896406 3 3 15896152 4 3 15896174 4
Thanks,

Sort numbered list
I can't seem to find any information on how to correctly sort a list like this. My list looks something like this
["1. Banana", "2. Pear", "11. Apple", "5. Grapes", "4. Orange"]
Using
sorted()
leaves me with the following['1. Banana', '11. Apple', '2. Pear', '3. Orange', '4. Grapes']
and I would like it to come out like this
['1. Banana', '2. Pear', '3. Orange', '4. Grapes', '11. Apple']
If it adds any complications I need to use this to sort a list of dictionaries using a specific key's value, so my current code islist.sort(key=lambda k: k["key"])

Sort list of lists creating another mapping list with index values
So i have an original list of lists oList, child lists are sequences of numbers. I create another list srt to manipulate the data like that:
#... srt = [] for i in range(len(oList)): srt.append([ int(oList[i][0]), int(oList[i][2]), i ])
So each element of srt is [n0,n2,idx] (or something like that, main point is that i keep index of original element from oList as last element)... Now i want to sort it via(n0,n2...ni) with indexing as creation of another mapping list of idx.
srt.sort()
does the first part just fine, but generating mapping manually seems inefficient to me.So i want srt to be sorted by both n0, n1 ... ni and another list map to contain indexes of original elements. And while processing data in a loop i want to be able (when i need to) to get some element from srt via idx like that:
something = srt[map[idx]][0]
Example:
# srt=[ [12,8,0], [4,4,1], [4,2,2], [6,8,3], ] map, srt = custom_sort_here(srt) # srt=[ [4,2,2], [4,4,1], [6,8,3], [12,8,0], ] # map=[ 3, 1, 0, 2, ] # here i can get element with idx=2 from srt like: el = srt[map[2]]
P.S. atm i have my indexing performed AFTER the sorting as a loop:
#... srt.sort() map = range(len) for x in range(len): map[srt[x][2]]=x #for 2number lists where idx at [2]
So it is very inefficient, and that's the reason for my question  i mean it's definitely possible to create mapping structure WHILE sorting, and i just don't know how cuz i'm new to Python...
P.P.S. if u wonder why i want such weird behaviour  it has something to do with 3D mesh processing, so i really need to keep original point values + polygon data while manipulating duplicate point array of projected [2]coords and/or discreet (approximated) [3]coord values of the original points. Looping thru them along the axis/vectors while sometimes still get some points via indexes according to polygon edge connections. So i REALLY need that kind of data layout.

Round function off by 1  C
char note_array[] = "G#5"; int approx_freq = 880; int result = 0; if(note_array[1] == '#') approx_freq = round(approx_freq * pow(2, 1.0/12)); switch(note_array[0]) { case 'A': result = approx_freq; break; case 'B': result = round(approx_freq * pow(2, 2.0/12)); break; case 'C': result = round(approx_freq / pow(2, 9.0/12)); break; case 'D': result = round(approx_freq / pow(2, 7.0/12)); break; case 'E': result = round(approx_freq / pow(2, 5.0/12)); break; case 'F': result = round(approx_freq / pow(2, 4.0/12)); break; case 'G': result = round(approx_freq / pow(2.0, 2.0/12)); break; default: return 1; break; } return result;
Output Coming  830
Output Needed  831
I know there is something wrong with my usage of the round function, but I don't know what I'm doing wrong. Can anybody please help me out?

fgetc not displaying correctly after space
#include <stdio.h> #include <stdlib.h> #include <string.h> int main() { FILE *userfile, *pwfile, *usernamesPasswords, *readUsernamesPasswords; char u, p, user[20][25], pass[20][20], userLine[25], passLine[20]; int i = 0; int j = 0; int userIndex = 0; int passIndex = 0; userfile = fopen("usernames.txt", "r"); pwfile = fopen("passwords.txt", "r"); if (userfile == NULL  pwfile == NULL) { printf("Cannot open file \n"); exit(0); } u = fgetc(userfile); while (u != EOF) { if ( u != '\n'){ userLine[userIndex++] = u; } else { userLine[userIndex] = '\0'; strcpy(user[i], userLine); userIndex = 0; i++; } u = fgetc(userfile); } fclose(userfile); p = fgetc(pwfile); while (p != EOF) { if ( p != '\n'){ passLine[passIndex++] = p; } else { passLine[passIndex] = '\0'; strcpy(pass[j], passLine); passIndex = 0; j++; } p = fgetc(pwfile); } fclose(pwfile); usernamesPasswords = fopen("usernamesPasswords.txt", "w"); int w, k; char newLine[1024]; for (w=0;w<20;w++) { strcat(newLine, user[w]); int q = strlen(newLine); for (k=0;k<(25q);k++) { strcat(newLine, " "); } strcat(newLine, pass[w]); strcat(newLine, "\n"); strcat(newLine, "\0"); fputs(newLine ,usernamesPasswords); strcpy(newLine, ""); } fclose(usernamesPasswords); printf("\nDo you want to display the new file? Enter (y) to view and any other key to exit\n"); char word; scanf("%c",&word); if (word == 'y') { readUsernamesPasswords = fopen("usernamesPasswords.txt", "r"); if (readUsernamesPasswords == NULL) { printf("Cannot open file \n"); exit(0); } char r; while((r=fgetc(readUsernamesPasswords))!=EOF) { printf("%c", r); } fclose(readUsernamesPasswords); } return 0; }
Expected Output:
Moodie 123456 Intelllligent password Happee 12345678 Mischeivous qwerty SweetKristy 123456789 KristyHoney 12345 BubblySnowflake 1234 AngelicPrincessKristy 111111 FairyPrincessKristy 1234567 BabyKristyButterfly dragon daffyusers 123123 magpiedoodle baseball aspiringthreat abc123 landmarksspreader football cavaliervanquish monkey chatteringparma letmein veggiehydrogen 696969 teethunsure shadow rumpboast master lidarstrudel 666666
Instead...
123456 password 12345678 qwerty 123456789 12345 1234ke 111111incessKristy 1234567sKristy dragonutterfly 123123 baseball abc123 footballer monkeysh letmein 696969 shadow master 666666
This only happens when I try to output on terminal. The actual usernamesPasswords.txt file comes out as expected. The left side of strings only seem to get printed only when I newline in place of whitespace...
I even tried fgets and fread but similar output. I have read other posts about eating or consuming so I tried using fgets or fread as suggested and even tried unget. did not seem to work. I have been looking all over stack overflow to no avail.
If this is a duplicate, I apologize in advanced. I have really tried to look all over the web for couple hours before deciding to post.
I usually don't post cuz stack overflow usually has everything already...
Please help! Thank you!

Logical Error in Calculation  C
The value of approx_freq = 440
case 'C': result = round(approx_freq / pow(2, 9/12));
But the problem is that the above calculation is not getting executed. The value of result in each case is 440.

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.