• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Bear Bibeault
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Jj Roberts
  • Carey Brown
Bartenders:
  • salvin francis
  • Frits Walraven
  • Piet Souris

Bubble Sort DNA Sorting

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi, I have a problem with my code about bubble sort for alphabet sorting in dna. It must sort according to ``most sorted'' to ``least sorted''. The first line contains two integers: a positive integer n (0 < n ≤ 1000) giving the length of the strings; and a positive integer m (0 < m ≤ 1000) giving the number of strings. These are followed by m lines, each containing a string of length n.

Here is my code.


       
Could someone help me ?
 
Bartender
Posts: 4272
160
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
When is a String more sorted than another String?
 
Piet Souris
Bartender
Posts: 4272
160
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And welcome to the Ranch!
 
Piet Souris
Bartender
Posts: 4272
160
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, just had a closer look at your code. My question was superfluous, since a String is more sorted when the number of inversions is less than another string (an inversion in this case is when a character is followed somewhere by a smaller character).

Now, you have two nested loops for finding the number of inversions, and that is oke (there is a faster way though), but it makes the code a bit hard to follow. Also, it is tied to the four letters of a DNA, and becomes tedious when there are more characters possible.
So, why not refactor the code first?

Here is a method that counts the inversions of a String, given a character c:

Can you build from this the method: private static int nrOfInversions(String s)?

Then, your names are not the best. For instance: dna1 is the size of the input, but you wouldn't say that given that name! 'sizeOfInput' would be much more clear. Likewise for the name 'sizeCharacter'.

But what I think is the problem (can't test your code by lack of input) is that you have two parallel arrays: one containing the inputstrings, and one containing the number of inversions for these strings. Then, based on that second array, you sort the first array. However, if you swap two strings, then you should likewise also swap the corresponding nrOfInversions, otherwise the two arrays get out of sync.

Keeping two arrays in sync is not a pretty task, that's why you should avoid such a construct at all cost.

Do you know about HashMaps? If so, what about a HashMap<String, Integer> where the keys are the input strings and the Integer is the number of inversions of that string. Having this map, you can then bubblesort your array of strings by looking up their inversions in the map. Give it a try!

 
reply
    Bookmark Topic Watch Topic
  • New Topic