help with Bubble Sort

Log in or register to post comments
Go To Last Post
32 posts / 0 new
Author
Message
Fianawarrior
Fianawarrior's picture
Level: Posting Freak
Joined: Wed. Jun 11, 2008
Posts: 1682 View posts
Location: Belfast, Ireland
#1
Posted by Fianawarrior: Tue. Jul 16, 2019 - 02:49 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0


Guys, i'm working on a bubble sort and its only resulting in a semi sorted list.  Long file names are not being sorted properly.

 

	for (l = 0; l < entry_nr; l++) {
		for (j = 0; j < entry_nr - 1; j++) {

			// compare strings
			if (strcmp(data[j].strings[j], data[j + 1].strings[j + 1]) > 0) {

				    strcpy(temp, data[j].strings[j]);

			            strcpy(data[j].strings[j], data[j + 1].strings[j + 1]);
		        	    strcpy(data[j + 1].strings[j + 1], temp);
	         }
	    }
	}

 

The Bubble sort results in a sorted list but long file names are not sorted properly.  See below:

 

This topic has a solution.

Tags:

Tools, Compilers and General Programming, solved, clang
Last Edited: Tue. Jul 16, 2019 - 03:40 PM
Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 102874 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
This reply has been marked as the solution. 
Posted by clawson: Tue. Jul 16, 2019 - 03:28 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

Fianawarrior wrote:
but long file names are not sorted properly.
Define "properly". In the picture I see (first characters only)

 

N, N, S, n, o, s,, t, t

 

N, a, b, n, o, t

 

Given that ASCII character order is (roughly):

 

0..9, A..Z, a..z

 

then they ARE in correct order aren't they? I wonder if you might want to convert everything to either all upper or all lower case during the sort?

 

In a POSIX OS you should have access to strcasecmp(). In the MS world it's probably _stricmp()

Top
Simonetta
Simonetta's picture
Level: Raving Lunatic
Joined: Wed. Mar 12, 2003
Posts: 3217 View posts
Location: Portland, Oregon USA
Posted by Simonetta: Tue. Jul 16, 2019 - 04:09 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You have an incomprehensible data structure in your sort loop.  What exactly does this mean?:

data[j].strings[j], data[j + 1].strings[j + 1]) > 0)

It should be:

    for (OuterIndex = 0; OuterIndex < entry_nr; OuterIndex++) {
       for (InsideIndex = 0; InsideIndex< entry_nr - 1;  InsideIndex++) {
          if (strcmp(strings[InsideIndex], strings[InsideIndex+ 1]) > 0) {
                strcpy(temp, strings[InsideIndex]);
                strcpy(strings[InsideIndex], strings[InsideIndex + 1]);
                strcpy(strings[InsideIndex + 1], temp);
          }
       }
    }
Top
Fianawarrior
Fianawarrior's picture
Level: Posting Freak
Joined: Wed. Jun 11, 2008
Posts: 1682 View posts
Location: Belfast, Ireland
Posted by Fianawarrior: Tue. Jul 16, 2019 - 04:32 PM (Reply to #3)
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0


Hi Simonetta, I had to remove a lot of code before presenting it here.  When sorting the list I needed to also carry other data around with the strings, such as directory info.

 

Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 102874 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Tue. Jul 16, 2019 - 04:50 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
for (l = 0; l < entry_nr; l++) {

BTW, that's about the nastiest C I have seen in a long time. frown

 

Who in their right mind would use lower case L as a variable name? 

Top
Fianawarrior
Fianawarrior's picture
Level: Posting Freak
Joined: Wed. Jun 11, 2008
Posts: 1682 View posts
Location: Belfast, Ireland
Posted by Fianawarrior: Tue. Jul 16, 2019 - 04:56 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:

for (l = 0; l < entry_nr; l++) {

BTW, that's about the nastiest C I have seen in a long time. frown

 

Who in their right mind would use lower case L as a variable name? 

 

mr! lmfao.  Okay, you have a point.  but it was the quickest decision in finding a suitable loop counter. 

 

 

 

Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 102874 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Tue. Jul 16, 2019 - 05:05 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

a,b,c, ...  i,j,k ... x,y,z

 

Anything has to be better than l surely?

 

(while i is ubiquitous the jury is still out on that one)

 

Coincidentally today, while doing a peer code review, I came across use of both ii and i1 as iterators - wasn't very keen on either of those too! They'd been used to avoid a name clash with the plain i in the outer loop.

 

Things like "byte_counter", "string_index" and so on tell the reader/maintainer far more about what for() loop iterators are being used for. I suppose it's a bit more typing and multiple use of the iterator can start to look complex.

 

(never really mind x and y though assuming we're talking about pixels!)

Top
MrKendo
MrKendo's picture
Level: Resident
Joined: Mon. Nov 19, 2018
Posts: 567 View posts
Posted by MrKendo: Tue. Jul 16, 2019 - 06:15 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You're doing more loops than you need.

If you had 4 items, max number of compares you need would be

01 12 23

01 12

01

I think you're doing

01 12 23

01 12 23

01 12 23

01 12 23

Top
Torby
Torby's picture
Level: 10k+ Postman
Joined: Tue. Nov 11, 2003
Posts: 10389 View posts
Location: Bartlesville Oklahoma USA
Posted by Torby: Tue. Jul 16, 2019 - 06:30 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

hint:

 

There's a quicksort function built into the libraries.

If you don't know my whole story, keep your mouth shut.

If you know my whole story, you're an accomplice. Keep your mouth shut. 

Top
Bronze Marktheusch
theusch's picture
Level: 10k+ Postman
Joined: Mon. Feb 19, 2001
Posts: 40257 View posts
Location: Wisconsin USA
Posted by theusch: Tue. Jul 16, 2019 - 07:21 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0


Fianawarrior wrote:
... but long file names are not ...

Smiting from the patent holder...

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

Top
avrcandies
avrcandies's picture
Level: Raving Lunatic
Joined: Wed. Jun 30, 2004
Posts: 7376 View posts
Location: Cincinnati Oh
Posted by avrcandies: Tue. Jul 16, 2019 - 07:57 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

 

I hate when the names are long & similar to others...they should be as distinct (and easily discerned) as possible 

 

BLAH:

led35mx_inp4a3acal_switch = 23;

led35mx_inp4b3acal_switch = 45;

led35nx_inp4a3acal_switch = 76;

led35mx_inp4a3bcal_switch = 29;

led35nx_inp4b3acal_switch = 47;

led35mx_inp3b4acal_switch = 28;

 

Someone gave me a bunch of code with many very similar names scattered all around...thank goodness for automatic highlighting!  My eyes hurt after 5 minutes...always on the edge of making a hard to find mistake!

 

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

Top
christop
christop's picture
Level: Hangaround
Joined: Fri. Jan 28, 2011
Posts: 377 View posts
Location: Arizona, USA
Posted by christop: Tue. Jul 16, 2019 - 08:40 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Torby wrote:

hint:

 

There's a quicksort function built into the libraries.

 

I'll second that. Use qsort with a custom comparator function.

 

Pedantic mode on: qsort does not necessarily use the Quicksort sorting algorithm, but generally you can expect it to use a fast algorithm (certainly faster than bubble sort!).

 

Top
barnacle
barnacle's picture
Level: Raving Lunatic
Joined: Tue. Jan 3, 2006
Posts: 6869 View posts
Location: Berlin DE
Posted by barnacle: Thu. Jul 18, 2019 - 05:00 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

But otherwise, as pointed out earlier, assuming that the screen grab was the result of two separate sort attempts with different inputs, it is correctly sorted per ASCII. Which is what Cliff pointed out earlier. And since you'll probably use strcmp() as the custom comparator function in qsort() you'll end up with the same result, only faster :)

 

strcmp() sorts by ASCII values. Some ASCII values - 0x30 = '0', 0x39 = '9', 0x41 = 'A', 0x5A = 'Z'; 0x61 = 'a'; 0x7A = 'z' (check out a convenient table at http://www.asciitable.com) so you can see why something starting with a capital letter will return that string as being shorter than something with the same letter in lower case. The comparison method also means that a shorter word such as 'bed' will always be considered of lower value than a longer which shares characters with it (e.g. beds). The comparison is performed letter by letter starting from the left and the order depends on the order of the first characters which are different; in this case the 'logical' comparison is the string end marker 0x00 vs 's', 0x73 (though the actual implementation probably doesn't do it quite like that).

 

Neil

Neil Barnes
www.nailed-barnacle.co.uk

Top
MarkThomas
MarkThomas's picture
Level: Posting Freak
Joined: Sat. Sep 3, 2011
Posts: 1830 View posts
Location: San Francisco
Posted by MarkThomas: Thu. Jul 18, 2019 - 05:50 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
Anything has to be better than l surely?

I have to admit to using "i" for loop index by nature from FORTRAN days where ints were i - n and variable name length was an issue, but you may not be old enough to remember that.  I did have a problem once typing a "1" instead of an "i".  It has never occurred to me to use anything but "i" for loop index after doing it for 50 years, and working on a LOT of other people's code for as long who all did the same.  That's what "i" is used for.  Now I am going to have to rethink all my code going forward.  Thanks a lot, Cliff!  But you really dont have to be so supercilious about it.

Top
kk6gm
kk6gm's picture
Level: Raving Lunatic
Joined: Fri. Sep 11, 2009
Posts: 3981 View posts
Location: Sacramento, CA
Posted by kk6gm: Thu. Jul 18, 2019 - 06:24 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

MarkThomas wrote:
I have to admit to using "i" for loop index by nature from FORTRAN days where ints were i - n and variable name length was an issue

Capital L is obviously not a problem, but small l, well....

Top
avrcandies
avrcandies's picture
Level: Raving Lunatic
Joined: Wed. Jun 30, 2004
Posts: 7376 View posts
Location: Cincinnati Oh
Posted by avrcandies: Thu. Jul 18, 2019 - 07:39 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Always use something searchable...if you need to search a file for some reason looking for "i" or "e" will give a baziliion wrong hits, but  battery_sample_num  is probably going to find what you intend to find (even "bsn" is better than  "i", if you despise typing).

 

 

 

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

Top
MarkThomas
MarkThomas's picture
Level: Posting Freak
Joined: Sat. Sep 3, 2011
Posts: 1830 View posts
Location: San Francisco
Posted by MarkThomas: Thu. Jul 18, 2019 - 07:42 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

kk6gm wrote:
Capital L is obviously not a problem, but small l, well....

I dont do that any more.  I learned my lesson.  Now I am more likely to use "ii".  I seem to remember in the FORTRAN days there was no distinction between upper and lower case, but that was 40 some years ago and my memory is gradually fading away.

Top
MarkThomas
MarkThomas's picture
Level: Posting Freak
Joined: Sat. Sep 3, 2011
Posts: 1830 View posts
Location: San Francisco
Posted by MarkThomas: Thu. Jul 18, 2019 - 08:01 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

avrcandies wrote:
Always use something searchable...if you need to search a file for some reason looking for "i" or "e" will give a baziliion wrong hits, but  battery_sample_num  is probably going to find what you intend to find (even "bsn" is better than  "i", if you despise typing).

I can search on " i " and find all my loops.  I am very conscientious about how I use white space.  If I am looking for a particular bit of code I search on variable names or method names, being of the school that code be self documenting, and I never put comments in line with the code when one is needed for a particular tricky bit of algorithm.  Always off to the side.  Being in line just makes the code harder to read and is distracting.

Top
avr-mike
avr-mike's picture
Level: Resident
Joined: Sat. Jul 21, 2018
Posts: 865 View posts
Location: U.S. Pacific
Posted by avr-mike: Thu. Jul 18, 2019 - 09:52 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Even though I use long names like battery_sample_num

for variables, I'll still use 'i' as a loop variable.  I find it's

easier to read this:

for (int i=1; i<10; ++i) {
    battery_sample[i-1] = battery_sample[i];
}

than this:

for (int battery_sample_num = 1; battery_sample_num < 10; ++battery_sample_num) {
    battery_sample[battery_sample_num - 1] = battery_sample[battery_sample_num];
}

 

As always, these are questions of style and people disagree.

I even disagree with my own style from last year at times!

 

--Mike

 

Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 102874 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Thu. Jul 18, 2019 - 10:40 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This very thread proves the issue beyond doubt. I was not objecting to lower case India but to lower case Lima which is too similar to digit One.

Top
MarkThomas
MarkThomas's picture
Level: Posting Freak
Joined: Sat. Sep 3, 2011
Posts: 1830 View posts
Location: San Francisco
Posted by MarkThomas: Thu. Jul 18, 2019 - 11:04 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

avr-mike wrote:

Even though I use long names like battery_sample_num

for variables, I'll still use 'i' as a loop variable.  I find it's

easier to read this:

for (int i=1; i<10; ++i) {
    battery_sample[i-1] = battery_sample[i];
}

I almost always use spaces around operators, except ++ or --, so I would write:

for (int i = 1; i < 10; i++)
{
    battery_sample[i - 1] = battery_sample[i]  // or maybe for clarity i would use [i-1]  for verydense code with lots of index manipulation I sometimes leave out the spaces 
}

For += and -= I always use the space:  i += 12;   j -= 11;  It is just easier to read for me.  One company I worked for had a style manual we were supposed to follow for our code.  It was mostly stuff I did anyway, so I didn't break the rules too often.

Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 102874 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Fri. Jul 19, 2019 - 08:47 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

MarkThomas wrote:
I almost always use spaces around operators,
Me too - the coding standard I've used for the last 20+ years mandates it ;-)

Top
Torby
Torby's picture
Level: 10k+ Postman
Joined: Tue. Nov 11, 2003
Posts: 10389 View posts
Location: Bartlesville Oklahoma USA
Posted by Torby: Fri. Jul 19, 2019 - 01:10 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

MarkThomas wrote:

clawson wrote:
Anything has to be better than l surely?

I have to admit to using "i" for loop index by nature from FORTRAN days where ints were i - n and variable name length was an issue, but you may not be old enough to remember that.  I did have a problem once typing a "1" instead of an "i".  It has never occurred to me to use anything but "i" for loop index after doing it for 50 years, and working on a LOT of other people's code for as long who all did the same.  That's what "i" is used for.  Now I am going to have to rethink all my code going forward.  Thanks a lot, Cliff!  But you really dont have to be so supercilious about it.

 

A coworker is out to correct all my carefully acquired bad programming habits.

If you don't know my whole story, keep your mouth shut.

If you know my whole story, you're an accomplice. Keep your mouth shut. 

Top
gchapman
gchapman's picture
Level: 10k+ Postman
Joined: Tue. Jan 9, 2007
Posts: 14805 View posts
Location: Clay County, Texas, u.S.A.
Posted by gchapman: Fri. Jul 19, 2019 - 01:29 PM (Reply to #21)
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

MarkThomas wrote:
One company I worked for had a style manual we were supposed to follow for our code.  It was mostly stuff I did anyway, so I didn't break the rules too often.

Fight a war over design issues, not style. - Jack Ganssle

via

The Embedded Muse 353 - Tools and Tips

...

 

Daniel Wisehart responded to my comments on MISRA-C:

...

A Clang pretty printer with VCS interfaces and IDE plug-ins or extensions :

ClangFormat — Clang 10 documentation

 

"Dare to be naïve." - Buckminster Fuller

Top
barnacle
barnacle's picture
Level: Raving Lunatic
Joined: Tue. Jan 3, 2006
Posts: 6869 View posts
Location: Berlin DE
Posted by barnacle: Fri. Jul 19, 2019 - 04:13 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You're all missing the point: the loop counter should of course be 'q'...cheeky

 

Neil

Neil Barnes
www.nailed-barnacle.co.uk

Top
MarkThomas
MarkThomas's picture
Level: Posting Freak
Joined: Sat. Sep 3, 2011
Posts: 1830 View posts
Location: San Francisco
Posted by MarkThomas: Fri. Jul 19, 2019 - 09:29 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

barnacle wrote:

You're all missing the point: the loop counter should of course be 'q'...cheeky

 

Neil

 

What a good idea.  I currently use 'q' as a command to quiet UART to get timings without all the time spent talking to PuTTY, but that is an easy change.  Neil, you are a genius and an original thinker.

Top
Bronze Marktheusch
theusch's picture
Level: 10k+ Postman
Joined: Mon. Feb 19, 2001
Posts: 40257 View posts
Location: Wisconsin USA
Posted by theusch: Fri. Jul 19, 2019 - 10:54 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0


barnacle wrote:

You're all missing the point: the loop counter should of course be 'q'...cheeky

 

Neil

???  Y'all are losing me. 

 

 

[side note:  I'm of the age where loop counters should obviously be i - j - k]

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

Top
barnacle
barnacle's picture
Level: Raving Lunatic
Joined: Tue. Jan 3, 2006
Posts: 6869 View posts
Location: Berlin DE
Posted by barnacle: Sat. Jul 20, 2019 - 01:26 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Personal taste/choice. I suspect I started using them when I was modelling digital filters, where i, j, k tend to have domain specific understanding. I do prefer for loop counters where the counter name itself isn't particularly important to use q, r, s, t with a comment if required.

 

    ... // blah blah
    // don't compile this tight timing loop away mr compiler!
    for (volatile uint8_t q = 0; q < 10; q++)
    {
        // nothing to see here
    }
    
    // versus
    for (volatile uint8_t hard_counter = 0; hard_counter < 10; hard_counter++)
    {
        // nothing to see here
    }

Neil

Neil Barnes
www.nailed-barnacle.co.uk

Top
avrcandies
avrcandies's picture
Level: Raving Lunatic
Joined: Wed. Jun 30, 2004
Posts: 7376 View posts
Location: Cincinnati Oh
Posted by avrcandies: Sun. Jul 21, 2019 - 07:57 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You can cause some interference issues if you use i (and j)  as a variable in Matlab...please don't (just save the world)

 

Avoid Using i and j for Variables

MATLAB uses the characters ii and j to represent imaginary units. Avoid using ii and jj for variable names if you intend to use them in complex arithmetic.

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

Top
Scroungre
Scroungre's picture
Level: Posting Freak
Joined: Wed. Apr 18, 2007
Posts: 1556 View posts
Location: Southern California
Posted by Scroungre: Mon. Jul 22, 2019 - 05:24 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I suppose it would be rude to point out that I like to use loop counters "r18" and "r19". cheeky  S.

Top
Torby
Torby's picture
Level: 10k+ Postman
Joined: Tue. Nov 11, 2003
Posts: 10389 View posts
Location: Bartlesville Oklahoma USA
Posted by Torby: Mon. Jul 22, 2019 - 01:22 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

theusch wrote:

barnacle wrote:

You're all missing the point: the loop counter should of course be 'q'...cheeky

 

Neil

???  Y'all are losing me. 

 

 

[side note:  I'm of the age where loop counters should obviously be i - j - k]

 

Or maybe a James Bond reference?

If you don't know my whole story, keep your mouth shut.

If you know my whole story, you're an accomplice. Keep your mouth shut. 

Top
meslomp
meslomp's picture
Level: Raving Lunatic
Joined: Wed. May 2, 2007
Posts: 6510 View posts
Location: Nieuwegein, Netherlands
Posted by meslomp: Tue. Jul 23, 2019 - 05:11 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Torby wrote:

theusch wrote:

barnacle wrote:

You're all missing the point: the loop counter should of course be 'q'...cheeky

 

Neil

???  Y'all are losing me. 

 

 

[side note:  I'm of the age where loop counters should obviously be i - j - k]

 

Or maybe a James Bond reference?

my first thought went to "Q & Q"  but a quick wiki search resulted in the conclusion that people knowing that had to be dutch as it was a dutch series, hahahahaha

Top