Sort algorithms usually have:
There are other algorithms which work in a similar way. For example, a shuffle algorithm takes an array of elements which are in order, and mixes them up in a random order, just like shuffling a pack of cards. This algorithm is used in computer card games such as Solitaire.
The natural way to write an algorithm like this would be to use 2 arrays, an input array containing the initial values, and an output array to hold the sorted values. The output array would start off empty (e.g. filled with zeros).
in = [9, 3, 6, 5, 2, 1, 8] out = [0 , 0, 0, 0, 0, 0, 0]
After sorting, the output array would contain the elements in correct order:
in = [9, 3, 6, 5, 2, 1, 8] out = [1, 2, 3, 5, 6, 8, 9]
Using two arrays could be a problem is there is a very large amount of data, because it requires twice as much memory. We might prefer a version of the algorithm which works "in-place" - the calculation is performed by moving elements around in a single array. We start with:
in = [9, 3, 6, 5, 2, 1, 8]
And end up with this (with no second array required:
in = [1, 2, 3, 5, 6, 8, 9]
Many common search algorithms can be carried out in place.
Copyright (c) Axlesoft Ltd 2021