Integrated sort with existing code

[yqoET05o]

Hey, so I had this bubble sort method which I have tested and works, but I have to integrate it with another class. I don't understand why it's not actually sorting, would anyone see the issue?

[lastchance]

Don't you mean
>
rather than
<
on line 37?

[ne555]

> so I had this bubble sort method
insertion sort

[lastchance]

Is it just me who can't compile this?

[tpb]

You need a cast to (int*) for the malloc to make it C++-compatible.

[lastchance]

Ah, thanks @tpb. I only ever learnt c++-style memory allocation.

[tpb]

@lastchance, Wow, you're lucky!

OP, your sort works. Not only do you need to toggle the condition in your test loop, as lastchance said, but you also need to only loop up to (but not including) size - 1 so that the index + 1 is not out of bounds, which would most likely mean you'd be comparing the last actual value to some arbitrary value just past the end.

[yqoET05o]

Hey everyone, so I took this bubble sort method from the textbook, not my code or online, from a textbook and I have to integrate with the code here. It's C I should of said well, I just thought someone here might be able to help.

[lastchance]

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

int main(int argc, char *argv[]) 
{
//      printf("METHOD SORTING\n");
//      if (argc != 2) {
//              printf("%s <student-id>\n", argv[0]);
//              exit(0);
//      }
//      int seed = atoi(argv[1]);
        int seed = 4;                    // Just for now!!

        int i;
        int size = 10;                   // Come on, can't debug when it's large

        srand(seed % 4);                 // No idea
        
        int *int_array = (int*)malloc(sizeof(int)*size);  // Credit ... @tpb


        printf( "Original:\n" );
        for (i = 0; i < size; i++)
        {
            int_array[i] = rand() % 100;       // Keep it small
            printf( "%d\n", int_array[i] );    // Gotta check it!
        }

        // This is the method which has to be integrated
        int j;
        for ( i = 0; i < size; i++ )
        {
           for ( j = 0; j < size - 1 - i; j++ )          //
           {                                             // Sorry, had to fix bubble sort
              if ( int_array[j] > int_array[j + 1] )     //
              {                                          //
                  int temp = int_array[j];               //
                  int_array[j] = int_array[j + 1];       //
                  int_array[j + 1] = temp;               //
              }                                          //
           }
        }

        printf( "After this masterpiece:\n" );
        for (i = 0; i < size; i++)
        {
            printf( "%d\n", int_array[i] );              // Fingers crossed ...
        }

        int failed = 0;
        for (i = 0; i < size; i++)
        {
                if (int_array[i] > int_array[i+1])       //    >   not  <
                {
                        failed = 1;
                        break;
                }
        }
        
        printf("------------------\n");
        printf("------------------\n");
        if (failed == 1)
        {
                printf("FAILED SORTING\n");
        } else {
                printf("SUCCESSFUL SORTING\n");
        }
        printf("------------------\n");
        printf("------------------\n");

        free(int_array);

        return 0;
}

[yqoET05o]

Thank you to everyone that helped, but just wondering, is that bubble sort I had a bubble sort? I used the text book example for the c one so just wondering is it wrong?

[lastchance]

BastionCamper wrote:

is that bubble sort I had a bubble sort?

You've just deleted it while I was trying to work that out!

It definitely worked, just wasn't the form of bubble sort that I was used to.

[yqoET05o]

Sorry about that, here it is the one.

int j;
	for (i = 0; i < size; i+= 1) {
		for (j = i - 1; j >= 0 && int_array[j] < int_array[j + 1]; j--) {
			int temp = int_array[j];
                        int_array[j] = int_array[j + 1];
        	        int_array[j + 1] = temp;
		}
	}

[lastchance]

To be honest, I really can't identify it! Seems like (a very inefficient) form of insertion sort, but I'm not quite sure.

[ne555]

¿why inefficient?
the sorted portion is from 0 to i-1, at each step we insert element array[i]
in the insertion the element is array[j+1], we traverse the array (from i-1 to 0) pushing it down (swaps) until it is in its position (it is not greater than the one to its left, in this case it is descending order)

if the array were sorted the inner loop will break on the first iteration, so only O(n) operations would be done

[lastchance]

"Inefficient" insertion sort because each element does a full swap with each lower element on the way down. Where I've seen it before, the temp variable would only be stored for the element moving down, the ones larger than it would all be shuffled up (no swapping) and the moving element (stored in temp) inserted into the sorted place below.

        int j;
        for ( i = 1; i < size; i++ )                                     // int_array[i] is to be moved into sorted part 0, 1, ... , i - 1
        {
           int temp = int_array[i];
           for ( j = i; j > 0 && int_array[j-1] > temp; j-- ) ;          // aim to put it in the jth place
           for ( int k = i; k > j; k-- ) int_array[k] = int_array[k-1];  // shuffle the rest up (assignment, not swapping)
           if ( i != j ) int_array[j] = temp;                            // put in jth place
        }

However, the number of comparisons is the same, so, I guess "very inefficient" was not appropriate here. It just felt like a hybrid of insertion sort and bubble sort with so much swapping.

[MikeyBoy]

Please DON'T go back and remove your code from your original question. It makes the thread incomprehensible to anyone trying to read it.