There are a lot of algorithms available for sorting a set of numbers. Here I will give you the logic behind bubble sort and a c++ function implementing the same. The bubble sort can be used to sort a given set of numbers either in ascending order or in descending order in minimum number of iterations. Bubble sort starts by comparing the first two numbers and arranging them in the correct order, then the next two numbers and again arranging them. This process is repeated for all the numbers in the list a number of times until the list is sorted.
To implement bubble sort, two loops are required, the inner loop swaps two adjacent numbers throughout the array and the outer loop causes the inner loop to repeat a numbers of times. Now lets us consider the case of sorting numbers in ascending order. In this case, when the inner loop completes one iteration, the largest number will be moved to the end of the array. When the inner loop completes the second iteration, then the second largest number will be moved to the second last position in the array and so on. Now here is the code to perform bubble sort.
When the above function is run by passing an array and number of elements in it, the array will be sorted in ascending order.
The function can be easily altered to sort the array in descending order. This can be done by changing the if condition. The function to sort in descending order is given below.
In the above two functions, the swapping is implemented using a third variable temp. This variable can be eliminated to reduce memory consumption. Algorithm to swap two numbers without using a third variable is given in a previous posting (Click Here). The three lines inside the if block can be replaced with the code obtained from the given link. This would not cause much of a difference in performance.
To implement bubble sort, two loops are required, the inner loop swaps two adjacent numbers throughout the array and the outer loop causes the inner loop to repeat a numbers of times. Now lets us consider the case of sorting numbers in ascending order. In this case, when the inner loop completes one iteration, the largest number will be moved to the end of the array. When the inner loop completes the second iteration, then the second largest number will be moved to the second last position in the array and so on. Now here is the code to perform bubble sort.
//Code uses c++ Syntax
//Function accepts pointer to array and number of elements in array
void bubbleSortAsc(int &arr, int num)
{
int temp;
for(int i=0;i<num;i++)
{
for(int j=0;j<(num-i-1);j++)
{
if(arr[j]>arr[j+1])
{
//Swap two numbers
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
//End of function
When the above function is run by passing an array and number of elements in it, the array will be sorted in ascending order.
The function can be easily altered to sort the array in descending order. This can be done by changing the if condition. The function to sort in descending order is given below.
//Code uses c++ Syntax
//Function accepts pointer to array and number of elements in array
void bubbleSortDsc(int &arr, int num)
{
int temp;
for(int i=0;i<num;i++)
{
for(int j=0;j<(num-i-1);j++)
{
if(arr[j]<arr[j+1])
{
//Swap two numbers
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
//End of function
In the above two functions, the swapping is implemented using a third variable temp. This variable can be eliminated to reduce memory consumption. Algorithm to swap two numbers without using a third variable is given in a previous posting (Click Here). The three lines inside the if block can be replaced with the code obtained from the given link. This would not cause much of a difference in performance.
No comments:
Post a Comment