What would be the space and time complexity of my sorting algorithm?

Question

Given below is the code for which I would like someone to help me figure out the time and space complexity, keeping in mind that both of them would depend only on the "Sorting Algorithm Code" of the given program.
Do keep in mind that the no. of columns that you can take as input should be an odd integer excluding 1, and an even numbered column will yield false results due to the way the code is being sorted.
When asked for the "constant multiplier" you need to type in these tested numbers, that help sort the 2D array: 1. For 100 elements, columns=33 and constant multiplier=4,
2. For 200 elements, columns=67 and constant multiplier=10,
3. For 300 elements, columns=101 and constant multiplier=15,
4. For 400 elements, columns=133 and constant multiplier=15,
5. For 500 elements, columns=167 and constant multiplier=25,
6. For 30000 elements, columns=9999 and constant multiplier=2500.
etc.. etc..

I would also like to accept input from a .txt file saved elsewhere. How can I do it?
Cheers. Thanks for baring with me :)

The Code:

#include<iostream>
#include<conio.h>
#include<stdio.h>
#include<fstream>

using namespace std;

void main()
{
system("cls");
int col;
int d;
int cons=1;
A:
cout << endl;
int a[3][40000] = { {0} };//Initializing the array to 0
cout << "enter no. of columns:";//No. of Columns for the 3xN matrix
cin >> col;
int noe = col * 3;//Total No. of Elements

//Code to accept the constant multiplier
cout << "Enter the constant multiplier:";
cin >> cons;

//Code to generate a list of random integers and store it in the array 
for (int i = 0; i < col;i++)
for (int j = 0; j < 3; j++)
{
    d = rand() % 9000;
    a[j][i] = d; 
}


int k = 0;
int temp;//Temporary Storage
int flag = 0;


//Sorting algorithm 
for (int n = 0; n <= noe*cons; n++)
{
    if ((k % 2 == 0) && (flag == 0))
    {
        //Sorting Upper Triangle
        //3 row check
        if (a[0][k]>a[0][k + 1])
        {
            temp = a[0][k + 1];
            a[0][k + 1] = a[0][k];
            a[0][k] = temp;
        }

        if (a[1][k] > a[1][k + 1])
        {
            temp = a[1][k + 1];
            a[1][k + 1] = a[1][k];
            a[1][k] = temp;
        }

        if (a[2][k] > a[0][k + 2])
        {
            temp = a[0][k + 2];
            a[0][k + 2] = a[2][k];
            a[2][k] = temp;
        }

        //First Column Check
        {
            if (a[0][k] > a[1][k])
            {
                temp = a[1][k];
                a[1][k] = a[0][k];
                a[0][k] = temp;
            }

            if (a[1][k] > a[2][k])
            {
                temp = a[2][k];
                a[2][k] = a[1][k];
                a[1][k] = temp;
            }

            if (a[0][k] > a[1][k])
            {
                temp = a[1][k];
                a[1][k] = a[0][k];
                a[0][k] = temp;
            }

        }
        //Second Column Check
        {
            if (a[0][k + 1] > a[1][k + 1])
            {
                temp = a[1][k + 1];
                a[1][k + 1] = a[0][k + 1];
                a[0][k + 1] = temp;
            }

            if (a[1][k + 1] > a[0][k + 2])
            {
                temp = a[0][k + 2];
                a[0][k + 2] = a[1][k + 1];
                a[1][k + 1] = temp;
            }

            if (a[0][k + 1] > a[1][k + 1])
            {
                temp = a[1][k + 1];
                a[1][k + 1] = a[0][k + 1];
                a[0][k + 1] = temp;
            }
        }

        //3 Diagonal Checks
        if (a[0][k + 1] < a[1][k])
        {
            temp = a[1][k];
            a[1][k] = a[0][k + 1];
            a[0][k + 1] = temp;
        }
        if (a[2][k] > a[1][k + 1])
        {
            temp = a[1][k + 1];
            a[1][k + 1] = a[2][k];
            a[2][k] = temp;
        }
        if (a[2][k] > a[0][k + 1])
        {
            temp = a[0][k + 1];
            a[0][k + 1] = a[2][k];
            a[2][k] = temp;
        }    
        //Upper Triangle Sorted
        k = k + 2;
        if (k == (col - 1))flag = 1;
    }

    else if ((k % 2 == 0) && (flag == 1))
    {
        //Sorting Lower Triangle
        //3 row check
        if (a[2][k - 2]>a[0][k])
        {
            temp = a[0][k];
            a[0][k] = a[2][k - 1];
            a[2][k - 2] = temp;
        }

        if (a[1][k - 1] > a[1][k])
        {
            temp = a[1][k];
            a[1][k] = a[1][k - 1];
            a[1][k - 1] = temp;
        }

        if (a[2][k - 1] > a[2][k])
        {
            temp = a[2][k];
            a[2][k] = a[2][k - 1];
            a[2][k - 1] = temp;
        }

        //First Column Check
        {
            if (a[2][k - 2] > a[1][k - 1])
            {
                temp = a[1][k - 1];
                a[1][k - 1] = a[2][k - 2];
                a[2][k - 2] = temp;
            }

            if (a[1][k - 1] > a[2][k - 1])
            {
                temp = a[2][k - 1];
                a[2][k - 1] = a[1][k - 1];
                a[1][k - 1] = temp;
            }

            if (a[2][k - 2] > a[1][k - 1])
            {
                temp = a[1][k - 1];
                a[1][k - 1] = a[2][k - 2];
                a[2][k - 2] = temp;
            }

        }

        //Second Column Check
        {
            if (a[0][k] > a[1][k])
            {
                temp = a[1][k];
                a[1][k] = a[0][k];
                a[0][k] = temp;
            }

            if (a[1][k] > a[2][k])
            {
                temp = a[2][k];
                a[2][k] = a[1][k];
                a[1][k] = temp;
            }

            if (a[0][k] > a[1][k])
            {
                temp = a[1][k];
                a[1][k] = a[0][k];
                a[0][k] = temp;
            }
        }

        //3 Diagonal Checks
        if (a[0][k] < a[1][k - 1])
        {
            temp = a[1][k - 1];
            a[1][k - 1] = a[0][k];
            a[0][k] = temp;
        }
        if (a[2][k - 1] > a[1][k])
        {
            temp = a[1][k];
            a[1][k] = a[2][k - 1];
            a[2][k - 1] = temp;
        }
        if (a[2][k - 1] > a[0][k])
        {
            temp = a[0][k];
            a[0][k] = a[2][k - 1];
            a[2][k - 1] = temp;
        }
        //Lower Triangle Sorted
        k = k - 2;
        if (k == 0)flag = 0;
    }


}


//Code to print the sorted elements
cout << "Sorted Elements:" << endl;

for (int i = 0; i < col; i++)
for (int j = 0; j < 3; j++)
{
    cout << a[j][i] << " ";
}

//Code to check if the elements are sorted or not
int l = 0;
int s = a[0][0];
for (int i = 0; i < col;i++)
for (int j = 0; j < 3; j++)
{
    if (s > a[j][i])l++;
    s = a[j][i];
}

if (l == 0)cout << "\nSorted Array!\n";
else cout << "\nUnsorted!\n";

system("pause");
goto A;

}

My recommendation is to first do a statistical analysis before doing any theoretical analysis, the reason being a. it's easy to do and b. it will save you from any potential surprises later. I say this because when I once developed a sorting algorithm that had worst case n * log(n) comparisons and constant space overhead, yet its wall clock time was n^2 - I then discovered that the algorithm was performing n^2 swaps. Start by measuring wall clock time, if it's approx. n*log(n) then you can probably get away with only doing theoretical analysis on comparisons, not swaps — Zim-Zam O'Pootertoot, Apr 29 '15 at 18:36
How can I do that? P.S: I am 17 years old and I am self learning on how to code. For example, is there any software I can make use of? Or I have to go with the traditional ? and if so, how should I move along with statistical analysis? — Anand Akshay, Apr 29 '15 at 18:38
[Here](http://stackoverflow.com/questions/2808398/easily-measure-elapsed-time) is an explanation on how to measure the program's run time. Then randomly generate several inputs of varying lengths and sort them, outputting the length and sort time to the console - be certain that you only time the sort phase, not the input generation phase. Graph the results, x-axis is the input length and y-axis is the sort time. Hopefully it will be immediately apparent whether it's n * log(n) or n^2, otherwise an [interpolation](http://en.wikipedia.org/wiki/Interpolation) library will help — Zim-Zam O'Pootertoot, Apr 29 '15 at 18:44
I would also wish to take random inputs from a test.txt file. What code can I use to perform the same? The Graph that I expect would be less that n^2 but higher than n log(n) — Anand Akshay, Apr 30 '15 at 03:02

Zim-Zam O'Pootertoot · Answer 1 · 2015-04-29T19:27:39.610

1

Looking through the algorithm, it would initially appear that this is an O(n) time complexity sorting algorithm if we treat the constant factor as a constant (you've got one loop with C * n iterations), but a comparison based sorting algorithm has a lower bound of O(n * log(n)). This either means that a. you're not successfully sorting the data in the traditional sense of the word (I'm assuming this isn't the case), b. you're doing a non-comparison sort (and it appears that you are doing a comparison sort), or c. the constant factor can't be treated as a constant (this is almost certainly the case, particularly because the constant factor is larger for larger inputs).

How are you determining the constant factor? What is its relation to the input size? What you need to determine (e.g. statistically as I described in the comments) is whether this relation is e.g. "constant factor = C * log(input size)", or "constant factor = C * (input size)", or something in between.

Space complexity appears to be a constant, because you're not dynamically allocating any memory or using a swap array or anything like that, nor are you using recursion.

edited Apr 29 '15 at 19:27

answered Apr 29 '15 at 19:22

Zim-Zam O'Pootertoot

17,888
4
41
69

Constant Factor = log(2) * log(2) * (input Size) – Anand Akshay Apr 30 '15 at 03:42
@AnandAkshay Do you mean log_base_2(input size), or do you mean log_base_10(2) * (input size)? If you mean the second one then this would be an O(n^2) algorithm, because log_base_10(2) is a constant (albeit a small one), so you get log(2)^2 * (input size)^2 => C * n^2 => O(n^2) – Zim-Zam O'Pootertoot Apr 30 '15 at 15:21
The constant factor of my algorithm increases as the number of elements increases but the constant factor never equals the no. Of elements and is always less than half of the input size. What is the time complexity then? I suspect the time complexity would be between O(nlogn) and O(n^2) – Anand Akshay Apr 30 '15 at 17:49
@AnandAkshay I'd need to know the function that determines the size of the constant factor, say g(n) - the time complexity is O(g(n) * n), e.g. if g(n) is log(n) then the time complexity is O(log(n) * n). If you're experimentally determining the constant factor then you could use [interpolation](http://en.wikipedia.org/wiki/Interpolation) to determine g(n) – Zim-Zam O'Pootertoot Apr 30 '15 at 17:57

What would be the space and time complexity of my sorting algorithm?

1 Answers1

Linked