In-place algorithm - Revision history

Tea2min: Undid revision 1291440941 by 122.180.29.222 (talk)

2025-05-22T04:17:13Z

Undid revision 1291440941 by 122.180.29.222 (talk)

← Previous revision		Revision as of 04:17, 22 May 2025
Line 5:		Line 5:
	In [[computer science]], an '''in-place algorithm''' is an [[algorithm]] that operates directly on the input [[data structure]] without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called '''not-in-place''' or '''out-of-place'''.		In [[computer science]], an '''in-place algorithm''' is an [[algorithm]] that operates directly on the input [[data structure]] without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called '''not-in-place''' or '''out-of-place'''.

	In-place can have slightly different meanings. In s strictest form, the algorithm can only have a [[Space complexity\|constant amount of extra space]], counting everything including [[Subroutine\|function]] calls and [[Pointer (computer programming)\|pointers]]. However, this form is very limited as simply having an index to a length {{math\|''n''}} array requires {{math\|''O''(log ''n'')}} bits. More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is {{math\|''O''(log ''n'')}}, though sometimes anything in {{math\|''o''(''n'')}} is allowed. Note that space complexity also has varied choices in whether or not to count the index lengths as part of the space used. Often, the space complexity is given in terms of the number of indices or pointers needed, ignoring their length. In this article, we refer to total space complexity ([[Deterministic space\|DSPACE]]), counting pointer lengths. Therefore, the space requirements here have an extra {{math\|log ''n''}} factor compared to an analysis that ignores the lengths of indices and pointers.		In-place can have slightly different meanings. In its strictest form, the algorithm can only have a [[Space complexity\|constant amount of extra space]], counting everything including [[Subroutine\|function]] calls and [[Pointer (computer programming)\|pointers]]. However, this form is very limited as simply having an index to a length {{math\|''n''}} array requires {{math\|''O''(log ''n'')}} bits. More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is {{math\|''O''(log ''n'')}}, though sometimes anything in {{math\|''o''(''n'')}} is allowed. Note that space complexity also has varied choices in whether or not to count the index lengths as part of the space used. Often, the space complexity is given in terms of the number of indices or pointers needed, ignoring their length. In this article, we refer to total space complexity ([[Deterministic space\|DSPACE]]), counting pointer lengths. Therefore, the space requirements here have an extra {{math\|log ''n''}} factor compared to an analysis that ignores the lengths of indices and pointers.

	An algorithm may or may not count the output as part of its space usage. Since in-place algorithms usually overwrite their input with output, no additional space is needed. When writing the output to write-only memory or a stream, it may be more appropriate to only consider the working space of the algorithm. In theoretical applications such as [[log-space reduction]]s, it is more typical to always ignore output space (in these cases it is more essential that the output is ''write-only'').		An algorithm may or may not count the output as part of its space usage. Since in-place algorithms usually overwrite their input with output, no additional space is needed. When writing the output to write-only memory or a stream, it may be more appropriate to only consider the working space of the algorithm. In theoretical applications such as [[log-space reduction]]s, it is more typical to always ignore output space (in these cases it is more essential that the output is ''write-only'').

122.180.29.222 at 07:29, 21 May 2025

2025-05-21T07:29:15Z

← Previous revision		Revision as of 07:29, 21 May 2025
Line 5:		Line 5:
	In [[computer science]], an '''in-place algorithm''' is an [[algorithm]] that operates directly on the input [[data structure]] without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called '''not-in-place''' or '''out-of-place'''.		In [[computer science]], an '''in-place algorithm''' is an [[algorithm]] that operates directly on the input [[data structure]] without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called '''not-in-place''' or '''out-of-place'''.

	In-place can have slightly different meanings. In ~~its~~ strictest form, the algorithm can only have a [[Space complexity\|constant amount of extra space]], counting everything including [[Subroutine\|function]] calls and [[Pointer (computer programming)\|pointers]]. However, this form is very limited as simply having an index to a length {{math\|''n''}} array requires {{math\|''O''(log ''n'')}} bits. More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is {{math\|''O''(log ''n'')}}, though sometimes anything in {{math\|''o''(''n'')}} is allowed. Note that space complexity also has varied choices in whether or not to count the index lengths as part of the space used. Often, the space complexity is given in terms of the number of indices or pointers needed, ignoring their length. In this article, we refer to total space complexity ([[Deterministic space\|DSPACE]]), counting pointer lengths. Therefore, the space requirements here have an extra {{math\|log ''n''}} factor compared to an analysis that ignores the lengths of indices and pointers.		In-place can have slightly different meanings. In s strictest form, the algorithm can only have a [[Space complexity\|constant amount of extra space]], counting everything including [[Subroutine\|function]] calls and [[Pointer (computer programming)\|pointers]]. However, this form is very limited as simply having an index to a length {{math\|''n''}} array requires {{math\|''O''(log ''n'')}} bits. More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is {{math\|''O''(log ''n'')}}, though sometimes anything in {{math\|''o''(''n'')}} is allowed. Note that space complexity also has varied choices in whether or not to count the index lengths as part of the space used. Often, the space complexity is given in terms of the number of indices or pointers needed, ignoring their length. In this article, we refer to total space complexity ([[Deterministic space\|DSPACE]]), counting pointer lengths. Therefore, the space requirements here have an extra {{math\|log ''n''}} factor compared to an analysis that ignores the lengths of indices and pointers.

	An algorithm may or may not count the output as part of its space usage. Since in-place algorithms usually overwrite their input with output, no additional space is needed. When writing the output to write-only memory or a stream, it may be more appropriate to only consider the working space of the algorithm. In theoretical applications such as [[log-space reduction]]s, it is more typical to always ignore output space (in these cases it is more essential that the output is ''write-only'').		An algorithm may or may not count the output as part of its space usage. Since in-place algorithms usually overwrite their input with output, no additional space is needed. When writing the output to write-only memory or a stream, it may be more appropriate to only consider the working space of the algorithm. In theoretical applications such as [[log-space reduction]]s, it is more typical to always ignore output space (in these cases it is more essential that the output is ''write-only'').

163.53.211.96 at 05:10, 4 May 2025

2025-05-04T05:10:04Z

← Previous revision		Revision as of 05:10, 4 May 2025
Line 13:		Line 13:
	Given an [[Array data structure\|array]] {{code\|a}} of {{math\|''n''}} items, suppose we want an array that holds the same elements in reversed order and to dispose of the original. One seemingly simple way to do this is to create a new array of equal size, fill it with copies from {{code\|a}} in the appropriate order and then delete {{code\|a}}.		Given an [[Array data structure\|array]] {{code\|a}} of {{math\|''n''}} items, suppose we want an array that holds the same elements in reversed order and to dispose of the original. One seemingly simple way to do this is to create a new array of equal size, fill it with copies from {{code\|a}} in the appropriate order and then delete {{code\|a}}.

	'''function''' reverse(a[0..n - 1]		'''function''' reverse(a[0..n - 1])
	allocate b[0..n - 1]		allocate b[0..n - 1]
	'''for''' i '''from''' 0 '''to''' n - 1		'''for''' i '''from''' 0 '''to''' n - 1

163.53.211.96 at 05:09, 4 May 2025

2025-05-04T05:09:47Z

← Previous revision		Revision as of 05:09, 4 May 2025
Line 13:		Line 13:
	Given an [[Array data structure\|array]] {{code\|a}} of {{math\|''n''}} items, suppose we want an array that holds the same elements in reversed order and to dispose of the original. One seemingly simple way to do this is to create a new array of equal size, fill it with copies from {{code\|a}} in the appropriate order and then delete {{code\|a}}.		Given an [[Array data structure\|array]] {{code\|a}} of {{math\|''n''}} items, suppose we want an array that holds the same elements in reversed order and to dispose of the original. One seemingly simple way to do this is to create a new array of equal size, fill it with copies from {{code\|a}} in the appropriate order and then delete {{code\|a}}.

	'''function''' reverse(a[0..n - 1])		'''function''' reverse(a[0..n - 1]
	allocate b[0..n - 1]		allocate b[0..n - 1]
	'''for''' i '''from''' 0 '''to''' n - 1		'''for''' i '''from''' 0 '''to''' n - 1

139.101.160.63: Undid revision 1267700597 by 2409:4070:2001:D70B:595B:FBA7:2508:874C (talk)

2025-04-05T20:50:03Z

Undid revision 1267700597 by 2409:4070:2001:D70B:595B:FBA7:2508:874C (talk)

← Previous revision		Revision as of 20:50, 5 April 2025
Line 26:		Line 26:
	a[i] := a[n − 1 − i]		a[i] := a[n − 1 − i]
	a[n − 1 − i] := tmp		a[n − 1 − i] := tmp

	And for further clarification check leet code problem number [https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150 88]

	As another example, many [[sorting algorithm]]s rearrange arrays into sorted order in-place, including: [[bubble sort]], [[comb sort]], [[selection sort]], [[insertion sort]], [[heapsort]], and [[Shell sort]]. These algorithms require only a few pointers, so their space complexity is {{math\|''O''(log ''n'')}}.<ref>The bit space requirement of a pointer is {{math\|''O''(log ''n'')}}, but pointer size can be considered a constant in most sorting applications.</ref>		As another example, many [[sorting algorithm]]s rearrange arrays into sorted order in-place, including: [[bubble sort]], [[comb sort]], [[selection sort]], [[insertion sort]], [[heapsort]], and [[Shell sort]]. These algorithms require only a few pointers, so their space complexity is {{math\|''O''(log ''n'')}}.<ref>The bit space requirement of a pointer is {{math\|''O''(log ''n'')}}, but pointer size can be considered a constant in most sorting applications.</ref>

MrBenjo: Reverted edits by 103.77.43.192 (talk) to last version by 2409:4070:2001:D70B:595B:FBA7:2508:874C: editing tests

2025-02-05T08:41:48Z

Reverted edits by 103.77.43.192 (talk) to last version by 2409:4070:2001:D70B:595B:FBA7:2508:874C: editing tests

← Previous revision		Revision as of 08:41, 5 February 2025
Line 63:		Line 63:
	[[Functional programming]] languages often discourage or do not support explicit in-place algorithms that overwrite data, since this is a type of [[side effect (computer science)\|side effect]]; instead, they only allow new data to be constructed. However, good functional language compilers will often recognize when an object very similar to an existing one is created and then the old one is thrown away, and will optimize this into a simple mutation "under the hood".		[[Functional programming]] languages often discourage or do not support explicit in-place algorithms that overwrite data, since this is a type of [[side effect (computer science)\|side effect]]; instead, they only allow new data to be constructed. However, good functional language compilers will often recognize when an object very similar to an existing one is created and then the old one is thrown away, and will optimize this into a simple mutation "under the hood".

	Note that it is possible in principle to carefully construct in-place algorithms that do not modify data (unless the data is no longer being used), but this is rarely done in practice. ~~this~~		Note that it is possible in principle to carefully construct in-place algorithms that do not modify data (unless the data is no longer being used), but this is rarely done in practice.

	== See also ==		== See also ==

103.77.43.192: /* In functional programming */

2025-02-05T08:41:37Z

In functional programming

← Previous revision		Revision as of 08:41, 5 February 2025
Line 63:		Line 63:
	[[Functional programming]] languages often discourage or do not support explicit in-place algorithms that overwrite data, since this is a type of [[side effect (computer science)\|side effect]]; instead, they only allow new data to be constructed. However, good functional language compilers will often recognize when an object very similar to an existing one is created and then the old one is thrown away, and will optimize this into a simple mutation "under the hood".		[[Functional programming]] languages often discourage or do not support explicit in-place algorithms that overwrite data, since this is a type of [[side effect (computer science)\|side effect]]; instead, they only allow new data to be constructed. However, good functional language compilers will often recognize when an object very similar to an existing one is created and then the old one is thrown away, and will optimize this into a simple mutation "under the hood".

	Note that it is possible in principle to carefully construct in-place algorithms that do not modify data (unless the data is no longer being used), but this is rarely done in practice.		Note that it is possible in principle to carefully construct in-place algorithms that do not modify data (unless the data is no longer being used), but this is rarely done in practice. this

	== See also ==		== See also ==

2409:4070:2001:D70B:595B:FBA7:2508:874C: i had changed example section by adding leet code example problem

2025-01-06T07:15:11Z

i had changed example section by adding leet code example problem

← Previous revision		Revision as of 07:15, 6 January 2025
Line 26:		Line 26:
	a[i] := a[n − 1 − i]		a[i] := a[n − 1 − i]
	a[n − 1 − i] := tmp		a[n − 1 − i] := tmp

			And for further clarification check leet code problem number [https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150 88]

	As another example, many [[sorting algorithm]]s rearrange arrays into sorted order in-place, including: [[bubble sort]], [[comb sort]], [[selection sort]], [[insertion sort]], [[heapsort]], and [[Shell sort]]. These algorithms require only a few pointers, so their space complexity is {{math\|''O''(log ''n'')}}.<ref>The bit space requirement of a pointer is {{math\|''O''(log ''n'')}}, but pointer size can be considered a constant in most sorting applications.</ref>		As another example, many [[sorting algorithm]]s rearrange arrays into sorted order in-place, including: [[bubble sort]], [[comb sort]], [[selection sort]], [[insertion sort]], [[heapsort]], and [[Shell sort]]. These algorithms require only a few pointers, so their space complexity is {{math\|''O''(log ''n'')}}.<ref>The bit space requirement of a pointer is {{math\|''O''(log ''n'')}}, but pointer size can be considered a constant in most sorting applications.</ref>

Adam El-Sawaf at 10:10, 30 November 2024

2024-11-30T10:10:54Z

← Previous revision		Revision as of 10:10, 30 November 2024
Line 5:		Line 5:
	In [[computer science]], an '''in-place algorithm''' is an [[algorithm]] that operates directly on the input [[data structure]] without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called '''not-in-place''' or '''out-of-place'''.		In [[computer science]], an '''in-place algorithm''' is an [[algorithm]] that operates directly on the input [[data structure]] without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called '''not-in-place''' or '''out-of-place'''.

	In-place can have slightly different meanings. In its strictest form, the algorithm can only have a [[Space complexity\|constant amount of extra space]], counting everything including [[Subroutine\|function]] calls and [[Pointer (computer programming)\|pointers]]. However, this form is very limited as simply having an index to a length {{math\|''n''}} array requires {{math\|''O''(log ''n'')}} bits. More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is {{math\|''O''(log ''n'')}}, though sometimes anything in {{math\|''o''(''n'')}} is allowed. Note that space complexity also has varied choices in whether or not to count the index lengths as part of the space used. Often, the space complexity is given in terms of the number of indices or pointers needed, ignoring their length. In this article, we refer to total space complexity ([[Deterministic space\|DSPACE]]), counting pointer lengths. Therefore, the space requirements here have an extra {{math\|log ''n''}} factor compared to an analysis that ignores the ~~length~~ of indices and pointers.		In-place can have slightly different meanings. In its strictest form, the algorithm can only have a [[Space complexity\|constant amount of extra space]], counting everything including [[Subroutine\|function]] calls and [[Pointer (computer programming)\|pointers]]. However, this form is very limited as simply having an index to a length {{math\|''n''}} array requires {{math\|''O''(log ''n'')}} bits. More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is {{math\|''O''(log ''n'')}}, though sometimes anything in {{math\|''o''(''n'')}} is allowed. Note that space complexity also has varied choices in whether or not to count the index lengths as part of the space used. Often, the space complexity is given in terms of the number of indices or pointers needed, ignoring their length. In this article, we refer to total space complexity ([[Deterministic space\|DSPACE]]), counting pointer lengths. Therefore, the space requirements here have an extra {{math\|log ''n''}} factor compared to an analysis that ignores the lengths of indices and pointers.

	An algorithm may or may not count the output as part of its space usage. Since in-place algorithms usually overwrite their input with output, no additional space is needed. When writing the output to write-only memory or a stream, it may be more appropriate to only consider the working space of the algorithm. In theoretical applications such as [[log-space reduction]]s, it is more typical to always ignore output space (in these cases it is more essential that the output is ''write-only'').		An algorithm may or may not count the output as part of its space usage. Since in-place algorithms usually overwrite their input with output, no additional space is needed. When writing the output to write-only memory or a stream, it may be more appropriate to only consider the working space of the algorithm. In theoretical applications such as [[log-space reduction]]s, it is more typical to always ignore output space (in these cases it is more essential that the output is ''write-only'').

APenguinThatIsSilly: fixed link

2024-09-10T22:30:55Z

fixed link

← Previous revision		Revision as of 22:30, 10 September 2024
Line 19:		Line 19:
	'''return''' b		'''return''' b

	Unfortunately, this requires {{math\|''O''(''n'')}} extra space for having the arrays {{code\|a}} and {{code\|b}} available simultaneously. Also, [[~~Memory~~ management~~#ALLOCATION~~\|allocation]] and deallocation are often slow operations. Since we no longer need {{code\|a}}, we can instead overwrite it with its own reversal using this in-place algorithm which will only need constant number (2) of integers for the auxiliary variables {{code\|i}} and {{code\|tmp}}, no matter how large the array is.		Unfortunately, this requires {{math\|''O''(''n'')}} extra space for having the arrays {{code\|a}} and {{code\|b}} available simultaneously. Also, [[Manual memory management\|allocation]] and deallocation are often slow operations. Since we no longer need {{code\|a}}, we can instead overwrite it with its own reversal using this in-place algorithm which will only need constant number (2) of integers for the auxiliary variables {{code\|i}} and {{code\|tmp}}, no matter how large the array is.

	'''function''' reverse_in_place(a[0..n-1])		'''function''' reverse_in_place(a[0..n-1])