CODEWITHSUNDEEP
csortingbubble-sort
Hayra
Hayra

Reputation: 466

Obtain two cluster via bubble sort mechanism

I am trying to obtain two cluster from the strings via bubble sort algorithm. Main logic is putting the character strings to left side and the numbers to right side, and the positions can not be changed according to the right to left reading, also i need to use bubble sort for this implementation(!)

For example;

If the string is '503692EC12FATMA' i need to put it FIRSTLY as 'ECFATMA50369212' but the thing i didn't get it how i can use bubble sort to implement this mechanism besides a single if statement ?

I tried somethings but i always sort the character array via bubble sort i can not store the old positions, i need to use just one array and it needs to be implementation of C.

My code example : 

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
  char st[25],temp;
  int l,i,j;
 // clrscr();

  printf("enter Any Sting\n");
  gets(st);
  l=strlen(st);
  /*Logic Bubble Sort  */
  for(i=1;i<l;i++)
     for(j=0;j<l-i;j++)
    if(st[j]>st[j+1])
    {
       temp=st[j];
       st[j]=st[j+1];
       st[j+1] =temp;
    }
  printf("sorted string  \n");
  printf("%s",st);
  getch();
}

But this gives me : '01223569AACEFMT' (!)

After i made the string 'ECFATMA50369212', i will use this string to arrange a cluster left to right A < B and 0 < 1.

to : 'AACEFMT01223569'

Like two functions, first function, use bubble sort to divide numbers and characters, then use this functions returned array to compare it right to left for sorting to create sorted character array.

Any help would be appreciated.

Upvotes: 1

Views: 127

Answers (4)

syntagma
syntagma

Reputation: 24344

I think that the problem with your code is that you are bubble-sorting the array according to the ASCII values of the characters, in which upper-case letters (as well as lower-case letters) appear after number characters.

What you could do to make you program work is define you own comparison function, in which you would treat number characters (48 <= ASCII code <= 57) and upper-case letter characters (65 <= ASCII code <= 90) differently.

Upvotes: 2

WhozCraig
WhozCraig

Reputation: 66244

To do this in a single pass requires a differentiation of digits and non-digits. Once you have that, the algorithm can be summed up as:

  • Always swap if you have digit in the first slot and a non-digit in the second.
  • Else, only swap if their both digits or both non-digits and then, only if they're out of order (the higher slot is "less than" the lower slot).

Following that, you can do this in a single bubble-run. Its all about proper comparison:

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

int main()
{
    char st[25] = "503692EC12FATMA", temp;
    size_t len, i;
    int swapped = 1;

    puts(st);
    len = strlen(st);

    while (swapped && len--)
    {
        swapped = 0;
        for (i=0; i<len; ++i)
        {
            int swap = !isdigit((unsigned char)st[i+1]);
            if (isdigit((unsigned char)st[i]))
                swap = swap || (st[i+1] < st[i]);
            else
                swap = swap && (st[i+1] < st[i]);

            if (swap)
            {
                temp = st[i];
                st[i] = st[i+1];
                st[i+1] = temp;
                swapped = 1;
            }
        }
    }

    puts(st);
}

Output

503692EC12FATMA
AACEFMT01223569

There are other ways to do this obviously. You can even combine all that madness into a single if expression if you're a masochist, (i didn't for clarity). But to accomplish both clustering and cluster-sorting, this is one way to achieve it.

Upvotes: 1

Iłya Bursov
Iłya Bursov

Reputation: 24209

I suppose it is your homework and you actually need some kind of buble-type sort to do clustering first, without actually sorting, here is sample version which "bubbles" letter to the beginning of the string, preserving their relative positions:

l = strlen(st);
for (i = 1; i < l; i++)
    if (isAlpha(st[i])) // bubble this letter to the beginning of the string
        for (j = (i - 1); (j >= 0) && !isAlpha(st[j]); j--)
            swap(&st[j + 1], &st[j]);

printf("sorted string\n%s\n", st);

NOTE: you need following 2 functions before your main:

char isAlpha(char a) {
    return (a >= 'A') && (a <= 'Z');
}

void swap(char* a, char *b) {
    char t = *a; *a = *b; *b = t;
}

Upvotes: 1

anakin
anakin

Reputation: 599

This is not a bubble sort algorithm. What you're trying to do is just a string manipulation that can be done like that:

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
  char st[25],temp;
  int l,i,j;
 // clrscr();

  printf("enter Any Sting\n");
  gets(st);
  int i;
  char sorted_st[25];
  int str_index = 0;
  for (i = 0; i < strlen(l); ++i) {
    if((l[i] >= 'a' && l[i] <= 'z') ||
       (l[i] >= 'A' && l[i] <= 'Z')) {
      sorted_st[str_index++] = l[i];
    }
  }
  for (i = 0; i < strlen(l); ++i) {
    if(l[i] >= '0' && l[i] <= '9') {
      sorted_st[str_index++] = l[i];
    }
  }
  // add the terminating zero
  sorted_st[str_index++] = '\0';
  printf("sorted string  \n");
  printf("%s",st);
  getch();
}

ADVICE: It's better your main function to return int. On successful execution should return '0', in other cases error code.

int main() {
  /* code */
  return 0;
}

Upvotes: 0

Related Questions