Talk:In-place algorithm

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

High

This article has been rated as High-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Computing High‑importance

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles
High	This article has been rated as High-importance on the project's importance scale.

Proposed move

According to Wikipedia: Naming conventions, I propose moving this page to the noun phrase In-place algorithm. Sound good? There shouldn't be a hyphen between "work" and "in" anyway. Deco 02:28, 24 Feb 2005 (UTC)

Sounds good. I vote in favour :) --Clausen 22:09, 28 Feb 2005 (UTC)

In-Place is ambiguous?

It seems to me that there are two different meanings for "in-place": algorithms which modify their inputs so that the output is put in the same place as where the input was, and algorithms that only require constant additional space.

In a theoretical settting, I think the latter is standard. I think we should either decide that the first one is wrong, or emphasis the ambiguity.

--Clausen 05:47, 6 Jun 2005 (UTC)

This is a tricky ambiguity. I thought about this and added a paragraph regarding it. I think it's outright wrong to say that an algorithm which replaces its input with its output is in-place even if it uses large amounts of auxilary storage (although this is done informally). More ambiguous is whether the output space should be counted in determining the auxilary space used, which is never done in theory but sometimes done in practice. Deco 08:20, 6 Jun 2005 (UTC)

Latin?

Why Latin? —Preceding unsigned comment added by 66.109.35.41 (talk) 13:53, 25 January 2010 (UTC)[reply]

QuickSort

Allo.
The reason QuickSort is sometimes referred to as an in-place sort is because there's more than one definition of "in-place". Some reference materials will strictly mandate "constant" additional space, while others define it as meaning "constant or logarithmic" (O(N) or O(log N)) additional space.
So, depending on which definition you use, QuickSort can be in-place, or not. 139.57.100.63 (talk) 21:37, 30 June 2011 (UTC)[reply]

Quicksort and in place

I changed the article to try to better clarify the distinctions between the different interpretations of "in place". — Preceding unsigned comment added by Lurrch (talk • contribs) 16:52, 23 September 2015 (UTC)[reply]