-2

I was trying to find a way to sort arrays with the smallest time complexity possible. I was thinking that the following is O(n), however that seems unlikely to me because the currently existing methods to sort arrays have at best O(nlogn). My question is what is the big O complexity of this method in java and how is it calculated?

public static void ArrSort(int[] arr){
        int temp;
        for(int j=0;j<arr.length;j++)
        {
            if(arr[j]>arr[j+1]) {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                if(j==0)
                    j=-1;
                else
                    j=j-2;
            }
        }
Cleophatt
  • 7
  • 2
  • I think the algorithm that you are using is [Bubble-sort](https://www.geeksforgeeks.org/bubble-sort/) where you sort an array by swapping two elements. Take a look, there are lots of sorting algorithms out there! [Sorting algorithms](https://www.geeksforgeeks.org/sorting-algorithms/) – Mohamad Ghaith Alzin May 22 '22 at 00:43
  • This is insertion sort, and its complexity is O(n²). – Caesar May 22 '22 at 00:47
  • 4
    This is `ArrayIndexOutOfBoundsException` sort, and its complexity is too damn high. – akuzminykh May 22 '22 at 01:06
  • 1
    Off topic: I was taught that altering the value of the index of a `for` loop is bad form, and makes the code hard to follow. Consider using a `while` loop instead. – Old Dog Programmer May 22 '22 at 04:17

1 Answers1

0

Its time complexity is NOT O(n) at all. Your algorithm that dealing with array's index j made its time complexity seemed to be O(n) because of containing one single loop only, but actually this loop won't end with runing codes inside n-times only. For some average condition, this number will rise to n^2 times acturally. It's a O(n²) sort algorithm.

Xiaoqian
  • 16
  • 2