Advertisement

05.16.2008 at 09:39AM PDT, ID: 23408923
[x]
Attachment Details
[x]
The Solution Rating System

With so many solutions, how can you tell which solutions are most likely to help you and which ones are not? To provide you with a tool to use, we rate our solutions based on various elements that most accurately determine if a solution is a quality solution. To explain what factors affect the solution rating, here are the elements we take into consideration when formulating our solution rating.

  • The Grade of the Solution
  • The Zone Rank of the Expert Providing the Solution
  • The Number of Author and Expert Comments
  • The Number of Experts Contributing
  • The Feedback of the Community

Your Input Matters
Because of the way the system is set up, the most important variable in this equation is you. As a member of Experts Exchange, you are able to cast your vote on the quality of the solutions in regard to how complete, accurate, helpful and easy to understand each solution is. When you provide your feedback, each rating is adjusted accordingly. So, if you see a solution that has a poor rating that you think is a good solution, let us know by rating it. As you do, the rating will be adjusted and will become more accurate for other members of our site.

If you have any suggestions that you would like to make for our rating system, please ask a question in the Suggestions Zone of Community Support.

Thank you!

Infinite Sort

Zone: Algorithms
Hi All,

Many modern sort routine have as a parameter, a function that will be called to compare two objects.  Now suppose that the compare function has an error.  It's making a nonsense compare so that the return value is meaningless.

Does anyone know of a sort algorithm that, when corrupted by a meaningless comparison, will go into an infinite loop trying to resolve the sort?


Kent
Start your free trial to view this solution
Question Stats
Zone: Programming
Question Asked By: Kdo
Solution Provided By: Infinity08
Participating Experts: 2
Solution Grade: A
Views: 0
Translate:
Loading Advertisement...
05.16.2008 at 10:03AM PDT, ID: 21584438

Rank: Master

All comments and solutions are available to Premium Service Members only.

Start your 7-day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
05.16.2008 at 12:36PM PDT, ID: 21585748

All comments and solutions are available to Premium Service Members only.

Start your 7-day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
05.16.2008 at 12:56PM PDT, ID: 21585917

Rank: Guru

All comments and solutions are available to Premium Service Members only.

Start your 7-day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
05.16.2008 at 01:25PM PDT, ID: 21586157

Rank: Guru

All comments and solutions are available to Premium Service Members only.

Start your 7-day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
05.16.2008 at 01:38PM PDT, ID: 21586268

Rank: Master

All comments and solutions are available to Premium Service Members only.

Start your 7-day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
05.31.2008 at 07:31AM PDT, ID: 21683839

All comments and solutions are available to Premium Service Members only.

Start your 7-day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
 
Loading Advertisement...
Microsoft
  • Internet Protocols
  • Applications
  • Development
  • OS
  • Hardware
  • Windows Security
Apple
  • Operating Systems
  • Hardware
  • Programming
  • Networking
  • Software
Internet
  • Search Engines
  • File Sharing
  • WebTrends / Stats
  • Spy / Ad Blockers
  • Web Browsers
  • New Net Users
  • Web Development
  • Chat / IM
  • Anti Spam
  • Web Servers
  • Anti-Virus
  • Email Clients
Gamers
  • Tips
  • Online / MMORPG
  • Puzzle
  • Emulators
  • Action / Adventure
  • Role Playing
  • Consoles
  • Game Programming
  • Strategy
  • Sports
  • Misc
  • Computer Games
Digital Living
  • Hardware
  • Automotive
  • New Net Users
  • New Users
  • Software
  • Digital Music
  • Gaming World
  • Home Security
  • Apple
  • Networking Hardware
Virus & Spyware
  • Vulnerabilities
  • IDS
  • Encryption
  • Anti-Virus
  • Operating Systems Security
  • Software Firewalls
  • WebApplications
  • Cell Phones
  • Operating Systems
  • Internet
  • Hardware Firewalls
Hardware
  • Displays / Monitors
  • Handhelds / PDAs
  • Components
  • Peripherals
  • Laptops/Notebooks
  • Servers
  • Misc
  • Apple
  • Embedded Hardware
  • Networking Hardware
  • Storage
  • Desktops
  • New Users
Software
  • System Utilities
  • Industry Specific
  • Network Management
  • Photos / Graphics
  • Page Layout
  • VMware
  • Misc
  • Web Development
  • OS
  • CYGWIN
  • Voice Recognition
  • Virtualization
  • Message Queue
  • Quality Assurance
  • Security
  • Firewalls
  • MultiMedia Applications
  • Development
  • Database
  • Office / Productivity
  • Business Management
  • OS/2 Apps
  • Server Software
  • Internet / Email
ITPro
  • OS
  • Storage
  • Encryption
  • Operating Systems Security
  • Apple Hardware
  • Laptops & Notebooks
  • Servers
  • Networking Hardware
  • Peripherals
  • Devices
  • Displays / Monitors
  • WebTrends / Stats
  • Search Engines
  • Firewalls
  • Web Computing
  • WebApplications
  • IDS
  • Vulnerabilities
  • Email Clients
  • File Sharing
  • Spy / Ad Blockers
  • Web Browsers
  • Web Servers
  • Networking
  • Anti-Virus
  • Consulting
  • Chat / IM
  • Anti Spam
Developer
  • Web Servers
  • Web Browsers
  • Game Programming
  • Dev Tools
  • Industry Specific
  • Office / Productivity
  • Database
  • CYGWIN
  • Web Development
  • Search Engines
  • File Sharing
  • WebTrends / Stats
  • Programming
  • Content Management
  • Application Servers
  • Protocols
Storage
  • Removable Backup Media
  • Storage Technology
  • Servers
  • Grid
  • Remote Access
  • Backup / Restore
  • Misc
  • Hard Drives
OS
  • Miscellaneous
  • Security
  • Development
  • Linux
  • VMware
  • MainFrame OS
  • Unix
  • Apple
  • OS / 2
  • AS / 400
  • BeOS
  • Microsoft
  • VMS / OpenVMS
Database
  • Oracle
  • Miscellaneous
  • MySQL
  • Software
  • Sybase
  • Contact Management
  • PostgreSQL
  • Data Manipulation
  • Clarion
  • InterSystems Cache
  • Siebel
  • MUMPS
  • OLAP
  • SQLBase
  • SAS
  • GIS & GPS
  • 4GL
  • Berkeley DB
  • DB2
  • Informix
  • Interbase / Firebird
  • FoxPro
  • Reporting
  • LDAP
  • Filemaker Pro
  • MS SQL Server
  • dBase
  • MS Access
Security
  • Misc
  • Web Browsers
  • Software Firewalls
  • Operating Systems Security
  • File Sharing
  • Spy / Ad Blockers
  • Vulnerabilities
  • WebApplications
  • IDS
  • Anti-Virus
  • Encryption
  • Anti Spam
  • Email Clients
  • VPN
  • Chat / IM
Programming
  • Editors IDEs
  • Installation
  • Handhelds / PDAs
  • Multimedia Programming
  • System / Kernel
  • Automation
  • Algorithms
  • Game
  • Signal Processing
  • Project Management
  • Open Source
  • Database
  • Misc
  • Languages
  • Processor Platforms
  • Theory
Web Development
  • Scripting
  • Blogs
  • Web Servers
  • Software
  • Search Engines
  • Web Graphics
  • Web Services
  • Images
  • Internet Marketing
  • Images and Photos
  • Components
  • Document Imaging
  • Web Languages/Standards
  • Illustration
  • WebApplications
  • Fonts
  • WebTrends / Stats
  • Authoring
  • Digital Camera Software
  • Miscellaneous
Networking
  • Protocols
  • Apple Networking
  • Network Management
  • Message Queue
  • Application Servers
  • Content Management
  • File Servers
  • Email Servers
  • Misc
  • Java Editors & IDEs
  • Wireless
  • Networking Hardware
  • Backup / Restore
  • System Utilities
  • ISPs & Hosting
  • Web Servers
  • Storage Technology
  • Removable Backup Media
  • Servers
  • Web Computing
  • Broadband
  • Grid
  • OS / 2
  • Novell Netware
  • Unix Networking
  • Windows Networking
  • Security
  • Telecommunications
  • Operating Systems
  • Linux Networking
Other
  • Lounge
  • Business Travel
  • Community Support
  • New Net Users
  • Philosophy / Religion
  • Math / Science
  • Miscellaneous
  • URLs
  • Expert Lounge
  • Politics
  • Puzzles / Riddles
  • Automotive
Community Support
  • Suggestions
  • New to EE
  • New Topics
  • CleanUp
  • Announcements
  • General
  • Feedback
  • Input
  • EE Bugs
 
05.16.2008 at 10:03AM PDT, ID: 21584438

Rank: Master

>> Does anyone know of a sort algorithm that, when corrupted by a meaningless comparison, will go into an infinite loop trying to resolve the sort?

If "meaningless comparison" means that it has a random result (or that it can have any result), and I take the "will" literally (as opposed to "might"), then no. Since random results mean that the results might be correct by coincidence, that would mean that the sorting algorithm would also end with the correct result (and thus not go into an infinite loop).

Assuming "might" instead of "will", then we only need one case where it goes into an infinite loop.

So, let's take bogosort for example that can even go in an infinite loop if the comparison function is correct ... so there's surely a chance that it will go into an infinite loop with an erroneous comparison function ;)

        http://en.wikipedia.org/wiki/Bogosort


But I guess you're looking for realistic algorithms ... Let me give that some thought ... The problem is that the worst-case complexity of all common sorting algorithms is under O(n²)
Accepted Solution
 
05.16.2008 at 12:36PM PDT, ID: 21585748

Hi Infinity,

Not quite what I'm looking for....

Consider a sort with the following compare function:

int Compare (void*A, void *B)
{
  return (((mystruct1*)A)->ID - ((mystruct2*)B)->ID);
}

Note that A and B are being recast to two different structures.  B is erroneous (it should have been A), so there's no valid comparison here.  In fact, if B->ID doesn't actually lie within the bounds of A, repeated calls of Compare() with the same arguments could return different values.

I've not actually seen this, but it occurred to me while writing a Compare() function that it could easily happen.  Then I got to wondering if any sort algorithms could get put into an infinite loop due to this bad comparison.  For the infinite loop to occur, a lot of stars would have to align just right, but you never know....


Kent

 
05.16.2008 at 12:56PM PDT, ID: 21585917

Rank: Guru

A bubble sort or an algorithm that contained a bubble sort could have a potential to infinite loop
 
05.16.2008 at 01:25PM PDT, ID: 21586157

Rank: Guru

> A bubble sort or an algorithm that contained a bubble sort could have a potential to infinite loop
Although that can depend on how the termination condition was written
If if runs until it finds no unsorted items, it could loop a long time.
if it decreases the region to be sorted on each pass, it could guarantee termination.
Assisted Solution
 
05.16.2008 at 01:38PM PDT, ID: 21586268

Rank: Master

>> Not quite what I'm looking for....

I did get what you meant ;) And the flaw you describe could have a "random" result. And that's what my observations were based on.

The "problem" is that most realistic sorting algorithms assume that the comparison function is correct, and thus optimize the algorithm accordingly. Meaning that, even if the comparison function would be incorrect, the algorithm would still end as it would normally (although the sorted order will probably be wrong).
As ozo said : bubble sort could be implemented in such a way that an infinite loop is possible with an incorrect comparison function, but that would be a sub-optimal implementation, and you will probably not see it in production code (at least I'd hope not).
The same is true for pretty much all common sorting algorithms - they're usually optimized based on the assumption that the comparison function is correct. So, they wouldn't be "vulnerable" to an infinite loop due to an comparison sorting function.
 
05.31.2008 at 07:31AM PDT, ID: 21683839

That's what I thought -- no one else has a definitive 'yes' either.

Thanks guys
Kent
 
 
20080236-EE-VQP-29 / EE_QW_EXPERT_20070906