Sort an array using bubble sort using C programming language

Sort an array using bubble sort using C programming language.

Code:

#include <stdio.h>

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
}
}
}
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

bubbleSort(arr, n);

printf("\nSorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

This code defines the swap function to swap two elements, the bubbleSort function to perform the bubble sort algorithm, and the main function to demonstrate the sorting process on an example array. The bubble sort algorithm repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated for all elements until the array is sorted.

Keep in mind that bubble sort is not the most efficient sorting algorithm for large arrays, as its time complexity is O(n^2). There are more efficient sorting algorithms like quicksort or mergesort for larger datasets.

 

Explanation:

#include <stdio.h>

This line includes the standard input-output library, which provides functions for input and output operations like printf and scanf.

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

This defines a function named swap that takes two integer pointers (int *a and int *b) as arguments. It swaps the values of the integers pointed to by a and b using a temporary variable temp.

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
}
}
}
}

This defines the bubbleSort function, which takes an integer array arr and its size n as arguments. It implements the bubble sort algorithm. The outer loop iterates from the beginning of the array to the second-to-last element. The inner loop iterates from the beginning of the array to the current last unsorted element. If an element is greater than the next element, the swap function is called to swap their positions, pushing the larger element towards the end of the array. This process is repeated until the entire array is sorted.

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

In the main function, an integer array arr is initialized with values. The sizeof operator is used to calculate the size of the array in bytes, and by dividing it by the size of an individual element, we get the number of elements in the array (n).

printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

This loop prints out the elements of the original array before sorting.

bubbleSort(arr, n);

The bubbleSort function is called to sort the array.

printf("\nSorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

This loop prints out the elements of the sorted array after applying the bubble sort algorithm.

return 0;
}

The main function returns 0 to indicate successful execution of the program.

Overall, this program demonstrates the bubble sort algorithm by sorting an example array and printing the original and sorted arrays.

 

Algorithm:

Bubble Sort Algorithm:

1. Start with an unsorted array of elements.

2. Repeat the following steps for each element in the array: a. Iterate through the array from the beginning to the (n - 1 - i)th element, where 'i' is the current iteration index. b. Compare each element with its adjacent element. c. If the current element is greater than the next element, swap their positions.

3. After completing each iteration, the largest unsorted element will "bubble up" to the last position.

4. Continue these steps for (n - 1) iterations, where 'n' is the number of elements in the array.

5. The array is now sorted.

Algorithm of above C program:

1. Include the standard input-output library (stdio.h).

2. Define a function named swap that takes two integer pointers as parameters:

   • Store the value pointed to by the first pointer in a temporary variable.

   • Assign the value pointed to by the second pointer to the first pointer.

   • Assign the temporary variable's value to the second pointer.

3. Define a function named bubbleSort that takes an integer array and its size as parameters:

   • Start an outer loop that iterates from 0 to n - 2 (where n is the size of the array).

     • Start an inner loop that iterates from 0 to n - i - 2, where i is the current iteration of the outer loop.

       • Compare the element at index j with the element at index j + 1.

       • If the element at index j is greater than the element at index j + 1, call the swap function to swap the elements.

4. In the main function:

   • Initialize an integer array arr with values.

   • Calculate the number of elements in the array using sizeof and element size.

   • Print the original array using a loop.

5. Call the bubbleSort function to sort the array.

6. Print the sorted array using a loop.

7. Return 0 to indicate successful program execution.

This algorithm demonstrates the bubble sort process of comparing and swapping adjacent elements repeatedly until the array is sorted. Keep in mind that bubble sort is not the most efficient sorting algorithm for large arrays due to its O(n^2) time complexity, but it serves as a simple example of a sorting algorithm.

 

Time Complexity:

The time complexity of the above bubble sort algorithm is O(n^2), where "n" is the number of elements in the array being sorted.

Here's why:

In the worst case, for each element in the array, the bubble sort algorithm compares it with all the remaining elements to the right of it and swaps if necessary. This results in a nested loop structure:

• The outer loop runs (n - 1) times, where "n" is the number of elements in the array. This is because the last element doesn't need to be compared since there's no element to its right.

• The inner loop runs (n - i - 1) times, where "i" is the current iteration of the outer loop. This accounts for the fact that after each iteration of the outer loop, the largest element "bubbles up" to its correct position at the end of the array, and the remaining unsorted portion of the array becomes smaller by one element.

This results in a total of (n - 1) * (n - 1) = n^2 - 2n + 1 comparisons and swaps in the worst case.

Since we are interested in the dominant term that affects the growth of the algorithm as the input size increases, we can drop the lower-order terms and constants. Thus, the time complexity of bubble sort simplifies to O(n^2).

Bubble sort is not very efficient for large arrays due to its quadratic time complexity. There are more efficient sorting algorithms like quicksort, mergesort, and heapsort that have better average and worst-case time complexities for larger datasets.

 

Space Complexity:

The space complexity of the provided bubble sort algorithm is O(1), which means it uses a constant amount of extra space that does not depend on the size of the input array.

Here's why:

1. Input Space: The input array is the main input to the algorithm. However, the space required for the input is not considered in the space complexity analysis, as it's a part of the input itself and not additional space used by the algorithm.

2. Temporary Variables: The algorithm uses a few temporary variables, such as temp in the swap function. These temporary variables require a constant amount of space, regardless of the size of the input array. Therefore, their space usage does not grow with the input size.

3. Loop Variables: The algorithm uses loop variables like i and j to control the iterations. These variables also require constant space since they do not increase with the size of the input array.

4. Function Call Stack: The algorithm involves function calls, but these function calls do not accumulate on the call stack because the recursive stack is not used. The memory required for function call overhead is relatively constant.

Since the extra space used by the algorithm remains constant, regardless of the size of the input array, the space complexity is O(1).

Keep in mind that space complexity analysis usually focuses on the additional space used by the algorithm itself, excluding the space required for the input data.