LinuxQuestions.org
Support LQ: Use code LQ3 and save $3 on Domain Registration
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
LinkBack Search this Thread
Old 07-12-2013, 06:30 AM   #1
Xeratul
Senior Member
 
Registered: Jun 2006
Location: Debian Land
Posts: 1,239

Rep: Reputation: 81
C: A Fastest Array Sorting, faster than bubble sort ?


Hi,

On sorting an array of array, the simplest and well known one is bubble sort.

Would you mind proposing a code that would do similar things but faster?

I dont sort all, just the first chars, herewith:

many thanks

Code:

void sort_bubble( void ) {
  int i , k , j , inversion ; 
  char stringtmpswap[PATH_MAX]; 

  mvprintw(0,0,"Sorting File (Bubble Sort). Please wait (actually long)...");
  refresh();

  for(j=6 ; (j>=0) ; j--)
  {
    inversion=1 ;
    while( inversion == 1 ) {
      inversion = 0 ; 
      for(i=1 ; (i<datalistfile_max_numberitems) ; i++)
      {
        if ( datalistfile[i][j]  >  datalistfile[i+1][j]   )
        {
          strncpy( stringtmpswap , datalistfile[i] , PATH_MAX);
          strncpy(  datalistfile[i] , datalistfile[i+1]  , PATH_MAX);
          strncpy(  datalistfile[i+1] , stringtmpswap  , PATH_MAX);
          inversion=1;
        }

      }
    }
  }
  mvprintw(1,0, "Sorted!! ");
  refresh();
}
 
Old 07-12-2013, 06:35 AM   #2
mina86
Member
 
Registered: Aug 2008
Distribution: Slackware
Posts: 311

Rep: Reputation: 120Reputation: 120
http://en.wikipedia.org/wiki/Sorting_algorithm
 
Old 07-12-2013, 06:47 AM   #3
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.0
Posts: 505
Blog Entries: 2

Rep: Reputation: 67
Quicksort, Mergesort and Heapsort all run faster than bubble sort.

Also, if datalistfile is an array of character pointers rather than character arrays, then you wouldn't need to do all those strncpy's. You could just swap pointers datalistfile[i] and datalistfile[i+1]
 
Old 07-12-2013, 11:39 AM   #4
Xeratul
Senior Member
 
Registered: Jun 2006
Location: Debian Land
Posts: 1,239

Original Poster
Rep: Reputation: 81
Quote:
Originally Posted by psionl0 View Post
Quicksort, Mergesort and Heapsort all run faster than bubble sort.

Also, if datalistfile is an array of character pointers rather than character arrays, then you wouldn't need to do all those strncpy's. You could just swap pointers datalistfile[i] and datalistfile[i+1]
Hi, thanks. In which way would you mean please?
"You could just swap pointers datalistfile[i] and datalistfile[i+1]"
 
Old 07-12-2013, 06:31 PM   #5
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.0
Posts: 505
Blog Entries: 2

Rep: Reputation: 67
Quote:
Originally Posted by Xeratul View Post
Hi, thanks. In which way would you mean please?
"You could just swap pointers datalistfile[i] and datalistfile[i+1]"
Code:
char *datalistfile[datalistfile_max_numberitems], *t;

. . . // allocate memory for strings, read strings, start sort etc

t = datalistfile[i];
datalistfile[i] = datalistfile[i+1];
datalistfile[i+1] = t;

. . .
Of course, unless you are running bubble sort, you would not necessarily be swapping adjacent strings.

EDIT: Looking at your original code, I see that you have written
Code:
for(j=6 ; (j>=0) ; j--)
{
   ... // complete bubble sort
}
No wonder your sort is "(actually long)..."! You are running a complete bubble sort 7 times in succession based on each individual character comparison.

Much better to use
Code:
...
if (strncmp(datalistfile[i] , datalistfile[i+1], 7) > 0) ...

Last edited by psionl0; 07-12-2013 at 06:59 PM.
 
Old 07-12-2013, 07:22 PM   #6
konsolebox
Senior Member
 
Registered: Oct 2005
Distribution: Gentoo, Slackware, LFS
Posts: 2,242
Blog Entries: 15

Rep: Reputation: 233Reputation: 233Reputation: 233
Quicksort is my personal favorite. A concept of it has been discussed well on the book I bought which is A Book on C 4th Edition. I even made an implementation of it for Bash here which now I used in my scripts.
 
Old 07-12-2013, 07:36 PM   #7
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
Quote:
Originally Posted by konsolebox View Post
Quicksort is my personal favorite. A concept of it has been discussed well on the book I bought which is A Book on C 4th Edition. I even made an implementation of it for Bash here which now I used in my scripts.
Quicksort is great, unless you have non-identical elements that compare as equal, in which case you might consider mergesort, which is stable. Contrary to all of the examples I've seen, mergesort can be done without recursion, although it always requires a buffer the same size as the array being sorted and it always performs the max number of steps regardless of the element values.

Kevin Barry
 
Old 07-12-2013, 08:36 PM   #8
konsolebox
Senior Member
 
Registered: Oct 2005
Distribution: Gentoo, Slackware, LFS
Posts: 2,242
Blog Entries: 15

Rep: Reputation: 233Reputation: 233Reputation: 233
Quote:
Originally Posted by ta0kira View Post
Quicksort is great, unless you have non-identical elements that compare as equal
That depends on the material considered and implementation I guess. I haven't seen any trouble with quicksort. If you're referring to objects sorted by identity and serialization I guess that would apply. But for strings or numbers which are common I don't think it will.

---- Add ----

And seeing the comparison of it with mergesort, I see mergesort as a more conservative and less aggressive algorithm, which isn't my taste. I think it was also discussed in the book A Book on C along with Quicksort and if it was I must have had the same reasons why I picked Quicksort over it.

About the problem of possibly having non-identical elements that compare as equal, the fault would already be about the comparer function and not really Quicksort itself.

And thanks to this discussion I found this interesting algorithm: http://en.wikipedia.org/wiki/Introsort.

Last edited by konsolebox; 07-12-2013 at 09:15 PM.
 
Old 07-13-2013, 06:51 AM   #9
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
Quote:
Originally Posted by konsolebox View Post
About the problem of possibly having non-identical elements that compare as equal, the fault would already be about the comparer function and not really Quicksort itself.
Not true. Suppose I have a spreadsheet and I want to sort rows by the values in column A. Suppose rows X and Y have the same value for A, and X comes before Y. With a stable algorithm, X will remain before Y, whereas with an unstable algorithm their order will depend on artifacts of the algorithm. So, with a stable algorithm I can sort with A, then B, then C, and the result will be the same as sorting with C, B, and A all at once, whereas with an unstable algorithm the result will be the same as sorting with only C.

Kevin Barry
 
Old 07-13-2013, 11:30 PM   #10
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.0
Posts: 505
Blog Entries: 2

Rep: Reputation: 67
Quote:
Originally Posted by konsolebox View Post
Quicksort is my personal favorite.
Quicksort seems to be a universal favourite. However, like all comparison-based sorts, the minimum time taken to sort a large set of elements is proportional to N * Log(N) where N is the number of elements. This is much faster than the N^2 time taken by more primitive sorts like Insertion Sort or Bubble Sort but we can do better.

Bucket Sort or Counting Sort can be made to run in linear time since they don't rely on comparisons. Counting sort is also stable since it doesn't change the order of two elements with the same key.

Radix Sort is a method of sorting large integers or strings by doing a counting sort digit by digit starting (usually) with the least significant digit first. http://www.jimloy.com/computer/radix.htm shows a simple demonstration of how a radix sort works.
 
Old 07-14-2013, 07:43 PM   #11
konsolebox
Senior Member
 
Registered: Oct 2005
Distribution: Gentoo, Slackware, LFS
Posts: 2,242
Blog Entries: 15

Rep: Reputation: 233Reputation: 233Reputation: 233
Quote:
Originally Posted by ta0kira View Post
Not true. Suppose I have a spreadsheet and I want to sort rows by the values in column A. Suppose rows X and Y have the same value for A, and X comes before Y. With a stable algorithm, X will remain before Y, whereas with an unstable algorithm their order will depend on artifacts of the algorithm.
Well like I said it would depend on the comparer function. I don't see it essential to consider the original order of two similar values unless the object in which they belong like in a link list of a set of cells within a row would be affected. If that is the case the comparer function would have to consider as well the original order of those two objects within that list. If the object is arranged through sort IDs instead of lists which is rare then the function would also have to consider the ID.

If an initial mapping is still required to make that work then perhaps you're correct.

Quote:
So, with a stable algorithm I can sort with A, then B, then C, and the result will be the same as sorting with C, B, and A all at once, whereas with an unstable algorithm the result will be the same as sorting with only C.
It seems only that it would be easier to implement or is more natural on stable sorts.
 
Old 07-14-2013, 08:05 PM   #12
konsolebox
Senior Member
 
Registered: Oct 2005
Distribution: Gentoo, Slackware, LFS
Posts: 2,242
Blog Entries: 15

Rep: Reputation: 233Reputation: 233Reputation: 233
Quote:
Originally Posted by psionl0 View Post
Quicksort seems to be a universal favourite. but we can do better.
Well Quicksort has been invented in 1960 so it's no longer unusual to seee better algorithms or improved variations of it. I did said that it was my favorite, but it doesn't mean that I'm no longer expecting other better algorithms over it.

Yet again if I would consider the balance between complexity of implementation and speed, with natural elements I would go for Quicksort.

Mergesort seems to be something to be considered with objects and linked lists.
 
Old 07-14-2013, 11:10 PM   #13
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,042

Rep: Reputation: 952Reputation: 952Reputation: 952Reputation: 952Reputation: 952Reputation: 952Reputation: 952Reputation: 952
Dr. Knuth wrote an entire book called Sorting and Searching.
 
Old 07-15-2013, 07:41 AM   #14
mina86
Member
 
Registered: Aug 2008
Distribution: Slackware
Posts: 311

Rep: Reputation: 120Reputation: 120
Really? No one mentioned that QuickSort is O(n^2) yet?[1] In the worst case it degenerates to select sort. That's why I much prefer Heap Sort (if I don't care if sorting is stable, but even if I do, I would probably just number the elements and sort by double key).

[1] Unless one uses median of medians approach, but then it's just ugly for my taste.

Last edited by mina86; 07-15-2013 at 07:43 AM.
 
Old 07-15-2013, 08:32 AM   #15
johnsfine
Senior Member
 
Registered: Dec 2007
Distribution: Centos
Posts: 4,963

Rep: Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073Reputation: 1073
Quote:
Originally Posted by sundialsvcs View Post
Dr. Knuth wrote an entire book called Sorting and Searching.
I learned about sorting from that book long ago. But I wouldn't recommend it.
He does a poor job of describing the methods. He focuses on the analysis of the performance. For a mathematician planning to invent a new sorting method, that focus on analysis is an important starting point.

For a software engineer planning to select and code a sorting method, you want a clear description of the method and a clear description of the performance bottom line reached from all that analysis. Knuth's pseudo code implementations are all lame and his performance analysis math may be better than I would do, but it is just a distraction from algorithm plus bottom line performance that I would want.

Before the internet, Knuth was the best you could easily find in an ordinary library. After the internet existed, it was time to forget Knuth.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
bubble sort without expected output [C] isamuede Programming 6 01-06-2012 03:30 PM
[SOLVED] problem with bubble sort for array of double bvkim Programming 1 05-10-2010 02:05 AM
selection sort compiles but does not sort the array as desired ganesha Programming 2 04-20-2008 07:44 AM
bubble sorting a linked list - what's wrong with this code ? indian Programming 11 08-06-2006 07:25 AM
Bubble sort? Becks Programming 4 09-12-2003 01:28 PM


All times are GMT -5. The time now is 02:06 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration