New Sorting Algo Pls Help Me! :(

[SwiftDeath]

I am creating a new sorting algorithm as a machine problem and i encounter difficulties.

The logic of my said the said algorithm is to create an array by inputing the total numbers to be accepted followed by the array variables and sorting it ascending or descending. The array would be sorted on both sides, through insertion sort.

So far, i didn't have any luck with it and my deadline is coming to a close. I really need anyone's help on this one i'm begging you. :(

Here is an example:

Array Total: 6
Ascending: 4 5 9 1 3 2

Compare the 1st and last number in ascending order. Swap if true.
1st Pass: 2 5 9 1 3 4
Increment both sides. this time the numbers to be compared are Group1(2,5) and Group2(3,4). Swap them according to their places.
2nd Pass: 2 3 9 1 4 5
Then the next pass, wherein you do the same procedure as number two. Group1(2,3,9) and Group2(1,4,5) Then swap.
3rd Pass: 2 3 9 1 4 5
The last pass where you arrange the whole array.
Last Pass: 1 2 3 4 5 9

If the amount of numbers to be arrange is odd. Then include the number in the middle to the left group and arrange it before doing the last pass.

Please everyone. Anyone. I really need your help on this.

#include"stdio.h"
#include"stdlib.h"

void read_list(int element[], int total)
{
  int ctr;
  for(ctr=0;ctr<total;ctr++)
  {
    printf("\n Enter Element [%d] ::" ,ctr);
    scanf("%d", &element[ctr]);
  }
}


void print_list(int element[], int total)
{
  int ctr;
  for(ctr=0;ctr<total;ctr++)
  printf("  %d", element[ctr]);
}


void insert_sort(int element[], int total)
{
  int mid, left, right, ctr, ctr2, ctr3, temp;

  mid = total/2;

  for(ctr=total-1; ctr>=mid; ctr--)
  {
    for(ctr2=0; ctr2<mid; ctr2++)
      {
      if (element[ctr2] > element[ctr])
      {
        temp = element[ctr];
        element[ctr] = element[ctr2];
        element[ctr2] = temp;    
      }
       if ((ctr2 < mid) && )(element[ctr2] > element [ctr2+1]))
         {
               temp = element[ctr2+1];
               element[ctr2+1] = element[ctr2];
               element[ctr2] = temp;
         }
       if ((ctr >= mid) && (element[ctr-1] > element[ctr]))
         {
               temp = element[ctr];
               element[ctr] = element[ctr-1];
               element[ctr-1] = temp;
         }
      }
      printf("\n Pass %d :: ", ctr2+1);
      print_list(element,total);
  }
}
void main()
{
  int element[20], total;
  clrscr();

  printf("\n Enter Array Length :: ");
  scanf("%d", &total);
  read_list(element,total);
  printf("\n The Array Elements are as follows :: ");
  print_list(element,total);
  insert_sort(element,total);
  printf("\n Last Pass :: ");
  print_list(element,total);
  getch();
}

I really need you help on this one pls.

[Ancient Dragon]

>>I am creating a new sorting algorithm
Not very likely unles you are doing a Ph.D. thesis. Sort algorithms have been one of the most researched topics in computer science, so designing your own unique algorithm is very unlikely.

[SwiftDeath]

uhmm thanks a lot Ancient Dragon, actually it is my girlfriend's case study. . i dunno why they proposed such, and the dead line is on july 30, 2008. . and i really am having a lot of difficulties. . i really don't know if i can make it though i don't wanna disappoint her. . T_T pls help me. .

[SwiftDeath]

i have re-written the code, it gives the first and last pass correct but it kinda does not in the in-between passes from 1st to last. . T_T i think i'm gonna have migraine. .

#include"stdio.h"
#include"stdlib.h"

void read_list(int element[], int total)
{
  int ctr;
  for(ctr=0;ctr<total;ctr++)
  {
    printf("\n Enter Element [%d] ::" ,ctr);
    scanf("%d", &element[ctr]);
  }
}


void print_list(int element[], int total)
{
  int ctr;
  for(ctr=0;ctr<total;ctr++)
    printf("  %d", element[ctr]);
}


void insert_sort(int element[], int total)
{
  int mid, left, right, ctr, ctr2, ctr3, temp;

  mid = total/2;

  for(ctr=total-1; ctr>=mid; ctr--)
  {
    for(ctr2=0; ctr2<mid; ctr2++)
      {
        if ((ctr >= mid) && (ctr2 < mid))
        {
          if (element[ctr2] > element[ctr])
          {
            temp = element[ctr];
            element[ctr] = element[ctr2];
            element[ctr2] = temp;
          }
        }
      }

    for (left=0; left<mid; left++)
    {
     if (element[ctr2] > element [ctr2+1])
       {
         temp = element[ctr2+1];
         element[ctr2+1] = element[ctr2];
         element[ctr2] = temp;
       }
    }
				
    for (right=total-1; right>=mid; right--)
    {
      if (element[ctr-1] > element[ctr])
      {
        temp = element[ctr];
        element[ctr] = element[ctr-1];
        element[ctr-1] = temp;
      }
    }

  printf("\n Pass %d :: ", ctr);
  print_list(element,total);

  }
}

void main()
{
  int element[20], total;
  clrscr();

  printf("\n Enter Array Length :: ");
  scanf("%d", &total);
  read_list(element,total);
  printf("\n The Array Elements are as follows :: ");
  print_list(element,total);
  insert_sort(element,total);
  printf("\n Last Pass :: ");
  print_list(element,total);
  getch();
}

[Salem]

> actually it is my girlfriend's case study
Get her to do her own homework you sap!

> i really don't know if i can make it though i don't wanna disappoint her.
Or what? She'll leave you?
She'll do that anyway once you've out-lived your usefulness to her.

[SwiftDeath]

uhh. . it's not that but. . i really don't think she can do it, so is there anyone ther whou might be able to help me?

[Adak]

I'll agree with you that you need help - anyone who names their array "element[]", is utterly at their limit! :)

I don't agree with your algorithm, however. It looks like it will fail when you are sorting more numbers which are not favorably arranged already, but I haven't run it yet, either.

I'll take a peek at it later tonight or tomorrow. Absolutely have no expectations about this, however. Sorting has been studied to death, btw. Is there some name for this kind of sort? May have info on the net by the bucket load, if so.

[SwiftDeath]

oohh.. uhmm, actually you're right it does limit the number of variables it can store in the array to 20, her study is theory based and the teacher said that a support program is mandatory so i'm trying the best i can to do so. .

the code sorts the array accurately up to 8 numbers so far, i haven't ttried 10 up.. nd yet i already encounter so many difficulties,

ascending order:
for example: 5 4 6 8 2 1 -- 1st last to be compared, then increment left and decrement right.

1st pass: 1 4 6 8 2 5 -- then compare the underline again and swap

2nd pass: 1 2 6 8 4 5 -- compare the underline again and swap

last pass: 1 2 4 5 6 8 -- final answer.

this is the flow of the algorithms logic. . thanks a lot every one i really appreciate it T_T

[Adak]

I believe I understand what the algo should be. You're using an insertion sort, like the last step in Quicksort, but you're using it over and over, on ever-increasing sizes of two groups.

So the algorithm is:

i = 0;
while(i++ < numbersToBeSorted/2)  {
   increase the numbers by one in both the first and last subsets
   and combine the subsets into one new subset.
   sort the new subset using insertion sort
}

//handle any odd middle number here, again by insertion sort

So you have three functions, one to make the left and right side sets up with the right amount of numbers, the second to combine them into one new subset, and the third to sort the new subset via insertion sort.

You can't just compare the right and left subsets, as I understand your description. As the amount of numbers to be sorted increases, it will not work.

[SwiftDeath]

omg! T_T by brain is already at its max. . how am i suppose to do that? i mean. . where is the best way to start doing so? god, i didn't think of that earlier thanks! you're really good at c, ^_^

[SwiftDeath]

i was able to rewrite the code and so far it displays the correct 1st and last pass.. although the in-between, pls help me. .

@Adek, i don't know how to start creating another function like what you said, just that i think i'm already overloading. .

@_@ >.<

#include"stdio.h"
#include"stdlib.h"

void read_list(int element[], int total)
{
  int ctr;
  for(ctr=0;ctr<total;ctr++)
  {
    printf("\n Enter Element [%d] ::" ,ctr);
    scanf("%d", &element[ctr]);
  }
}


void print_list(int element[], int total)
{
  int ctr;
  for(ctr=0;ctr<total;ctr++)
    printf("  %d", element[ctr]);
}


void insert_sort(int element[], int total)
{
  int mid, left, right, ctr, ctr2, ctr3, temp;

  mid = total/2;

		for(ctr=total-1; ctr>mid; ctr--)
		{
			for(ctr2=0; ctr2<mid; ctr2++)
				{
					if (element[ctr2] > element[ctr] && ctr2 == 0)
					{
						temp = element[ctr];
						element[ctr] = element[ctr2];
						element[ctr2] = temp;

						printf("\n Pass %d :: ", ctr2);
						print_list(element,total);

					}
					else if (element[ctr2] > element[ctr] && ctr2 !=0 )
					{
						temp = element[ctr];
						element[ctr] = element[ctr2];
						element[ctr2] = temp;
					}
				}

		printf("\n Pass %d :: ", ctr);
		print_list(element,total);


			for (left=0; left<mid; left++)
			{
			 if (element > element[left+1])
				 {
					 temp = element[left+1];
					 element[left+1] = element;
					 element = temp;
				 }
			}

			for (right=total-1; right>=mid; right--)
			{
				if (element[ctr-1] > element[ctr])
				{
					temp = element[ctr];
					element[ctr] = element[ctr-1];
					element[ctr-1] = temp;
				}
			}
/*
		printf("\n Pass %d :: ", ctr);
		print_list(element,total);
*/
		}
}

void main()
{
  int element[20], total;
  clrscr();

  printf("\n Enter Array Length :: ");
  scanf("%d", &total);
  read_list(element,total);
  printf("\n The Array Elements are as follows :: ");
  print_list(element,total);
  insert_sort(element,total);
	printf("\n\n Final Answer :: ");
  print_list(element,total);
  getch();
}

[Adak]

I believe I understand what the algo should be. You're using an insertion sort, like the last step in Quicksort, but you're using it over and over, on ever-increasing sizes of two groups.

So the algorithm is:

i = 0;
while(i++ < numbersToBeSorted/2)  {
   increase the numbers by one in both the first and last subsets
   and combine the subsets into one new subset.
   sort the new subset using insertion sort
}

//handle any odd middle number here, again by insertion sort

So you have three functions, one to make the left and right side sets up with the right amount of numbers, the second to combine them into one new subset, and the third to sort the new subset via insertion sort.

Here's a standard function for an insertion sort:
 void insertSort(int a[], size_t length) {
     int i, j, value;
 
     for(i = 1; i < length; i++) {
         value = a[i];
         for (j = i - 1; j >= 0 && a[j] > value; j--) {
             a[j + 1] = a[j];
         }
         a[j+1] = value;
     }
 }

//So let's use that for the sorting. Do not alter it, btw. Nothing breaks a 
//sorting routine faster than tinkering with it. :)

//One function down, two to go.

//print the a[] array, as it is, now

left[numbersToBeSorted/2 + 1] = {0};   //holds left side of our numbers array + 1
right[numbersToBeSorted/2] = {0};      //  "     right  "    "   "         "         "
i = 0;
while(i++ < numbersToBeSorted/2)  {

   //increase the numbers by one in both the first and last subsets
   left[i] = a[i]; 
   right[i] = a[numbersToBeSorted - i]; 

   //sort both the left, and the right subsets
   insertSort(int left[], int i);    //i may need to be replaced
   insertSort(int right[], int numbersToBeSorted);
}
//it will be more efficient to finish the left and right subsets completely 
//first, and then merge them back together, just one time.

//Middle numbers can be handled most effiiciently, by just leaving them 
//in the original array, since all of the numbers will have to be resorted
// at the end, anyway. This shows that this algo is inefficient :)

//if we must move the middle number, something like this could be worked up.
//This is unfinished
if(numbersToBeSorted %2 == 1)   //it was an odd number of numbers
   //add in the final middle number, now
   left[i] = a[i];

   //and combine the subsets into one array.
   //handles even number of numbers in the left and right arrays
   for(i = 0; i < numbersToBeSorted/2; i++)   {
      a[i] = left[i];

   for(i = numbersToBeSorted/2; i < numbersToBeSorted; i++)   
      a[i] = right[i];
   //sort the  using insertion sort
   insertSort(int a[], int numbersToBeSorted);

}

Since each function except insertionSort is so small, it makes sense to just block the code into the while loop.

All the above is just an outline, and is entirely untested. Why don't you remove your code to handle the number handling and sorting, and put this code in it's place? No it won't work as is, but tinker with it, (but not with the sorting function), and see what your muse might inspire you with. :)

I'll check back tomorrow and see what you have and do a little more tinkering to it, myself.

[SwiftDeath]

wow you're really awesome! ooh, the last or final pass wouldn't actually sort the whole set of array rather compare both subsets and swap if they fulfilled the condition. .

[Adak]

wow you're really awesome! ooh, the last or final pass wouldn't actually sort the whole set of array rather compare both subsets and swap if they fulfilled the condition. .

OK, I see what you're talking about. That would not work, I believe. That relies on the numbers having a favorable distribution, to work. Making the final pass a merge pass, would work, though The left subset is sorted, the right subset is sorted, so a merge pass would just be very efficient and logical, at this point. And it would work with any distribution of numbers.

Go to Wikipedia (or anywhere), and read up on merge sorting. That would be the ideal last pass, here.

Let me know.

[SwiftDeath]

i can't make it run T_T declaration syntax error, omg i haven't slept for 24 hours. .

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


void read_list(int a[],int n)
{
 int i;
 for(i=0;i<n;i++)
  {
   printf("\n\n\t ENTER THE ELEMENT [%d] :: ",i);
   scanf("%d",&a[i]);
  }
}

void print_list(int a[],int n)
{
 int i;
 for(i=0;i<n;i++)
  printf("\t%d",a[i]);
}

void accept(int a[], int n)
{
	int i, mid, left[10], right[10];

	mid = n/2;
	left[n/2+1] = {};
	right[n/2] = {};

	i = 0;
	while(i++ < mid)
	{
		left[i] = a[i];
		right[i] = a[mid - 1];

		insert_sort(int left[], int n);
		insert_sort(int right[], int n);
	}
}

void insert_sort(int a[],int n)
{
 int i,j,temp;
 for(i=1;i<n;i++)
  {
   temp=a[i];
   for(j=i-1;j>=0 && a[j]>temp;j--)
	  a[j+1]=a[j];
   a[j+1]=temp;
  printf("\n\n\t PASS %d :: ",i);
  print_list(a,n);
  }
}

void main()
{
 int a[20],n;
 textcolor(10);
 clrscr();
 printf("\n\n\t ENTER THE ARRAY LENGTH :: ");
 scanf("%d",&n);
 read_list(a,n);
 printf("\n\n\t THE ARRAY ELEMENTS ARE AS FOLLOWS :: ");
 print_list(a,n);
 insert_sort(a,n);
 printf("\n\n\t THE SORTED LIST IS :: ");
 print_list(a,n);
 getch();
}

[Adak]

I'll look at it later tonight. I'm not surprised because it's really an odd algo, and we're having to wing it a bit, as we go.

You get some sleep.

[SwiftDeath]

so far, it performs the 1st pass correctly and produces the desired output for ascending order, although what it does was a wee bit different, the right and left subsets sorts the numbers within them and won't swap it.. >.< i don't know what to do, hmm.. maybe you're right, but i got to get to school first T_T maybe i'd sleep when i get home after class

[Adak]

so far, it performs the 1st pass correctly and produces the desired output for ascending order, although what it does was a wee bit different, the right and left subsets sorts the numbers within them and won't swap it.. >.< i don't know what to do, hmm.. maybe you're right, but i got to get to school first T_T maybe i'd sleep when i get home after class

I think I see where you're coming from with this algo. This is why it violates a long held, near and dear tenant of algorithms.

You have a big problem - in this case sorting, now let's see how one of the best (and one of the fastest) sorting algo's handles this problem.

Take 20 numbers, pick a mid point. Move all the numbers greater than this midpoint into a new left group. Take all the numbers that are greater than the midpoint, and put them in a new right sub group.

Now in one of these sub groups, pick a new midpoint - and again, move all the numbers less than the midpoint to a new left side subgroup, and all the numbers greater than the midpoint to the new right side subgroup.

Continue like this until you have just 2 numbers left in the subgroup. Compare them and swap as needed.

(it now returns to all the other (larger) sub groups and repeats the above).

The point is Quicksort has taken a large problem, and broken it down into smaller and smaller partial problems, which can easily be solved. The once giant sorting problem has been decomposed into something easy to manage and easy to prove it's correct, because it's always *clear* what should be happening during the sort.

We don't *want* to compare the 3rd number in the left subgroup, with the 3rd number of the right subgroup, even if it would work - which it won't, but if you tweak it enough, you might get something to work - maybe.

Fine for 6 numbers, maybe even 20, but I *dare* you to make it work for 245,000 numbers! Your sanity will be long gone, my friend, fried by the complexities of this. :)

Never mind the first pass - we don't give a rat's patooey about the first pass. We need a sorting algo that will work for 2, as well as 2 million - and everything in between.

TTYL

[SwiftDeath]

yeah, you're right about that, unfortunately i don't think that i am able to do this alone, i mean i'm already feeling the pressure and it pains me to know that i can't even get near to the goal. . all that keeps me up is there are people like you still willing to help, thanks a lot and i'll try to rearrange the codes if need be. .

[SwiftDeath]

bump! pls help me.. T_T

[Adak]

I'm working on a version of this. It won't be exactly like your version above, but it will help you along and give you some idea's, I'm sure.

Because of the holiday, it won't be posted until Sunday, some time.

[SwiftDeath]

oh thanks a lot on that, i'm trying to make it accept letters and convert it to ascii to be arranged T_T thanks a lot.. maybe if you'd someday be here in the philippines i'd treat you ^_^

[Adak]

oh thanks a lot on that, i'm trying to make it accept letters and convert it to ascii to be arranged T_T thanks a lot.. maybe if you'd someday be here in the philippines i'd treat you ^_^

Letters are just small 8 bit numbers, and they are already ascii in value, (on most PC's at least).

This is a program that shows the idea's I was thinking of. You'll need to modify it to suit your own purposes, AND you'll need to test it thoroughly. I've only tested about 15 different number combinations, in quantity from 2 through 11.

The rest as they say, is left as an exercise for the student. :)

//Adak's help for SwiftDeath 

#include <stdio.h>
#include <values.h>
#define Size 11

void insertSort(int a[], size_t length)  {
   int i, j, value;
 
   for(i = 1; i < length; i++)  {
      value = a[i];
      for (j = i - 1; j >= 0 && a[j] > value; j--)  {
         a[j + 1] = a[j];
      }
      a[j+1] = value;
   }
}
int main(void)  {
   int i, j, k, mid;
   int a[Size] = {0,1,9,3,5,2,0,8,4,6,7};  //9,3,2,0,8,4,6,7};
   int left[Size/2]= {0}, right[Size/2] = {0};
   
   mid = MAXINT;

//   insertSort(a, sizeof(a)/sizeof(*a));

   putchar('\n');
   for(i = 0; i < sizeof(a)/sizeof(*a); i++)  //same as i < Size
      printf(" %4d", a[i]);
   getchar();

   i = 0;
   while(i < Size/2)  {

      //increase the numbers by one in both the first and last subsets
      left[i] = a[i]; 
      right[i] = a[Size - Size/2 + i]; 

      //sort both the left, and the right subsets
      insertSort(left, i + 1);    
      insertSort(right, i + 1);
      ++i;
   }
   
   if(Size % 2 == 1)   //it was an odd number of numbers
      mid = a[i];

   //and merge the sorted subsets into one array.
   i = 0; j = 0; k = 0;
   while(i < Size/2 && j < Size/2)   {
      while(left[i] <= right[j] && i < Size/2)  {
         if(mid <= left[i])  {
            a[k++] = mid;
            mid = MAXINT;   //defined in values.h 
         }
         else  {
            a[k] = left[i++];
            k++;
         }
      }
      while(right[j] < left[i]  && j < Size/2)  {
         if(mid <= right[j])  {
            a[k++] = mid;
            mid = MAXINT;   //defined in values.h 
         }
         else  {
            a[k] = right[j++];
            k++;
         }
      }
   }
   //handles the ends of left and right sub arrays, and mid's if mid is
   //not the largest number of the a[] array
   while(i < Size/2)  {
      if(mid < left[i])
         a[k++] = mid;
      else
         a[k++] = left[i++];
   }
   while(j < Size/2)  {
      if(mid < right[j])
         a[k++] = mid;
      else
         a[k++] = right[j++];
   }
   //if mid < MAXINT here, then it's the highest number of a[], so append it
   if(mid < MAXINT)
      a[Size - 1] = mid;

   putchar('\n');
   for(i = 0; i < sizeof(a)/sizeof(*a); i++)
      printf(" %4d", a[i]);

   getchar();
   return 0;
}

Good luck!

[SwiftDeath]

i got lost in your codes >.< i mean im really not that good, i'll study it! is there by any chance i might be able to convert chars to ascii? aside from the implicit conversion provided by c. . %c --> %d?? i'm making the program be able to accept chars as well. .

[Adak]

i got lost in your codes >.< i mean im really not that good, i'll study it! is there by any chance i might be able to convert chars to ascii? aside from the implicit conversion provided by c. . %c --> %d?? i'm making the program be able to accept chars as well. .

Sorting is not a terribly easy subject to tackle. Needless to say, I didn't just "whip" up this code in a few minutes. :)

If you want the sorting program to handle char's, instead of int's, then just make the arrays into arrays of char's, and change mid (where it's assigned the value of MAXINT), to mid being assigned the value of MAXCHAR, instead. Mid needs to be changed to type char; that's all I can think of that needs to be changed, right now.

If your compiler doesn't have a MAXCHAR value, you may need to set it as a define MAXCHAR 512 (or 256 if you use unsigned char's).

Naturally, you need to change the printf type to %c instead of %d, so printf can give you what you want.

I am now working on a large programming project, and don't have the time to re-do the program. I did give it a bit more testing today with 20 & 21 numbers, and it worked great.
You should test it much more before relying on it, however.

If you have other problems, just post them up with a new thread, and post up either the whole program, or the part of the program that shows the error.

[SwiftDeath]

thank you so much ^_^ thanks a lot this will be a great help for me ^_^