View source for IndexSort

{{Draft article}}
{{Short description|sorting algorithm}}
{{Infobox Algorithm
|name={{PAGENAMEBASE}}|class=[[Sorting algorithm]]
|image=empty
|caption=Example of IndexSort. starting with first value and switching by its index, if correct place go next one, repeated until done.
|data=[[Array data structure|Array]]
|time=around: <math>O(n)</math>
|best-time=probably around: <math>O(n)</math>
|average-time=around: <math>O(n)</math>
|space=<math>O(1)</math> as it doesn't use auxiliary arrays
<ref>{{Harvtxt|Skiena|2008|p=122}}</ref>
}}

index sort is an index based [[Sorting algorithm]] that sorts by taking value (if language have index 0 put value - 1) and putting as index, it breaks when it has duplicate value, only works on [[integer]] values
==Algorithm==

basically it works:
#take first value of array (called current) and go to array[current - 1] and switch places with other value same index as current, then continuing on first value do same repeatedly
#if array[current - 1] is same as current - 1, it will go to 2nd value, and repeated until sorted

==implementation/code==
we will use python for this example

<syntaxhighlight lang="python">
def Indexsort(arr):
    current = 0
    n = len(arr)
    while current < n:
        target = arr[current] - 1
        if 0 <= target < n and arr[current] != arr[target]:
            arr[current], arr[target] = arr[target], arr[current]
        else:
            current += 1
</syntaxhighlight>

==note==
#current implementation likely crashes if there are repeated values
#needed gif image
#still under maintenance, don't expect a lot from it
{{Drafts moved from mainspace|date=October 2024}}
{{⚠️🚨COPIED from EverybodyWiki ❗❕⚠️😡😤Please respect Licence CC-BY-SA ❗}}
{{Source Wikipedia}}