0
int ascendingSort(int* a, int n) {
    int i=0, temp=0;
    for (i = 0; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
            temp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = temp;
            i = -1;
        }
    }
    return a;
}

void main() {
    int a[] = { 1,5,9,2,3 };
    int n = sizeof(a) / sizeof(int);
    int result = ascendingSort(a, n);
    for (int i = 0; i < n; i++) {
        printf("%d", a[i]);
    }
}

Im trying to Bubble sort the array in ascending order, Im not sure if the time complexity is O(n)? and if not how can I improve it?

Snir Taub
  • 3
  • 3
  • You shouldn't be returning `a`. `a` is an int pointer, not an int. Either change what you're turning, return nothing, or change the return type to `int *` – codyne Jan 03 '22 at 22:19
  • About your time complexity, at a glance it looks like it's worst case `O(2 * n^2)` which is much worse than bubble sorts worst case. – codyne Jan 03 '22 at 22:22
  • 1
    Related: [Is there an O(n) integer sorting algorithm?](https://stackoverflow.com/questions/2352313/is-there-an-on-integer-sorting-algorithm) – Weather Vane Jan 03 '22 at 22:26
  • @codyne O(2 * n^2) aka O(n^2) would be exactly Bubble Sort's worst case – ikegami Jan 03 '22 at 22:58
  • Re "*Im not sure if the time complexity is O(n)?*", It is not. you keep resetting `i` every time you do a swap. – ikegami Jan 03 '22 at 23:00

1 Answers1

0

It's worse than linear (O(n)). You keep resetting i every time you do a swap causing the same elements to be compared multiple times.

The following function is completely equivalent to yours, but makes the fact that it's not linear a lot more obvious:

void ascendingSort(int* a, int n) {
    int i=0, temp=0;
    for (i = 0; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
            temp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = temp;
            ascendingSort(a, i+2);   // Was i = -1;
        }
    }
}

The worse case occurs when we have to perform the most swaps, and this occurs when the list is in the opposite order that we desire. When that's the case, we get the following number of compares:

  • n = 0, 0 compares.
  • n = 1, 0 compares.
  • n = 2, 2 compares.
  • n = 3, 6 compares.
  • n = 4, 13 compares.
  • n = 5, 24 compares.
  • n = 6, 40 compares.
  • n = 7, 62 compares.

This sequence is given by the formula (n^3 + 5*n + 6) / 6. I can't prove this, but it it would make your algorithm O(n3) if accurate.

ikegami
  • 367,544
  • 15
  • 269
  • 518