Editing In-place algorithm (section)

== Examples ==

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])
      allocate b[0..n - 1]
      '''for''' i '''from''' 0 '''to''' n - 1
          b[n − 1 − i] := a[i]
      '''return''' b

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])
      '''for''' i '''from''' 0 '''to''' floor((n-2)/2)
          tmp := a[i]
          a[i] := a[n − 1 − i]
          a[n − 1 − i] := tmp

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>

[[Quicksort]] operates in-place on the data to be sorted. However, quicksort requires {{math|''O''(log ''n'')}} stack space pointers to keep track of the subarrays in its [[divide and conquer algorithm|divide and conquer]] strategy. Consequently, quicksort needs {{math|''O''(log{{sup|2}} ''n'')}} additional space. Although this non-constant space technically takes quicksort out of the in-place category, quicksort and other algorithms needing only {{math|''O''(log ''n'')}} additional pointers are usually considered in-place algorithms.

Most [[selection algorithm]]s are also in-place, although some considerably rearrange the input array in the process of finding the final, constant-sized result.

Some text manipulation algorithms such as [[Trim (programming)|trim]] and reverse may be done in-place.