C program - modify bubble sort - need someone to check my code
-
Hello, i need to sort out this problem: "The bubble sort represented in fig 6.15 of your text book is inefficient for large arrays. Make the following simple modifications to improve the performance of the bubble sort. After the first pass, the largest number is guaranteed to be in the highest-numbered element of the array; after the second pass, the two highest numbers are “in place,” and so on. Instead of making nine comparisons on every pass, modify the bubble sort to make eight comparisons on the second pass, seven on the third pass and so on." Could someone check my code? I should get an output like this but i don't:confused:: After pass 0: 2 4 6 8 10 12 68 45 37 89 After pass 1: 2 4 6 8 10 12 45 37 68 After pass 2: 2 4 6 8 10 12 37 45 After pass 3: 2 4 6 8 10 12 37 After pass 4: 2 4 6 8 10 12 After pass 5: 2 4 6 8 10 After pass 6: 2 4 6 8 After pass 7: 2 4 6 After pass 8: 2 4 There is something wrong with the loop... Thanks a lot!!! raeiko
/* Program that modifies the bubble sort array in fig. 6.15 */
#include <stdio.h>
#define SIZE 10int main ( void )
{
int a[ SIZE ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 }; /* declare and initialize array a */
int pass; /* passes counter */
int i; /* comparisons counter */
int hold; /* temporary location used to swap arrays elements */
int NumOfComparisons = 0;printf( "Data items in original order:\\n\\n" ); for ( i = 0; i <SIZE; i++ ){ /\* display array output \*/ printf( "%4d", a\[ i \] ); } /\* end of for loop \*/ printf( "\\n\\n" ); /\* bubble sort \*/ for ( pass = 1; pass < 9; pass++ ){ for ( i = 0; i < 9 - pass; i++ ){ if ( a\[ i \] > a\[ i + 1\] ){ hold = a\[ i \]; a\[ i \] = a\[ i + 1\]; a\[ i + 1\] = hold; }/\* end of if \*/ NumOfComparisons = NumOfComparisons + 1; }/\* end of inner for \*/ for ( i = 0; i < SIZE - pass; i++ ){ printf( "After pass %d: %4d\\n", pass, a\[ i \] ); /\* the problem should be here \*/ printf( "\\n " ); }/\* end of for \*/ }/\* end of outer for \*/ printf( "Data items in ascending order:\\n\\n" ); for ( i = 0; i < SIZE; i++ ){ /\* output array in ascending order \*/ printf( "%4d", a\[ i \] ); } printf( "\\n\\n" ); printf( "Number of comparisons: %d\\n", NumOfComparisons );return 0;
} -
Hello, i need to sort out this problem: "The bubble sort represented in fig 6.15 of your text book is inefficient for large arrays. Make the following simple modifications to improve the performance of the bubble sort. After the first pass, the largest number is guaranteed to be in the highest-numbered element of the array; after the second pass, the two highest numbers are “in place,” and so on. Instead of making nine comparisons on every pass, modify the bubble sort to make eight comparisons on the second pass, seven on the third pass and so on." Could someone check my code? I should get an output like this but i don't:confused:: After pass 0: 2 4 6 8 10 12 68 45 37 89 After pass 1: 2 4 6 8 10 12 45 37 68 After pass 2: 2 4 6 8 10 12 37 45 After pass 3: 2 4 6 8 10 12 37 After pass 4: 2 4 6 8 10 12 After pass 5: 2 4 6 8 10 After pass 6: 2 4 6 8 After pass 7: 2 4 6 After pass 8: 2 4 There is something wrong with the loop... Thanks a lot!!! raeiko
/* Program that modifies the bubble sort array in fig. 6.15 */
#include <stdio.h>
#define SIZE 10int main ( void )
{
int a[ SIZE ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 }; /* declare and initialize array a */
int pass; /* passes counter */
int i; /* comparisons counter */
int hold; /* temporary location used to swap arrays elements */
int NumOfComparisons = 0;printf( "Data items in original order:\\n\\n" ); for ( i = 0; i <SIZE; i++ ){ /\* display array output \*/ printf( "%4d", a\[ i \] ); } /\* end of for loop \*/ printf( "\\n\\n" ); /\* bubble sort \*/ for ( pass = 1; pass < 9; pass++ ){ for ( i = 0; i < 9 - pass; i++ ){ if ( a\[ i \] > a\[ i + 1\] ){ hold = a\[ i \]; a\[ i \] = a\[ i + 1\]; a\[ i + 1\] = hold; }/\* end of if \*/ NumOfComparisons = NumOfComparisons + 1; }/\* end of inner for \*/ for ( i = 0; i < SIZE - pass; i++ ){ printf( "After pass %d: %4d\\n", pass, a\[ i \] ); /\* the problem should be here \*/ printf( "\\n " ); }/\* end of for \*/ }/\* end of outer for \*/ printf( "Data items in ascending order:\\n\\n" ); for ( i = 0; i < SIZE; i++ ){ /\* output array in ascending order \*/ printf( "%4d", a\[ i \] ); } printf( "\\n\\n" ); printf( "Number of comparisons: %d\\n", NumOfComparisons );return 0;
}1. You've got the loop bounds for pass and i wrong (hint - think SIZE) 2. Your print loop contents is incorrect Apart from that, the algorithm's correct.
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
-
Hello, i need to sort out this problem: "The bubble sort represented in fig 6.15 of your text book is inefficient for large arrays. Make the following simple modifications to improve the performance of the bubble sort. After the first pass, the largest number is guaranteed to be in the highest-numbered element of the array; after the second pass, the two highest numbers are “in place,” and so on. Instead of making nine comparisons on every pass, modify the bubble sort to make eight comparisons on the second pass, seven on the third pass and so on." Could someone check my code? I should get an output like this but i don't:confused:: After pass 0: 2 4 6 8 10 12 68 45 37 89 After pass 1: 2 4 6 8 10 12 45 37 68 After pass 2: 2 4 6 8 10 12 37 45 After pass 3: 2 4 6 8 10 12 37 After pass 4: 2 4 6 8 10 12 After pass 5: 2 4 6 8 10 After pass 6: 2 4 6 8 After pass 7: 2 4 6 After pass 8: 2 4 There is something wrong with the loop... Thanks a lot!!! raeiko
/* Program that modifies the bubble sort array in fig. 6.15 */
#include <stdio.h>
#define SIZE 10int main ( void )
{
int a[ SIZE ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 }; /* declare and initialize array a */
int pass; /* passes counter */
int i; /* comparisons counter */
int hold; /* temporary location used to swap arrays elements */
int NumOfComparisons = 0;printf( "Data items in original order:\\n\\n" ); for ( i = 0; i <SIZE; i++ ){ /\* display array output \*/ printf( "%4d", a\[ i \] ); } /\* end of for loop \*/ printf( "\\n\\n" ); /\* bubble sort \*/ for ( pass = 1; pass < 9; pass++ ){ for ( i = 0; i < 9 - pass; i++ ){ if ( a\[ i \] > a\[ i + 1\] ){ hold = a\[ i \]; a\[ i \] = a\[ i + 1\]; a\[ i + 1\] = hold; }/\* end of if \*/ NumOfComparisons = NumOfComparisons + 1; }/\* end of inner for \*/ for ( i = 0; i < SIZE - pass; i++ ){ printf( "After pass %d: %4d\\n", pass, a\[ i \] ); /\* the problem should be here \*/ printf( "\\n " ); }/\* end of for \*/ }/\* end of outer for \*/ printf( "Data items in ascending order:\\n\\n" ); for ( i = 0; i < SIZE; i++ ){ /\* output array in ascending order \*/ printf( "%4d", a\[ i \] ); } printf( "\\n\\n" ); printf( "Number of comparisons: %d\\n", NumOfComparisons );return 0;
}Don't like to do exercise for others :-D Anyway, the following is the fastest possible bubble sort I know;
// Assusme an array A of ints of size N.
bool sorted = false; // THIS MAKES THE TRICK
for (int i=1; i<N && !sorted; ++i)
{
sorted = true;
for (int j=0; j<N-i; ++j)
{
int k = j + 1;
if (A[j] > A[k]) {
int t = A[j];
A[j] = A[k];
A[k] = t;
sorted = false;
}
}
}-- Arman