Search code examples
csortingbubble-sort

Bubble sorting not working for large file, but it works for small file


I having issue with bubble sorting large data. This is an assignment, and my teacher explicitly said to use bubble sort to sort this large data. I tried running in a small file and it works perfectly, but it's having trouble outputting anything for big file. I don't know what's the problem. I have to use bubble sort too. Thank you. The small file "small.txt"is provided below. The big file "big.txt" does fit in here, it contains thousands of lines but the same format as the small file, and my program is provided below: I waited for 1 hour for anything to output, and the program is still in progress for the big file.

small.txt

FORD    2001
NISSAN  2000
JAYCO   2003

Program

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
    FILE *read;
    char lines[110000];
    int i=0, c, j,a;
    char *make[111100];
    char *year[111100], *swapyear, *swapmake; 

    if( (read = fopen("big.txt", "r")) == NULL) 
    {
       printf("can't open %s\n", "big.txt");
       exit(1);
    }

    c=0;
    while(fgets(lines, sizeof(lines), read)!=NULL){
       make[c] = strdup(strtok(lines, " "));
       year[c] = strdup(strtok(NULL, " "));
       c++;
    }


    for(j=0; j<c-1; j++){
        for(a=0; a<(c-j-1); a++){
            if(atoi(year[a]) > atoi(year[a+1])){
                swapyear = year[a];
                swapmake = make[a];
                year[a] =year[a+1];
                make[a] = make[a+1];
                year[a+1] = swapyear;
                make[a+1] = swapmake;
            }
        }
    }  

  for(j=0; j<=(c-1); j++)
    {
        printf("%s %s\n", make[j], year[j]);
    }    


 }

Solution

  • This is the bubble sort algorithm. 
    Note that it extends all the way through the data on each pass
    (unlike the OPs code)
    

    Step 1: Repeat Steps 2 and 3 for i=1 to number of entries to sort

    Step 2: Set j=1

    Step 3: Repeat while j<=n

         (A) if  a[i] < a[j]
    
             Then interchange a[i] and a[j]
    
             [End of if]
    
         (B) Set j = j+1
        [End of Inner Loop]
    
    [End of Step 1 Outer Loop]
    

    Step 4: Exit

    and here is a code implementation:

    for(i=0 ; i<n ; i++)
    {
        for(j=0 ; j<n-i-1 ; j++)
        {
            if(arr[j]>arr[j+1]) //Swapping Condition is Checked
            {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    

    The above uses a temp variable, usually a bad idea. Here is an example of using the XOR operator (and no temp variable)

    x = x ^ y  (1)
    y = y ^ x  (2)
    x = x ^ y  (3)