Scribd Logo
Upload

Welcome to Scribd!

  • 23 views

    Placing Sort: Constraints: This Algorithm Is Applicable Only of The Given Set Is Contiguous and The Minimum of The

    Uploaded by

    Bala Kumar
    This algorithm sorts a contiguous set of numbers where the minimum value is known in O(n) time. It iterates through the array, swapping elements that are out of place based on their value relative to the minimum. This places the numbers in sorted order without the need for comparisons. The example shows sorting the set {7,6,1,3,5,2,4} with minimum 1 by swapping elements on each iteration until it reaches the sorted order of {1,2,3,4,5,6,7}.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Placing Sort: Constraints: This Algorithm Is Applicable Only of The Given Set Is Contiguous and The Minimum of The

    Uploaded by

    Bala Kumar
    23 views2 pages
    This algorithm sorts a contiguous set of numbers where the minimum value is known in O(n) time. It iterates through the array, swapping elements that are out of place based on their value relative to the minimum. This places the numbers in sorted order without the need for comparisons. The example shows sorting the set {7,6,1,3,5,2,4} with minimum 1 by swapping elements on each iteration until it reaches the sorted order of {1,2,3,4,5,6,7}.

    Original Description:

    A linear time sorting algorithm (non-comparision sort) developed by me.

    Original Title

    Placing Sort

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This algorithm sorts a contiguous set of numbers where the minimum value is known in O(n) time. It iterates through the array, swapping elements that are out of place based on their value relative to the minimum. This places the numbers in sorted order without the need for comparisons. The example shows sorting the set {7,6,1,3,5,2,4} with minimum 1 by swapping elements on each iteration until it reaches the sorted order of {1,2,3,4,5,6,7}.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    23 views2 pages

    Placing Sort: Constraints: This Algorithm Is Applicable Only of The Given Set Is Contiguous and The Minimum of The

    Uploaded by

    Bala Kumar
    This algorithm sorts a contiguous set of numbers where the minimum value is known in O(n) time. It iterates through the array, swapping elements that are out of place based on their value relative to the minimum. This places the numbers in sorted order without the need for comparisons. The example shows sorting the set {7,6,1,3,5,2,4} with minimum 1 by swapping elements on each iteration until it reaches the sorted order of {1,2,3,4,5,6,7}.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Placing Sort

    Constraints: This algorithm is applicable only of the given set is contiguous and the minimum of the
    given set is given.

    Algorithm:
    placingSort (A, low)
    for i = 1 to A.length
    if A[i] = i + low
    i=i+1
    else
    swap(A[A[i] - low], A[i])
    Complexity: O(n)

    Example:
    Given the set { 7, 6, 1, 3, 5, 2, 4 } [Contiguous and minimum = 1]
    After iteration 1 :
    { 4, 6, 1, 3, 5, 2, 7}
    Iteration 2:
    { 3, 6, 1, 4, 5, 2, 7}
    Iteration 3:
    { 1, 6, 3, 4, 5, 2, 7}
    Iteration 4:
    { 1, 2, 3, 4, 5, 6, 7} --- (sorted)
    runs upto 7 iterations.

    By: Anshul Agarwal & Bala Kumar

    C++ Implementation:
    #include <iostream>
    using namespace std;
    void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
    }
    void placingsort(int arr[], int n, int k) {
    for (int i = 0; i < n; ) {
    if (arr[i] == i + k)
    i++;
    else {
    swap(arr[arr[i] - k], arr[i]);
    }
    }
    }
    int main(void) {
    int arr[] = { 45, 47, 42, 49, 48, 44, 46, 43 },
    n = sizeof(arr)/sizeof(int);
    // Printing input array
    cout << "Input Sequence : " << endl;
    for (int i = 0; i < n; i++)
    cout << arr[i] << "\t";
    cout << endl;
    placingsort(arr, n, 42);
    // Printing the sorted array
    cout << "Sorted Sequence : " << endl;
    for (int i = 0; i < n; i++)
    cout << arr[i] << "\t";
    cout << endl;
    }

    By: Anshul Agarwal & Bala Kumar

    You might also like