Bubble Sort Algorithm in C

问题:

The program I"m trying to finish is a program using the bubble sort algorithm. I am not sure what is the problem or in which function the problem is in. The problem is the program does not sort the array in properly. (It also must be arranged in ascending order).

Here is the code:

#include <stdio.h>
#include "simpio.h"

void getArray (int arr[], int size);
void sortArray (int arr[], int size);
void swap (int arr[], int num, int number);
void dispArray (int arr[], int size);
bool checkBigger (int arr[], int num, int number);

main()
{
          int size;

          printf("Enter number of elements: ");
          size=GetInteger();

          int arr[size];
          getArray(arr, size);
          sortArray(arr, size);
          dispArray(arr, size);

          getchar();
}

void getArray (int arr[], int size)
{
          int num;    

          printf("Please enter the value of the elements: \n");
          for(num=0; num<size; num++)
          {
                     arr[num]=GetInteger();           
          }    
}

void sortArray (int arr[], int size)
{
          int num, number, d;

          for(num=0;num<size-1;num++)
          {
              for(d=0; d<size-num-1; d++)
              {
                     number=num+1;                
                     checkBigger(arr, num, number);              
              }
          }
}

void swap (int arr[], int num, int number)
{
          int tem;

          tem=arr[num];
          arr[num]=arr[number];
          arr[number]=tem;
}

void dispArray (int arr[], int size)
{
          int num;

          printf("The sorted list is:\n");
          for(num=0; num<size; num++)
          {
                      printf("%d\t", arr[num]);         
          }     
}

bool checkBigger (int arr[], int num, int number)
{     
          if(arr[num]>arr[number])
          {
                      swap(arr, num, number);                     
          }     
}

Thank you very much.

回答1:

void sortArray (int arr[], int size)
{
    int num, number, d;

    for(num=0;num<size-1;num++)
    {
        for(d=0; d<size-num-1; d++)
        {
            number=d+1;
            checkBigger(arr, d, number);
        }
    }
}

回答2:

pretty sure your problem is with you algorithm, try to simulate your algorithm in pen and paper. it will help your understanding of your code and the algorithm better :)

for your convenience here i am including a bubble sort algorithm i did some while ago

void bubbleSort( int a[], int n)
{
    int i,j,temp; // for a={1,2,3,4,5} n is 5

    n = n - 1;    // bcz otherwise it will get out of index

    for(i=0; i<n; i++)
    {
        for(j=0; j<n-i; j++)
        {
            if(a[j]>a[j+1])
            {
                temp = a[j+1];
                a[j+1] = a[j];
               a[j] = temp;
            }

        }

    }

}

i hope this helps

回答3:

All I follow from the above examples is an implementation of the exchange sort.

The exchange sort on the outer loop checks each entry in the table against the first element, exchanging when necessary. At then end of the inner loop, the lowest element is in position 1, then it begins with position 2, comparing it to the remaining elements, and doing an exchange. Even if the array was already in order, the sort cannot stop. It has to do a n*(n-1) compares. An array of 50 elements, already sorted will do 50*49 comparisons.

The bubble sort works differently

set a swap flag to zero. Then slide along the array, comparing position(i) to position(i+1). If a swap takes place, you do the sort again.

here is some pseudo code.

1. swap = 0
2. do {
3. for (i=o;i< no-elements-1;i++) {
4. if (array[i] > array[i+1])
5. {
6. do the exchange
7. set swap=1
8. }
9. /**/
10. } while (swap == 1);

The above illustrates the bubble sort.

Note. if the data is in order, there is no swap and there is no second loop. The sort algorithm is able to quit early.

if a fifty element array is in order, the sort would have done 50 comparisons and would have stopped. The exchange sort, which is described earlier would have to do 50*49 or 2450 comparisons.

回答4:

//   BUBBLE SORT.
#include <stdio.h>
#define MAX 20
int main()
{
    int arr[MAX];int no;

    printf("PLEASE ENTER THE CURRENT SIZE OF THE ARRAY\n"); 
    scanf("%d",&no);

    int i;
    printf("PLEASE ENTER THE ELEMENTS OF THE ARRAY\n");
    for(i=0;i<no;i++)
        scanf("%d",&arr[i]);  /*reading the elements*/

    /* sorting begins*/
    int j,k,l;
    int temp;
    int flag=0;

    for(k=0;k<no-1;k++)
        {
        flag=0;
        j=k;
        for(i=0;i<no-j-1;i++)  /* not going to the part that has been sorted*/
        {
            if(arr[i]>arr[i+1])
            {
                flag=1;
                temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
            else 
                continue;/* not necessary*/
        }
        if(flag==0)  /*implies that the array is alraedy sorted*/
            break;
    }
    printf("THE SORTED LIST:\n\n");
    for(i=0;i<no;i++)
        printf("%d\n",arr[i]);
}