Counting sort in C apparently works but binarysearch doesn't

2017-06-17 18:52 J.Ober imported from Stackoverflow

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

answered 2017-06-17 18:52 Gassa
1. In binarysearch, the loop condition while(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 to while(end>=start), which literally means that the considered interval is non-empty.
2. In countsort, the line array=finalarr; does not copy the whole array. Instead, the local variable array becomes a pointer to finalarr. 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 changing finalarr[count]=i; to array[count]=i; and get rid of finalarr completely, putting the values into array right away. Alternatively, you can use memmove instead of that line.

See also questions close to this topic

C XOR Crypter doesn't work with long files

I wrote a C program to perform an XOR encryption. The code works with small files, but not for big files.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define BUF_SIZE 5

char* xor(char*,char*);
char* gen_key(size_t);
char* read_file(char*);
void  write_file(char*,char*);

int
main(int argc,char** argv)
{
    if(argc < 3)
        return -1;
    char *buffer = NULL ,*encrypted_buffer = NULL;
    char key[] = "Aydhdjezushdeosh";//gen_key(6);   
    buffer = read_file(argv[1]);
    encrypted_buffer = xor(buffer,key);
    free(buffer);
    write_file(encrypted_buffer,argv[2]);
    free(encrypted_buffer);
    return 0;
}

char*
gen_key(size_t length)
{
    srand(time(NULL));
    const char charset[] ="AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoP"
    "pQqRrSsTtUuVvWwXxYyZz012345679";
    const size_t charset_size = strlen(charset);
    unsigned int i;
    char *key = NULL;
    key = (char*)malloc((length + 1)*sizeof(char));
    memset(key,0, length + 1);
    for(i = 0; i < length; i++)
        key[i] = charset[rand() % charset_size];
    return key;
}

char*
xor(char* file,char* key)
{
    unsigned int i;
    printf("file : %d\n",strlen(file));
    char* xor = (char*)calloc(strlen(file) + 1,sizeof(char));
    memset(xor,0,strlen(file) + 1);
    for(i = 0; i < strlen(file) + 1; i++)
        *(xor + i) = *(file + i) ^ *(key + (i%strlen(key)));
    printf("length : %d\n",strlen(xor));
    return xor;
}

char*
read_file(char* file_name)
{
    size_t file_size;
    char *buffer = NULL;
    char tmp_buffer[BUF_SIZE];
    FILE *finput = NULL ;
    finput = fopen(file_name,"rb");
    fseek(finput,0,SEEK_END);
    file_size = ftell(finput);
    rewind(finput);
    buffer = (char*)malloc((file_size + 1) * sizeof(char));
    memset(buffer,0,file_size + 1);
    while (fgets(tmp_buffer, sizeof(tmp_buffer), finput))
    {
        strcat(buffer,tmp_buffer);
        memset(tmp_buffer,0,BUF_SIZE);
    }
    fclose(finput);
    return buffer;
}

void
write_file(char* buffer,char* file_name)
{
    FILE *foutput = NULL;
    int i;
    foutput = fopen(file_name,"wb");
    size_t s = fwrite(buffer,1,strlen(buffer) + 1,foutput);
    fclose(foutput);
}

So the output of small files is :

file : 93
length : 92

But with a big file :

file : 7344
length : 0

Those values are printed in the xor function.

Binary search stops working when more than 44 elements in an array
This is my first time posting here, so forgive stupid mistakes if such happen.

I am a beginner in C coding (learning right now), and frankly not much of a math genius so the problem I encountered stumps me quite a bit. I found a solution to it by the way of testing different things, but honestly I don't exactly understand why my solution does work, and the code before the solution applied doesn't.

The code is a binary search for a given number in a sorted array created by using seeded srand48, and sorted with a linear sort.

To frame the situation. Code before the solution did work well until array reached 45 elements, then it stopped finding the number.

Before the solution code:
```
bool search(int value, int values[], int n)
{
    int first, middle, last;

    first = 0;
    last = n - 1;
    middle = (first + last) / 2;

    if (n > 0)
    {
        while (first < last)
        {
            if (values[middle] == value)
            {
                return true;
            }
            else if (values[middle] < value)
            {
                first = middle + 1;
            }
            else
            {
                last = middle - 1;
            }
            middle = (first + last) / 2;
        }
    }
    else
    {
        return false;
    }
    return 0;
}
```
The solution I found was just removing + and - 1 from the new middle value assignment. After I did this it works perfectly fine. What I would like to know for my own future reference and learning is why exactly the first code does not work, and why did that solution fix it. (I might somehow subconsciously understand how this works and that is why I came up with the fix, but I can't consciously figure out the logic behind it.)
Inline assembly syntax error
I'm trying to compile this inline assembly (compiled with gcc -masm=intel), for some reason I get the following error:

error: expected ')' before ':' token
```
void *cont_exec=0x80402832;
asm("mycode:;"
"test byte ptr [rbp-0x10], 0x1;"
"je cont;"
"call function;"
"cont:;"
"jmp %0;"
: //error in this line
: "r" (cont_exec));
```

Check if my approach to SelectionSort is correct, also determine its complexity

The algorithm is like this:

1 do for i=0 to A.length
2    do key = A[i]
3      j=i+1
4     while j < A.length
5        do check if ( A[j] < key )
6           A[i] = A[j]

Distributed genetic algorithm exchange

I am working in the scientific field where we study the influence of genes in plants for a very simplified system. We are currently running several instances on our cluster, and simply exchange the top 50% percent between the different nodes. This is very simple and works reasonably well.

I am now wondering if any work has been done on finding smart exchange/cross/mutation strategies. Communicating a set of genes between nodes is quiet expensive, and I see some optimization potential there.

For example I could imagine segmenting the nodes into groups and crossbreeding only in between groups - with one big exchange every X generations.

Is anyone aware of any previous work on this topic?

Why HashMap resize In case of collision or worst case

I am asking this question with respect to java version till 1.7 only. I am using reflection to find out current capacity of HashMap. In below program am putting 12 unique person into a single bucket of HashMap (using same hashcode) . Then i am putting 13th unique person on same or different bucket(using same or different hashcodes). In both the cases after adding this 13th element, HashMap resizes to 32 buckets. i understand that due to load factor .75 and initial capacity 16 HashMap resizes to it's double with 13th element. But there are still empty buckets available and only 2 buckets are used for these 13th element.

My questions are:

1) Is my understanding correct. Am i not making any mistake. Is this the expected behavior of HashMap .

2) If all this is correct then even though there are 12 or 11 free buckets why the need to double the HashMap with 13th element in this case. Isn't it extra overhead or costly to resize the HashMap. What is the need to double the HashMap in this case While 13th can be put in any avalable bucket according to hashcode.

public class HashMapTest {
    public static void main(String[] args) throws NoSuchFieldException,
            SecurityException, IllegalArgumentException, IllegalAccessException {
        HashMap<Person, String> hm = new HashMap<Person, String>();
        for (int i = 1; i <= 12; i++) {
            // 12 Entry in same bucket(linkedlist)
            hm.put(new Person(), "1");
        }
        System.out.println("Number of Buckets in HashMap : "+bucketCount(hm));
        System.out.println("Number of Entry in HashMap :  " + hm.size());
        System.out.println("**********************************");
        // 13th element in different bucket
        hm.put(new Person(2), "2");
        System.out.println("Number of Buckets in HashMap : "+bucketCount(hm));
        System.out.println("Number of Entry in HashMap :  " + hm.size());
    }
    public static int bucketCount(HashMap<Person, String> h)
            throws NoSuchFieldException, SecurityException,
            IllegalArgumentException, IllegalAccessException {
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(h);
        return table == null ? 0 : table.length;
    }
}

class Person {
    int age = 0;
    Person() {
    }
    Person(int a) {
        age = a;
    }
    @Override
    public boolean equals(Object obj) {
        return false;
    }
    @Override
    public int hashCode() {
        if (age != 0) {
            return 1;
        } else {
            return age;
        }
    }
}

OUTPUT

Number of Buckets in HashMap : 16
Number of Entry in HashMap :  12
**********************************
Number of Buckets in HashMap : 32
Number of Entry in HashMap :  13

Sort a Custom Listview Adapter by Date

I want to programm a ChatApp with Firebase. Right now I am displaying the Users I chat with. But now I want them to be sorted by a Date String I am using: For Example: 21-06-2017 17:20. It should be sorted from the latest Time to the earliest Time.

My Adapter:

public class ChatAdapter extends ArrayAdapter<String> {

private Activity context;
private List<Chats> chatsList = new ArrayList<>();

public ChatAdapter(Activity context, List<Chats> chatsList) {
    super(context, R.layout.abc_main_chat_item);
    this.context = context;
    this.chatsList = chatsList;
}

@Override
public View getView(final int position, final View convertView, ViewGroup parent) {
    LayoutInflater inflater = context.getLayoutInflater();
    View listViewItem = inflater.inflate(R.layout.abc_main_chat_item, null, true);

    TextView tvusername = (TextView) listViewItem.findViewById(R.id.group_name);
    TextView tvuid = (TextView) listViewItem.findViewById(R.id.useruid);
    TextView tvlastmessage = (TextView) listViewItem.findViewById(R.id.latestMessage);
    TextView tvlastmessagetime = (TextView) listViewItem.findViewById(R.id.latestMessageTime);
    ImageView ivphoto = (ImageView) listViewItem.findViewById(R.id.profileImg);

    tvusername.setText(chatsList.get(position).getUsername());
    tvlastmessage.setText(chatsList.get(position).getLastMessage());
    tvlastmessagetime.setText(chatsList.get(position).getLastMessageTime());
    tvuid.setText(chatsList.get(position).getUseruid());
    Picasso.with(getContext()).load(chatsList.get(position).getPhotoURL()).placeholder(R.drawable.ic_person_grey_round).into(ivphoto);

    listViewItem.setOnClickListener(new View.OnClickListener() {
        @Override
        public void onClick(View v) {
            Intent i = new Intent(context, Chat_Room.class);
            i.putExtra("room_name", chatsList.get(position).getUsername());
            i.putExtra("room_uid", chatsList.get(position).getUseruid());
            context.startActivity(i);

        }
    });

    listViewItem.setOnLongClickListener(new View.OnLongClickListener() {
        @Override
        public boolean onLongClick(View v) {
            final Dialog dialog = new Dialog(context);
            dialog.setContentView(R.layout.abcd_listview_alertdia_layout);
            ArrayList<String> list_of_chats = new ArrayList<>();
            final ArrayAdapter<String> arrayAdapter;
            arrayAdapter = new ArrayAdapter<String>(context, android.R.layout.simple_list_item_1, list_of_chats);

            list_of_chats.add(0, "Chatverlauf mit "+ chatsList.get(position).getUsername()+" löschen?");
            list_of_chats.add(1, "Profil von "+chatsList.get(position).getUsername()+" anschauen");
            arrayAdapter.notifyDataSetChanged();
            final ListView lv = (ListView) dialog.findViewById(R.id.lv);
            lv.setAdapter(arrayAdapter);
            lv.setOnItemClickListener(new AdapterView.OnItemClickListener() {
                @Override
                public void onItemClick(AdapterView<?> parent, View view, final int position2, long id) {
                    if (position2 == 0) {
                        dialog.dismiss();
                        AlertDialog.Builder alert = new AlertDialog.Builder(context);
                        alert.setTitle("Chatverlauf mit "+chatsList.get(position).getUsername()+" löschen?")
                                .setMessage("Du kannst das Löschen nicht rückgängig machen. Bist du dir sicher?")
                                .setNegativeButton("Abbrechen", new DialogInterface.OnClickListener() {
                                    @Override
                                    public void onClick(DialogInterface dialog, int which) {
                                        dialog.cancel();
                                    }
                                })
                                .setPositiveButton("OK", new DialogInterface.OnClickListener() {
                                    @Override
                                    public void onClick(DialogInterface dialog, int which) {
                                        FirebaseDatabase.getInstance().getReference().child("chats").child("userchats").child(FirebaseAuth.getInstance().getCurrentUser().getUid()).child(chatsList.get(position).getUseruid()).setValue(null);
                                        FirebaseDatabase.getInstance().getReference().child("chats").child("users").child(FirebaseAuth.getInstance().getCurrentUser().getUid()).child("messages").child(chatsList.get(position).getUseruid()).setValue(null);
                                    }
                                }).setCancelable(true)
                                .show();
                        lv.setAdapter(arrayAdapter);
                        arrayAdapter.notifyDataSetChanged();
                    }
                    if (position2 == 1) {
                        Intent intent = new Intent(context, ViewContact.class);
                        intent.putExtra("useruid", chatsList.get(position).getUseruid());
                        context.startActivity(intent);
                    }
                }
            });
            dialog.show();
            return true;
        }
    });

    ivphoto.setOnClickListener(new View.OnClickListener() {
        @Override
        public void onClick(View v) {
            final Dialog dialog = new Dialog(context);
            dialog.setContentView(R.layout.abcd_profile_pic_dialog_layout);
            ImageView imageView = (ImageView) dialog.findViewById(R.id.alertImage);
            TextView textView = (TextView)dialog.findViewById(R.id.alertdialogtv);
            ImageView message = (ImageView)dialog.findViewById(R.id.alertMessage);
            ImageView profile = (ImageView)dialog.findViewById(R.id.alertProfile);
            profile.setOnClickListener(new View.OnClickListener() {
                @Override
                public void onClick(View v) {
                    Intent intent = new Intent(context, ViewContact.class);
                    intent.putExtra("useruid", chatsList.get(position).getUseruid());
                    context.startActivity(intent);
                    dialog.dismiss();
                }
            });
            message.setOnClickListener(new View.OnClickListener() {
                @Override
                public void onClick(View v) {
                    Intent intent = new Intent(getContext(), Chat_Room.class);
                    intent.putExtra("room_name", chatsList.get(position).getUsername());
                    intent.putExtra("room_uid", chatsList.get(position).getUseruid());
                    context.startActivity(intent);
                }
            });
            Picasso.with(getContext()).load(chatsList.get(position).getPhotoURL()).placeholder(R.drawable.ic_person_grey_round).into(imageView);
            textView.setText(chatsList.get(position).getUsername());
            dialog.setCancelable(true);
            dialog.show();
        }
    });

    return  listViewItem;
}

This is how i got my ArrayLists:

`for(DataSnapshot snapshot : dataSnapshot.getChildren()){
                    username.add(snapshot.child("roomname").getValue().toString());
                    photoURL.add(snapshot.child("photoURL").getValue().toString());
                    lastmessage.add(snapshot.child("lastMessage").getValue().toString());
                    lastmessagetime.add(snapshot.child("lastMessageTime").getValue().toString());
                    useruid.add(snapshot.child("userUiD").getValue().toString());
                }

                ChatAdapter chatAdapter = new ChatAdapter(getActivity(), username, useruid, photoURL, lastmessage, lastmessagetime);
                listView.setAdapter(chatAdapter);`

But how can I pass it as a List ?? How can I add them to the list?

Is it even possible to sort it?

I hope you Guys can help me :) Thanks.

Given two sorted lists (or arrays) and a number k, create an algorithm to fetch the least k numbers of the two lists

Need to find the first 3 smallest number in given two sorted array. I supposed that two array should merge into one first and sort it in order to fetch the first 3 smallest number. Can anyone help me with the merge and sort part or provide some advice, any help will appreciate.

This is where i reached now, I only can get the smallest number ( not first 3, just one).

public class MergeandSort {


public static void main(String[] args) {
    int[] set1 = {1,2,6,9,18};
    int[] set2 = {2,3,7,10,21,30};

    int smallest = set1[0];
    int smallests = set2[0];

    for(int i=0; i < set1.length; i++){
        if(set1[i] < smallest)
            smallest = set1[i];
    }
    for(int k=0; k < set2.length; k++){
        if(set2[k] < smallests)
            smallests = set2[k];
    }

    System.out.println("Smallest Number in Set 1 is : " + smallest);
    System.out.println("Smallest Number in Set 2 is : " + smallests);


}

}

How to sort csv by specific column

I try to sort a csv contain temperatures by the 4th column.

Sort -n -k4 temperature.csv

As a result I get this:

2017-06-24 11:20,23.57,19.0,16.7,0.087,3.615
2017-06-24 11:25,23.51,19.0,16.7,0.087,3.689
2017-06-24 12:45,22.03,19.0,17.1,0.096,4.152
2017-06-24 13:00,21.92,19.0,17.1,0.096,4.229
2017-06-24 14:00,22.22,19.0,17.4,0.197,4.639
2017-06-24 14:25,22.21,19.0,17.5,0.197,4.774
2017-06-24 15:10,22.30,19.0,17.1,0.134,5.472
2017-06-24 16:00,22.42,19.0,17.3,0.134,5.93
2017-06-24 17:45,22.07,21.0,17.0,0.144,6.472
2017-06-24 18:25,21.90,21.0,16.9,0.15,6.814
2017-06-24 19:40,23.01,21.0,16.9,0.318,8.503

As you can see the 4th column isn't sorted correctly. I would expect 17.5 in tbe first line and 16.7 in the last line.

I also tried this:

sort -n -t. -k4,1n temperature.csv

The result is exactly the same as the previous example. Can anyone give me a hint?

Vigenere in Python [CS50]

I hadn't been writing programs for a year now. I might forget how somethings work so I stuck at getting the output right. example:

Given key: abc / Given text: aaa / Expected result: abc / Output: tuv

and can't get rid of the spaces

import sys
import cs50
def main():
    if len(sys.argv) != 2:
        print("missing command-line argument")
        exit(0)
    if sys.argv[1].isalpha() == False:
        print("Yonly letters allowed!")
        exit(1)
    key = sys.argv[1]
    keylen = len(key)
    print("Text: ", end="")
    txt = cs50.get_string()
    print ("New Text: ", end="")
    jey = 0
    for i in range(len(txt)):
        j = ord(key[jey%keylen])
        c = ord(txt[i])
        if (65<=c<=90) == True:
            c = (c - 65 + j) % 26 + 65
            print(chr(c),end ="")
        elif (97<=c<=122) == True:
            c = (c - 97 + j) % 26 + 97
            print(chr(c),end ="")
        else:
            print(txt[i],end="")
        jey+=1      
    print()
if __name__ == "__main__":
    main()

How to repeat characters in array

I am trying to implement Vigenere's Cipher in C but the problem is that when I try to repeat the key used in the array it is in, it breaks after the 4th letter. So if the key is ABC and the plaintext is HELLO, it returns HFNLO instead of HFNLP. When I look at my code it logically makes sense but it seems to just not work. Can anybody see the problem?

Here is the code:

int main(int argc, string argv[])
{
    if(argc != 2)
    {
        printf("usage: ./vigenere k\n");
        return 1;
    }
    //asks for plain text
    printf("plaintext: ");
    string text = get_string();
    string k = argv[1];
    printf("ciphertext: ");

    //checks to see if length of key is shorter than length of plaintext and duplicates it.
    int count = 0;
    while(strlen(k) <= strlen(text))
    {
        k[strlen(k + count)] = k[count];
        count++;
    }

    //changes key to be within 0 - 25 and encrypts plaintext
    for(int i = 0; i < strlen(text); i++)
    {
        if(k[i] >= 'A' && k[i] <= 'Z')
        {
             k[i] = k[i] - 65;
        }
        else if (k[i] >= 'a' && k[i] <= 'z')
        {
            k[i] = k[i] - 97;
        }

        //if statement for plaintext capital letters
        if(text[i] >= 'A' && text[i] <= 'Z')
        {
            text[i] = text[i] - 64;
            text[i] = ((text[i] + k[i]) % 26) + 64;   
        }
        //if statement for plaintext lowercase letters
        else if(text[i] >= 'a' && text[i] <= 'z')
        {
             text[i] = text[i] - 96;
             text[i] = ((text[i] + k[i]) % 26) + 96;   
        }
        //prints final cipher
        printf("%c", text[i]);
    } 
    printf("\n");
    return 0;
}

Cs50 greedy without using <cs50.h>

I am solving the greedy algorithm of cs50 course without using the cs50 header file. I have written a code. It works fine with numbers as input but when I give it a string or alphabets as input it does not prompt me back. I do not know how to solve the issue.

#include <stdio.h>

int main()
{
float c;
int C, nQ, rem1, nD, rem2, nN, rem3;

do
{
    printf("O hai! How much change is owed? ");
    scanf("%f", &c);
}
while(c<0);

C = c * 100;

nQ = C / 25;
rem1 = C % 25;

nD = rem1 / 10;
rem2 = rem1 % 10;

nN = rem2 / 5;
rem3 = rem2 % 5;

printf("%d\n", nQ+nD+nN+rem3);
}

How to counting sort two dimensional array

Hi i have a problem with my code, i try sort array by counting sort (it must be stable sort), but my code doesn't work. I try implemented counting-sort from some wbesite, but it was in c# and I'm not sure s it done correctly. Can you tell me what is wrong with it?

#include <stdio.h>
#include <iostream>

using namespace std;


void sort_with_show(int **a, int rozmiar, int polecenie)
{
    int y, d;
    for (int i = 0; i< rozmiar - 1; i++)
    {
        for (int j = 0; j < rozmiar - 1 - i; j++)
        {
            if (a[j + 1][0] < a[j][0])
            {
                y = a[j][0];
                a[j][0] = a[j + 1][0];
                a[j + 1][0] = y;
            }
        }
    }

    for (int i = 0; i < rozmiar; i++)
    {
    //cout << tablica[i].x << " " << tablica[i].y << "\n";
        if (polecenie == 0)
        {
            cout << a[i][0] << '\n';
        }
        else if (polecenie == 1)
        {
            cout << a[i][0] << "," << a[i][1] << "\n";
        }
    }
}

int main()
{


    int rozmiar = 0;
    int polecenie = 0;

    char t[20] = { '\0' };
    char *p, *q;

    int liczba = 0;
    int calaLiczba = 0;

    bool isY = false;
    cin >> rozmiar;

    int ** a  = new int *[rozmiar];
    for (int i = 0; i < rozmiar; i++)
        a[i] = new int[2];

    cin.ignore();

    int i = 0;
    while(i < rozmiar)
    {
        fgets(t, sizeof t, stdin);

        for (p = t, q = t + sizeof t; p < q; p++)
        {

            if (*p >= 48 && *p <= 57)
            {
                liczba = *p - 48;
                calaLiczba = calaLiczba * 10 + liczba;
            }

            if (*p == ' ')
            {
                a[i][0] = calaLiczba;
                isY = true;
                calaLiczba = 0;
                liczba = 0;
            }

            if (*p == '\n')
            {
                a[i][1] = calaLiczba;
                isY = false;
            }

        }

        for (int j = 0; j < 20; j++)
            t[j] = '\0';

        liczba = 0;
        calaLiczba = 0;
        isY = false;
        i++;
    }

    cin >> polecenie;
    cin.ignore();

    sort_with_show(a, rozmiar, polecenie);
    return 0;
}

Should I use counting sort or any other alterntive for sorting frequncies of symbols complexity wise

I will have an array of symbols(256 ascii symbols) and array of their frequncies(some of the symbols apper zero times).Would it be preferble complexity wise to use counting sort for sorting and what soultion will take more code lines (the code will be written in assembly, tasm). Thanks in advance Doron

Javascript Counting Sort implementation

Is this a good way or the best way to implement Counting Sort in Javascript? Can't find a standard JS Counting Sort example.

function countingSort(arr){
  var helper = []; // This helper will note how many times each number appeared in the arr
                   // Since JS arrary is an object and elements are not continuously stored, helper's Space Complexity minor that n
  for(var i = 0; i<arr.length; i++){
    if(!helper[arr[i]]){
        helper[arr[i]] = 1;
    }else{
        helper[arr[i]] += 1;
    }
  }

  var newArr = []; 
  for(i in helper){
    while(helper[i]>0){
        newArr.push(parseInt(i));
        helper[i]--;
    }
  }
  return newArr; 
}

var arr = [5,4,3,2,1,0];
console.log(countingSort(arr)); // [0, 1, 2, 3, 4, 5]

Related questions

Counting sort in C apparently works but binarysearch doesn't

1 answer

See also questions close to this topic