programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# I have an algorithm for a sorting program but I don't know how to write it?

Greenhorn
Posts: 26
Righto. So, here's a fun one. I've been given an algorithm and instructions. I've also been giving key points and what I should end up with. It's on me to figure out how to write it. I think I got part of it, but some parts I'm not entirely sure how I would go about doing.

So let's say I have an array of random integers from 1-9. Roughly 20 integers are in this array. So, first I need to count how many times a number occurs in this array and put this into a new count[] array. count[] will only ever have 9 elements in it and each element corresponds to the number of times an element in the original array appears. So let's say in the original array (hereby referred to as a[]) the number 1 occurs 4 times, 2 once, 3 twice, and so on and so forth. count[0] would have 4, count[1] would have 1, and count[2] would have 2. I need to form an array count of 9 elements such that count[i-1] contains the number of times that i occurs in the array to be sorted.

Now once I do that, I need to use that data to form a new array. This new array is going to use the data from both of the first 2 arrays to create a sorted expanded array. So, like above, we said that 1 occurs 4 times? So in this new array new[] it would display 4 1's. So based off our original example new[] would end up with [1, 1, 1, 1, 2, 3, 3].

Now the data to use differs because it isn't really relevant, it's the functionality that is. Any suggestions on what can lead me in the right direction?

(Let me know if my explanation doesn't make sense)

Sheriff
Posts: 11494
180
I suggest you post some code so we can see what you've tried so far.

W Wilson
Greenhorn
Posts: 26
I don't have much so far because I'm trying to think of the current step. I have to determine the amount of times an element exists in the length of the array. So, figuring out how many times 1 exists, how many times 2 exists. And then I create an array based on this information where the index 0-8 represents how many times a number 1-9 exists in the original array. Sadly, I'm restricted to an array so I cant use like an ArrayList.

I'm not really good at this yet =P

Bartender
Posts: 4568
9
An array is fine here. You know already how big the count and sorted arrays have to be, don't you? So create them that size in the first place.

Inside the loop, all you need to do is increment the correct index of the count array.

Junilu Lacar
Sheriff
Posts: 11494
180
Standard advice applies here: StopCoding (←click) and do it manually, with a pencil and paper. You can do it several times if you want but you have to do it step-by-step and note what you're doing, so you can translate that into instructions that a computer can follow. If you can come up with instructions that even your grandmother or a 10-year-old child can follow to solve this manually, then you can translate those into instructions that a computer can follow.

lowercase baba
Bartender
Posts: 12565
49
first I need to count how many times a number occurs in this array

Right there. That is where you start. Given an array, and given a number, count how many times that number appears in the array. At the moment, you don't care where that number comes from, or where that array comes from. But assuming you have them, work this out.

put another way...someone hands you these two things, and you give them back one thing...that sounds like...a method!!!

The idea is to break down your huge project into smaller, more manageable pieces. then you assemble those pieces up into your larger program.

W Wilson
Greenhorn
Posts: 26
Update: Stopped, thought a little about it. I've managed to set up a method that counts how many of each integer exists within the original array. Now the problem is that I don't know how to use this information and put it into an array count[] so that count only has 9 integers (1-9) and how many times they occur.

Still no clue on how to do the sorting but I'll cross that bridge when I come to it. Here's what I've got so far:

Marshal
Posts: 56600
172
There is something wrong with the nine count calls. You can write a loop so you call it nine times but only write it once.

you should try putting all that lot into an array with pencil and paper, and once you have worked out how to do it on paper it is usually easy to convert it to code.

Ranch Hand
Posts: 411
5
From looking at your last post I would like to point out a few things to you:

1. Anytime you want to perform an operation more than once, the first thing should come to mind is using a looping construct.
2. When creating a method it should be created to perform no more than one operation which is the operation stated by its name.

Taking these points into consideration you'll end up with clean and maintainable code...

Illustration:

Master Rancher
Posts: 2045
75
@ w wilson:

in your opening post, you write:

"Now the data to use differs because it isn't really relevant, it's the functionality that is."

Now, all routines and advices given so far work for integers in the range 0 to 9. Can you
explain in a little more detail what this 'other data' might be?

Greetz,
Piet

Junilu Lacar
Sheriff
Posts: 11494
180
Piet, I think all he means is that the length of the input array can be different. So the size of your input array can be anywhere from 5 to 555 to whatever elements but the value of any element will always be a number from 0 to 9.