#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2012
    Posts
    31
    Rep Power
    6

    Unhappy Bubble sort not working


    Hey guys,

    I'm attempting to implement bubble sort in C++ with the following code:
    Code:
    int main() {
    	
    	int numbers[10] = {3, 4, 1, 7, 1, 8, 101, 89, 10, 47};
    	
    	// print array
    	cout << "numbers array before bubble sort:" << endl;
    	for (int i = 0; i < 10; i++) {
    		cout << numbers[i] << " ";
    	}
    	cout << endl;
    	
    	int total_passes = 0;
    	
    	for (int i = 0; i < 9; i++) {
    		for (int j = i + 1; j < 10 - i; j++) {
    			total_passes++;
    			if (numbers[i] > numbers[j]) {
    				int temp = numbers[i];
    				numbers[i] = numbers[j];
    				numbers[j] = temp;
    			}
    		}
    	}
    	
    	// print array
    	cout << "numbers array after bubble sort:" << endl;
    	for (int i = 0; i < 10; i++) {
    		cout << numbers[i] << " ";
    	}
    	cout << endl;
    	
    	// report total passes
    	cout << "Total passes = " << total_passes << endl;
    	
    	return 0;
    }
    The inner loop is supposed to be reduced by one each time (i.e. the first time round it loops 9 times, the second time it loops 8 times etc.) because after the first inner loop the last item in the array is the largest number, after the second time round the inner loop the largest two numbers are the last two items in the array etc.

    I'm getting the following output:
    Code:
    numbers array before bubble sort:
    3 4 1 7 1 8 101 89 10 47 
    numbers array after bubble sort:
    1 1 3 4 7 8 101 89 10 47 
    Total passes = 25

    Any idea where I'm going wrong?

    Cheers!

    Miktor
  2. #2
  3. Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Aug 2011
    Posts
    5,791
    Rep Power
    508
    All bubble sorts are currently failing because of the pico black hole swarm earth is encountering. Gravity at the cpu level is currently indeterminate. Run your program again in spring, when astronomers say earth shall be out of this mess. https://www.youtube.com/watch?v=1XM0x_qSeOk

    Despite this desperate circumstance, we'll do what we can.

    1) Abhor duplicate code. I've inserted a display function (candidate for a template, and to use vectors). Write the code just once.
    2) fix the bubble sort. Never use bubble sort. It's better, I'll admit than the doubly random swap sort of which I forget the name, and the performance of bubble sort on a presorted list is also tops.

    (your bubble sort implementation does not have optimal performance for presorted list)
    [edit]Now looking at following program I discover that it is a program that sorts, however it is not bubble sort.[/edit]
    Code:
    #include<iostream>
    
    const int N = 10;
    
    void display(const char*title, int*v, const int n) {
      std::cout << title << std::endl;
      for (int i = 0; i < n; i++) {
        std::cout << v[i] << " ";
      }
      std::cout << std::endl;
    }
    
    int main() {
    	
      int numbers[N] = {3, 4, 1, 7, 1, 8, 101, 89, 10, 47};
      int total_passes = 0;
    	
      display("numbers array before bubble sort:", numbers, N);
    	
    	
      for (int i = 0; i < (N-1); i++) {
        for (int j = i + 1; j < N; j++) { // changed the upper limit on this line
          total_passes++;
          if (numbers[i] > numbers[j]) {
    	int temp = numbers[i];
    	numbers[i] = numbers[j];
    	numbers[j] = temp;
          }
        }
      }
    	
      display("numbers array after bubble sort:", numbers, N);
    	
      // report total passes
      std::cout << "Total passes = " << total_passes << std::endl;
    	
      return 0;
    }
    Last edited by b49P23TIvg; December 24th, 2016 at 08:31 AM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Aug 2011
    Posts
    5,791
    Rep Power
    508
    Hence,
    Code:
    #include<iostream>
    
    const int N = 10;
    
    void display(const char*title, int*v, const int n) {
      std::cout << title << std::endl;
      for (int i = 0; i < n; i++)
        std::cout << v[i] << " ";
      std::cout << std::endl;
    }
    
    int bubble_sort(int*v, const int n) {
      // rewritten as bubble sort.  bubble sort
      // compares immediate neighbors only.
      // returns the number of comparisons.
      int temp;
      int i, j, comparisons = 0, swaps = 1;
      for (i = n-1; swaps && i; --i, comparisons += j)
        for (swaps = j = 0; j < i; ++j)
          if (v[j+1] < v[j])
    	temp = v[j+1], v[j+1] = v[j], v[j] = temp, ++swaps;
      return comparisons;
    }
    
    int main() {
      int numbers[N] = {3, 4, 1, 7, 1, 8, 101, 89, 10, 47};
      int total_passes;
      display("numbers array before bubble sort:", numbers, N);
      total_passes = bubble_sort(numbers, N);
      display("numbers array after bubble sort:", numbers, N);
      std::cout << "Total comparisons = " << total_passes << std::endl;
      return 0;
    }
    If in doubt, check Sorting algorithms/Bubble sort - Rosetta Code
    [code]Code tags[/code] are essential for python code and Makefiles!
  6. #4
  7. Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Aug 2011
    Posts
    5,791
    Rep Power
    508
    And finally, to answer your question, yes, I have an idea of where you've gone wrong.
    [code]Code tags[/code] are essential for python code and Makefiles!
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    16
    Rep Power
    0
    This is speed comparison of different sorting algorithms, if it helps:
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2012
    Posts
    31
    Rep Power
    6

    Smile


    @b49P23TIvg
    Thanks for all the help. I know bubble sort isn't the optimum sorting algorithm; I was trying to do one of the exercises in "C++: How To Program" at the end of the arrays and vectors chapter. :D Working my way through the book at the moment to learn C++. Also purchased C++ Primer for another viewpoint/to reinforce what I'm learning from the first book.
    I expect I may be on here a bit looking for help every few days(!)

    @ivanvodisek
    Neat gif! Just saved it to my desktop there.

    Miktor
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2017
    Posts
    3
    Rep Power
    0
    Hey try this code:

    Bubble Sort
    Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
    Example:
    First Pass:
    ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
    ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
    ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
    ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
    Second Pass:
    ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
    ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
    ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
    ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
    Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
    Third Pass:
    ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
    ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
    ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
    ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

    Learn C++ here https://hackr.io/tutorials/learn-c-c-plus-plus


    Code:
    // C program for implementation of Bubble sort
    #include <stdio.h>
     
    void swap(int *xp, int *yp)
    {
        int temp = *xp;
        *xp = *yp;
        *yp = temp;
    }
     
    // A function to implement bubble sort
    void bubbleSort(int arr[], int n)
    {
       int i, j;
       for (i = 0; i < n-1; i++)      
     
           // Last i elements are already in place   
           for (j = 0; j < n-i-1; j++) 
               if (arr[j] > arr[j+1])
                  swap(&arr[j], &arr[j+1]);
    }
     
    /* Function to print an array */
    void printArray(int arr[], int size)
    {
        for (int i=0; i < size; i++)
            printf("%d ", arr[i]);
        printf("\n");
    }
     
    // Driver program to test above functions
    int main()
    {
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        int n = sizeof(arr)/sizeof(arr[0]);
        bubbleSort(arr, n);
        printf("Sorted array: \n");
        printArray(arr, n);
        return 0;
    }
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2017
    Location
    bangalore
    Posts
    3
    Rep Power
    0
    there is a simple mistake you have done in your inner for loop everything else is fine dude
    for (int i = 0; i < 10; i++) {
    for (int j = i + 1; j < 10 ; j++)
    ^
    not 10-i
    and the total passes always will n-1
    in your case 10-1=9 passes

    try this
    for (int i = 0; i < 9; i++) {
    for (int j = i + 1; j < 10 ; j++) {

    if (numbers[i] > numbers[j]) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
    }
    }
    total_passes++;
    }

    Comments on this post

    • salim2120 agrees : yes, this answer is working
  16. #9
  17. Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Aug 2011
    Posts
    5,791
    Rep Power
    508
    Bubble-sort with Hungarian ("Csángó") folk dance
    https://www.youtube.com/watch?v=lyZQPjUT5B4
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo