Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
  • 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
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Devaka Cooray
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Knute Snortum
  • Bear Bibeault
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Frits Walraven
  • Carey Brown
  • Tim Holloway

Why non-recursive sorting algorithms are not popular?

 
Ranch Hand
Posts: 173
Firefox Browser Fedora Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have been revising algorithms for some days. Actually , i am not aware that iterative versions of the algorithms do exist but why they are not popular as their recursive counterparts.

Even the Arrays.sort method in java implements recursive quick sort.I heard that recursion causes overhead in maintaining the stack frames for each method call.

for e.g: Iterative version for merge sort is even simple. It first sort the adjacent elements and then the sorted pairs , so on.

I posted this question on StackOverflow too: but dint get a convincing answer.What are your views about this??

Thanks,
S.Hareendra
 
Saloon Keeper
Posts: 5587
144
Android Mac OS X Firefox Browser VI Editor Tomcat Server Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Quick sort (one of the fastest sorting algorithm) is recursive; trying to implement it in iterative fashion will lead to hard-to-understand code.

I heard that recursion causes overhead in maintaining the stack frames for each method call.


Yes, there is an overhead, but there is an overhead in implementing an iterative version, too. Recursion by itself is not something to be afraid of.
 
Hareendra Reddy
Ranch Hand
Posts: 173
Firefox Browser Fedora Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you Tim..
This, This andthis are useful too.
 
lowercase baba
Posts: 12751
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
memory is pretty cheap these days. My father used to tell me about when they paid basically $1 PER BYTE of memory. Today, I can run into just about any store and buy a 4GB thumb drive for under $15 bucks. It's usually not something to worry about. even my cell phone has a 4GB chip in it.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!