IndexSort

IndexSort

File:Empty Example of IndexSort. starting with first value and switching by its index, if correct place go next one, repeated until done.
Class	Sorting algorithm
Data structure	Array
Worst-case performance	around: $O(n)$
Best-case performance	probably around: $O(n)$
Average performance	around: $O(n)$
Worst-case space complexity	$O(1)$ as it doesn't use auxiliary arrays

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:

1. 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
2. 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

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

note

1. current implementation likely crashes if there are repeated values
2. needed gif image
3. still under maintenance, don't expect a lot from it

This article "IndexSort" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:IndexSort. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---