CODEWITHSUNDEEP
carrayssortingbubble-sortcs50
kartikeykant18
kartikeykant18

Reputation: 1811

Following Bubble sort not working in C

I am writing a sort function to implement a bubble sort in C but it is not sorting the given array. Here is the following code. I am using a void function so I cannot return the array and have to make changes in the existing array. The code compiles well and runs but it does not sort the array.

void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm
    for(int i = 0; i < n; i++)
    {
        int sp = 0;
        for(int j = 0; j < n; j++)
        {
            if (values[i] > values[i + 1])
            {
                int first_val = values[i];
                int second_val = values[i + 1];

                values[i] = second_val;
                values[i + 1] = first_val;
                sp = 1;
            }
        }
        if (sp == 0)
        {
            break;
        }
    }
}

Upvotes: 1

Views: 990

Answers (3)

Sumit Gemini
Sumit Gemini

Reputation: 1836

In Bubble Sort, n-1 comparisons will be done in 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be

(n-1)+(n-2)+(n-3)+.....+3+2+1
Sum = n(n-1)/2
i.e O(n2)

So two things you need to change in your code :-

  1. condition in inner loop will be for(j=0;j< n-i-1;j++).
  2. No need to take two variable to swap data. Space complexity for Bubble Sort is O(1), because only single additional memory space is required for temp variaable.

Upvotes: 2

kartikeykant18
kartikeykant18

Reputation: 1811

The code seems to be working now with the following code:

void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm
    for(int i = 0; i < n-1; i++)
    {
        int sp = 0;
        for(int j = 0; j < n-1; j++)
        {
            if (values[j] > values[j + 1])
            {
                int first_val = values[j];
                int second_val = values[j + 1];

                values[j] = second_val;
                values[j + 1] = first_val;
                sp = 1;
            }
        }
        if (sp == 0)
        {
            break;
        }
    }

}

Upvotes: 0

cokceken
cokceken

Reputation: 2076

You access values[i + 1] by saying values[i] > values[i + 1]. So natural limit of i should be n-1 

for(int i = 0; i < n - 1; i++)

Upvotes: 3

Related Questions