readme.md

Swap Sort

Swap Sort is also a sorting algorithm, which is not known by many.It has $O(n)$ time complexity.It works only on numbers [1 to n] and must not contain duplicates.You might be thinking what is the use of Swap Sort as there is Count Sort which time complexity is $O(n)$ and can also sort data with dupliactes, but Swap sort is useful and efficient in solving many problems namely, find duplicate and missing, find all duplicates and missing from Array.

Complexity

Best	Average	Worst	Memory	Stable
$O(n)$	$O(n)$	$O(n)$	$O(1)$	No

• The worst-case time complexity of Swap Sort is $O(n)$.
• The best-case time complexity of Swap Sort is $O(n)$.
• The average case time complexity of Swap Sort is $O(n)$.
• The space complexity of Swap Sort is $O(1)$.

Pseudo Code

procedure swapSort( A: nums)
    n = len(nums)
    while i < n
        // get the curr ele original index
        index = nums[i]-1
        if  nums[i] != nums[index]
            swap nums[i] and nums[index]
        else
            i++
end procedure

Implementations

• Python
• CPP
• C

Python

import sys

def swapSort(arr):
    n = len(arr)
    i = 0
    while i < n:
        if arr[i] != arr[arr[i] - 1]:
            tmp = arr[i]
            arr[i], arr[tmp - 1] = arr[arr[i] - 1], tmp
        else:
            i += 1

def main():
    arr = [5,2,3,1,4]
    swapSort(arr)
    print(arr)

if __name__ == "__main__":
    main()

CPP

#include<bits/stdc++.h>
using namespace std;


void swapSort(vector<int>& arr)
{
    int n = arr.size();
    int i=0;

    while(i < n)
    {
        if(arr[i] != arr[arr[i]-1])
            swap(arr[i], arr[arr[i]-1]);
        else
            i++;
    }
}


int main()
{
    vector<int> arr = {5,2,3,1,4};
    swapSort(arr);  // [1,2,3,4,5]

    for(auto x:arr)
        cout<<x<<" ";
}

C

#include<stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void swapSort(int* arr, int n)
{
    int i=0;
    while(i < n)
    {
        if(arr[i] != arr[arr[i]-1])
            swap(&arr[i], &(arr[arr[i]-1]));
        else
            i++;
    }
}


int main()
{
    int arr[] = {5,4,3,2,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    swapSort(arr, n);  // [1,2,3,4,5]

    for(int i=0; i<n; i++)
        printf("%d ", arr[i]);
}