Logic:
Bubble sort algorithm used for sorting purpose.
Two pointer used to point first and second position of element.
Each element is compared with next element.
If next element is smaller than previous then swapping operation is done and both pointer incremented by 1.
Complexity- Average case complexity O(n^2)
Best case O(n)
// C program for implementation of Bubble sort
#include <stdio.h>
void swap(int *xp, int *yp);
void bubbleSort(int arr[], int n) ;
void printArray(int arr[], int size);
int main()
{ int arr[10],n,i;
printf("\n Enter number of element in random array:");
scanf("%d",&n);
printf("\n Enter element of array :");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("\n Entered array is :");
printArray(arr,n);
// int arr[] = {64, 34, 25, 12, 22, 11, 90};
// int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("\nSorted array: \n");
printArray(arr, n);
return 0;
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf(" \'%d\' ", arr[i]);
// printf("\n");
}
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
{ if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
printf("\n Element of array at \'%d\' iteration\'%d\' pass\t:",i,j);
printArray(arr,n);
printf("\t Swap %d with %d",arr[j],arr[j+1]);
}
}
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
/*
Output
Enter number of element in random array:
Enter element of array :
Entered array is : '6' '5' '4' '3' '2'
Element of array at '0' iteration'0' pass : '5' '6' '4' '3' '2' Swap 5 with 6
Element of array at '0' iteration'1' pass : '5' '4' '6' '3' '2' Swap 4 with 6
Element of array at '0' iteration'2' pass : '5' '4' '3' '6' '2' Swap 3 with 6
Element of array at '0' iteration'3' pass : '5' '4' '3' '2' '6' Swap 2 with 6
Element of array at '1' iteration'0' pass : '4' '5' '3' '2' '6' Swap 4 with 5
Element of array at '1' iteration'1' pass : '4' '3' '5' '2' '6' Swap 3 with 5
Element of array at '1' iteration'2' pass : '4' '3' '2' '5' '6' Swap 2 with 5
Element of array at '2' iteration'0' pass : '3' '4' '2' '5' '6' Swap 3 with 4
Element of array at '2' iteration'1' pass : '3' '2' '4' '5' '6' Swap 2 with 4
Element of array at '3' iteration'0' pass : '2' '3' '4' '5' '6' Swap 2 with 3
Sorted array:
'2' '3' '4' '5' '6'
*/
No comments:
Post a Comment