LinuxQuestions.org
Share your knowledge at the LQ Wiki.
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
 
Search this Thread
Old 01-27-2005, 05:16 AM   #1
nodger
Member
 
Registered: Oct 2003
Location: Ireland
Distribution: Slackware 9.1, Ubuntu
Posts: 192

Rep: Reputation: 30
Which sorting algorithm?


I need a sorting algorithm that doesn't take long if the set is nearly sorted already, does qsort and mergesort do this?
 
Old 01-27-2005, 06:36 AM   #2
ilikejam
Senior Member
 
Registered: Aug 2003
Location: Glasgow
Distribution: Fedora / Solaris
Posts: 3,109

Rep: Reputation: 96
A bubble sort might be the thing. Overall, it's rubbish, but it gets quite fast near the end of the sort. I think it might have the edge over a quicksort.

Dave
 
Old 01-27-2005, 07:33 AM   #3
jtshaw
Senior Member
 
Registered: Nov 2000
Location: Seattle, WA USA
Distribution: Ubuntu @ Home, RHEL @ Work
Posts: 3,892
Blog Entries: 1

Rep: Reputation: 66
I would use a merge sort or a quick sort personally, but performance is highly dependant on how the data happens to fall.

I've found in real world performance the bubble sort rarely, if ever, will touch the performance of merge sort or quick sort, though I'm sure with some specifically structured datasets we could show bubble sort to be quite fast.
 
Old 01-27-2005, 09:47 AM   #4
jim mcnamara
Member
 
Registered: May 2002
Posts: 964

Rep: Reputation: 34
Your best solution:
try a known C library function like qsort, first. You are less likely to have problems later on. qsort has been beat on for 15+ years. Most of the problems have long since been chased out.

Test it on real data, not programmer data. If it works okay, don't worry about squeezing an extra five seconds off run-time. It is not worth your time.

If you are in a big production environment, look for commercial libraries like syncsort. Don't try to write a linear time sort on your own.
 
Old 01-28-2005, 06:26 AM   #5
nodger
Member
 
Registered: Oct 2003
Location: Ireland
Distribution: Slackware 9.1, Ubuntu
Posts: 192

Original Poster
Rep: Reputation: 30
The set would be something like this:

1 3 6 8 11 12 16 22 25 30 31 32 35 37 41 7 15 44 2

IE. Theres 20 numbers and the first 15 are sorted but the remaining 5 are still jumbled.
In reality it might be the first 99% of them are sorted, or something like that. I'm not in a big production enviornment, so I can't afford commercial licences.
 
Old 01-28-2005, 01:40 PM   #6
jim mcnamara
Member
 
Registered: May 2002
Posts: 964

Rep: Reputation: 34
try qsort().
 
Old 01-28-2005, 06:13 PM   #7
gamehack
Member
 
Registered: Jun 2003
Location: Sevenoaks, UK
Distribution: Ubuntu
Posts: 183

Rep: Reputation: 30
Check this out http://www.cplusplus.com/ref/cstdlib/qsort.html
 
  


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


Similar Threads
Thread Thread Starter Forum Replies Last Post
Airsnort Algorithm inthefuture Linux - Security 1 08-26-2004 10:01 PM
Do you memorize the algorithm?For... shakedown1987 Programming 5 08-05-2004 07:21 AM
Sorting Beppe83 Linux - Software 7 06-21-2004 09:10 AM
huffman algorithm mcshen Programming 3 03-12-2004 02:00 PM
assistance with an algorithm mandrake_linux Programming 3 07-27-2001 04:03 AM


All times are GMT -5. The time now is 08:50 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