43:
219:
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
234:
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
613:; 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".
155:
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
583:
steps, the chance that we will stumble across the other vertex provided that it is in the same component is very high. Similarly, there are simple randomized in-place algorithms for primality testing such as the
264:
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
512:
Identifying the in-place algorithms with L has some interesting implications; for example, it means that there is a (rather complex) in-place algorithm to determine whether a path exists between two nodes in an
196:
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
616:
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.
325:, 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
425:
additional space. Although this non-constant space technically takes quicksort out of the in-place category, quicksort and other algorithms needing only
719:
572:
of the graph, there is no known simple, deterministic, in-place algorithm to determine this. However, if we simply start at one vertex and perform a
443:
are also in-place, although some considerably rearrange the input array in the process of finding the final, constant-sized result.
107:
79:
86:
503:
additional space, to be in-place. This class is more in line with the practical definition, as it allows numbers of size
60:
609:
languages often discourage or do not support explicit in-place algorithms that overwrite data, since this is a type of
569:
537:
532:(a visited bit for each node). This in turn yields in-place algorithms for problems such as determining if a graph is
509:
as pointers or indices. This expanded definition still excludes quicksort, however, because of its recursive calls.
126:
93:
601:
585:
465:
610:
176:
75:
64:
625:
411:
239:, it is more typical to always ignore output space (in these cases it is more essential that the output is
589:
167:
In-place can have slightly different meanings. In its strictest form, the algorithm can only have a
318:
17:
53:
100:
606:
707:
559:
252:
8:
741:
477:
440:
236:
221:
558:
In many cases, the space requirements of an algorithm can be drastically cut by using a
711:
686:
529:
447:
715:
355:
695:
553:
514:
482:
168:
140:
31:
351:
floor((n-2)/2) tmp := a a := a a := tmp
231:
factor compared to an analysis that ignores the length of indices and pointers.
224:), counting pointer lengths. Therefore, the space requirements here have an extra
703:
549:
533:
459:
723:
489:
371:
367:
152:
735:
681:
654:, but pointer size can be considered a constant in most sorting applications.
588:, and there are also simple in-place randomized factoring algorithms such as
382:. These algorithms require only a few pointers, so their space complexity is
699:
468:, the strict definition of in-place algorithms includes all algorithms with
179:. However, this form is very limited as simply having an index to a length
664:
573:
359:
399:
operates in-place on the data to be sorted. However, quicksort requires
379:
172:
485:. In fact, it does not even include any of the examples listed above.
396:
363:
148:
321:
and deallocation are often slow operations. Since we no longer need
42:
562:. For example, if one wishes to know if two vertices in a graph of
375:
30:"In-place" redirects here. For execute in place file systems, see
436:
additional pointers are usually considered in-place algorithms.
410:
stack space pointers to keep track of the subarrays in its
358:
rearrange arrays into sorted order in-place, including:
536:
or testing whether two graphs have the same number of
626:
Table of in-place and not-in-place sorting algorithms
67:. Unsourced material may be challenged and removed.
733:
684:(2008), "Undirected connectivity in log-space",
481:(1). This class is very limited; it equals the
235:algorithm. In theoretical applications such as
453:
528:extra space using typical algorithms such as
665:The Complexity World below Logarithmic Space
595:
671:, pp. 64–78. 1994. Online: p. 3, Theorem 2.
643:The bit space requirement of a pointer is
446:Some text manipulation algorithms such as
669:Structure in Complexity Theory Conference
269:in the appropriate order and then delete
127:Learn how and when to remove this message
680:
663:Maciej Liśkiewicz and Rüdiger Reischuk.
414:strategy. Consequently, quicksort needs
14:
734:
543:
488:Algorithms are usually considered in
333:, no matter how large the array is.
151:that operates directly on the input
65:adding citations to reliable sources
36:
24:
492:, the class of problems requiring
450:and reverse may be done in-place.
309:extra space for having the arrays
27:Type of computer science algorithm
25:
753:
602:Purely functional data structure
317:available simultaneously. Also,
291:n - 1 b := a
279:reverse(a) allocate b
171:, counting everything including
41:
466:computational complexity theory
330:
326:
322:
314:
310:
270:
266:
255:
208:, though sometimes anything in
52:needs additional citations for
674:
657:
637:
169:constant amount of extra space
13:
1:
631:
298:Unfortunately, this requires
475:space complexity, the class
7:
619:
586:Miller–Rabin primality test
454:In computational complexity
246:
10:
758:
599:
547:
517:, a problem that requires
457:
29:
596:In functional programming
568:vertices are in the same
354:As another example, many
339:reverse_in_place(a)
700:10.1145/1391289.1391291
590:Pollard's rho algorithm
607:Functional programming
560:randomized algorithm
538:connected components
441:selection algorithms
237:log-space reductions
76:"In-place algorithm"
61:improve this article
570:connected component
687:Journal of the ACM
544:Role of randomness
530:depth-first search
412:divide and conquer
356:sorting algorithms
145:in-place algorithm
483:regular languages
137:
136:
129:
111:
16:(Redirected from
749:
727:
726:
678:
672:
661:
655:
653:
641:
582:
567:
554:BPL (complexity)
527:
515:undirected graph
508:
502:
474:
435:
424:
409:
392:
332:
328:
324:
316:
312:
308:
272:
268:
263:
257:
230:
218:
207:
195:
184:
141:computer science
132:
125:
121:
118:
112:
110:
69:
45:
37:
32:Execute in place
21:
757:
756:
752:
751:
750:
748:
747:
746:
732:
731:
730:
679:
675:
662:
658:
644:
642:
638:
634:
622:
604:
598:
577:
563:
556:
550:RL (complexity)
546:
518:
504:
493:
469:
462:
460:SL (complexity)
456:
426:
415:
400:
383:
352:
299:
296:
259:
249:
225:
209:
198:
186:
185:array requires
180:
133:
122:
116:
113:
70:
68:
58:
46:
35:
28:
23:
22:
15:
12:
11:
5:
755:
745:
744:
729:
728:
682:Reingold, Omer
673:
656:
635:
633:
630:
629:
628:
621:
618:
597:
594:
545:
542:
455:
452:
372:insertion sort
368:selection sort
335:
275:
248:
245:
153:data structure
135:
134:
49:
47:
40:
26:
9:
6:
4:
3:
2:
754:
743:
740:
739:
737:
725:
721:
717:
713:
709:
705:
701:
697:
693:
689:
688:
683:
677:
670:
666:
660:
651:
647:
640:
636:
627:
624:
623:
617:
614:
612:
608:
603:
593:
591:
587:
581:
575:
571:
566:
561:
555:
551:
541:
539:
535:
531:
525:
521:
516:
510:
507:
500:
496:
491:
486:
484:
480:
479:
472:
467:
461:
451:
449:
444:
442:
437:
433:
429:
422:
418:
413:
407:
403:
398:
394:
390:
386:
381:
377:
373:
369:
365:
361:
357:
350:
346:
342:
338:
334:
320:
306:
302:
294:
290:
286:
282:
278:
274:
262:
254:
244:
242:
238:
232:
229:
223:
216:
212:
205:
201:
193:
189:
183:
178:
174:
170:
165:
163:
159:
154:
150:
146:
142:
131:
128:
120:
109:
106:
102:
99:
95:
92:
88:
85:
81:
78: –
77:
73:
72:Find sources:
66:
62:
56:
55:
50:This article
48:
44:
39:
38:
33:
19:
691:
685:
676:
668:
659:
649:
645:
639:
615:
605:
579:
564:
557:
523:
519:
511:
505:
498:
494:
487:
476:
470:
463:
445:
438:
431:
427:
420:
416:
405:
401:
395:
388:
384:
353:
348:
344:
340:
336:
304:
300:
297:
292:
288:
284:
280:
276:
260:
250:
240:
233:
227:
214:
210:
203:
199:
191:
187:
181:
166:
162:out-of-place
161:
158:not-in-place
157:
144:
138:
123:
117:January 2015
114:
104:
97:
90:
83:
71:
59:Please help
54:verification
51:
694:(4): 1–24,
611:side effect
574:random walk
360:bubble sort
742:Algorithms
632:References
600:See also:
548:See also:
458:See also:
380:Shell sort
319:allocation
241:write-only
175:calls and
87:newspapers
716:207168478
576:of about
534:bipartite
397:Quicksort
364:comb sort
251:Given an
149:algorithm
736:Category
724:TR04-094
620:See also
376:heapsort
337:function
277:function
247:Examples
177:pointers
173:function
18:In-place
708:2445014
101:scholar
722:
714:
706:
478:DSPACE
378:, and
293:return
222:DSPACE
147:is an
103:
96:
89:
82:
74:
712:S2CID
648:(log
497:(log
439:Most
430:(log
419:(log
404:(log
387:(log
253:array
202:(log
190:(log
143:, an
108:JSTOR
94:books
720:ECCC
552:and
448:trim
345:from
329:and
313:and
285:from
226:log
80:news
696:doi
473:(1)
464:In
341:for
331:tmp
281:for
258:of
243:).
160:or
139:In
63:by
738::
718:,
710:,
704:MR
702:,
692:55
690:,
667:.
592:.
578:20
540:.
393:.
374:,
370:,
366:,
362:,
349:to
347:0
343:i
295:b
289:to
287:0
283:i
273:.
164:.
698::
652:)
650:n
646:O
580:n
565:n
526:)
524:n
522:(
520:O
506:n
501:)
499:n
495:O
490:L
471:O
434:)
432:n
428:O
423:)
421:n
417:O
408:)
406:n
402:O
391:)
389:n
385:O
327:i
323:a
315:b
311:a
307:)
305:n
303:(
301:O
271:a
267:a
261:n
256:a
228:n
220:(
217:)
215:n
213:(
211:o
206:)
204:n
200:O
194:)
192:n
188:O
182:n
130:)
124:(
119:)
115:(
105:·
98:·
91:·
84:·
57:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
