bubble sort

This is a discussion on bubble sort within the C Programming forums, part of the General Programming Boards category; Why does this bubble sort only make one pass? If I remove "swap" it sorts correctly, but from looking at ...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    380

    bubble sort

    Why does this bubble sort only make one pass? If I remove "swap" it sorts correctly, but from looking at two books with similiar code that would be creating a slower bubble sort.

    Code:
    for(outer = 0; outer < (numList-1); outer++)
     {
    	swap = 0; // Initialize after each pass
    	for(inner = outer; inner < numList; inner++)
    	 {
    	  if(strcmp(info[outer].lname,info[inner].lname) > 0)
    		{
    		  temp = info[outer];
    		  info[outer] = info[inner];
    		  info[inner] = temp;
    		  swap = 1;
    		}
    	 }
    	if(!swap) /* if no swap end sort */
    	 {break;}
    }

  2. #2
    Registered User sean345's Avatar
    Join Date
    Mar 2002
    Posts
    346
    > for(outer = 0; outer < (numList-1); outer++)
    Instead of looping this way I would just say
    Code:
    while(swap)
    This way when there is no more swapping to do the loop will end.

    - Sean
    If cities were built like software is built, the first woodpecker to come along would level civilization.
    Black Frog Studios

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    380
    Wouldn't the sort still only do one pass?

  4. #4
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    I think you're loop counters are incorrect. Here's your code revised:

    Code:
    for (outer = 0; outer < (numList - 1); outer++)
    {
    	swap = 0;	// Initialize after each pass
    	for (inner = 0; inner < (numList - 1 - outer); inner++)
    	{
    		if (strcmp(info[inner].lname, info[inner+1].lname) > 0)
    		{
    			temp = info[inner];
    			info[inner] = info[inner+1];
    			info[inner+1] = temp;
    			swap = 1;
    		}
    	}
    	if (!swap)	/* if no swap end sort */
    	{
    		break;
    	}
    }
    And the skeleton I based it on:
    Code:
    for (i=0; i<n-1; i++) {
      for (j=0; j<n-1-i; j++)
        if (a[j+1] < a[j]) {  /* compare the two neighbors */
          tmp = a[j];         /* swap a[j] and a[j+1]      */
          a[j] = a[j+1];
          a[j+1] = tmp;
      }
    }
    As we can see, the algorithm consists of two nested loops. The index j in the inner loop travels up the array, comparing adjacent entries in the array (at j and j+1), while the outer loop causes the inner loop to make repeated passes through the array. After the first pass, the largest element is guaranteed to be at the end of the array, after the second pass, the second largest element is in position, and so on. That is why the upper bound in the inner loop (n-1-i) decreases with each pass: we don't have to re-visit the end of the array.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bubble sort not working... wats d prob?
    By Huskar in forum C Programming
    Replies: 8
    Last Post: 04-01-2009, 12:59 AM
  2. My bubble sort only sorts once
    By Muller in forum C Programming
    Replies: 8
    Last Post: 03-27-2009, 05:36 PM
  3. Bubble Sort... which type?
    By gflores in forum C++ Programming
    Replies: 8
    Last Post: 08-15-2004, 05:48 AM
  4. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 04:54 PM
  5. Help with Bi-Directional Bubble Sort in C
    By cunninglinguist in forum C Programming
    Replies: 0
    Last Post: 04-19-2002, 03:32 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21