Society of Robots - Robot Forum

Software => Software => Topic started by: TrickyNekro on March 09, 2009, 08:50:53 PM

Title: Sorting Algo check up!
Post by: TrickyNekro on March 09, 2009, 08:50:53 PM
Hello guys,

 I was just sitting at my chair and trying to make a space and time efficient algorithm for
a little something I'm preparing... I was only familiar with the bubble sort but it's too slow and inefficient
so I came up to this as an idea of mixing smart bubble sort and insertion sort...
Please have a look and tell me your thoughts about it!!!


Let's say we have a 50 element array:

Code: [Select]
A[1] <- GetADC

FOR i = 1 TO 49
  temp <- GetADC

  IF temp > A[i] THEN
     A[i+1] <- temp

  ELSE


    j <- i

   WHILE a <- false
      A[j+1] <- A[j]
      j <- j - 1
    
     IF j = 0 THEN
       A[1] <- temp
       a <- true

     ELSE

       IF temp > A[j] THEN
         A[j+1] <- temp
         a <- true

       ENDIF

     ENDIF

   WEND

  ENDIF

NEXT
Title: Re: Sorting Algo check up!
Post by: superchiku on March 10, 2009, 01:15:25 AM
use merge sort or quicksort instead don use bubble sort or inserton sort the have max time complexity of n^2 while quick sort has nlogn

i have sample quick sort programs and merge sort programs in c...hope u know c...
Code: [Select]
# include<stdio.h>
# include<conio.h>

int a[10];
int divideandconquer(int low,int high)
 {
  int i,j,reference;
  i=low-1;
  j=high+1;
  reference=a[low];
  while(i<j)
   {
      do
     {
      i++;
     }while(a[i]<reference);
    do
     {
      j--;
     }while(a[j]>reference);

    if(i<j){
    a[i]=a[i]+a[j];
    a[j]=a[i]-a[j];
    a[i]=a[i]-a[j];
     }
     else
       return(j);
   }


 }
void quicksort(int low,int high)
 {
  int j;
  if(low<high)
   {
  j=divideandconquer(low,high);
  quicksort(low,j);
  quicksort(j+1,high);
   }
 }
 void main()
  {

   int g;
   clrscr();
   printf("\nenter the elements");
   for(g=0;g<=9;g++)
    {
     printf("\n insert the %dth element",g+1);
     scanf("%d",&a[g]);
    }
   quicksort(0,9);
   printf("\n sorted array is ");
   for(g=0;g<=9;g++)
    {
      printf(" %d ",a[g]);
    }
   getch();
  }

merge sort

Code: [Select]
# include<stdio.h>
# include<conio.h>
# include<math.h>
int a[10];
void merge(int,int,int);
void mergesort(int low,int high)
 {
   int mid;
    if(low<high)
      {
mid=(low+high)/2;
         mergesort(low,mid);
mergesort(mid+1,high);
         merge(low,mid,high);
       }
   }

void merge(int low,int mid,int high)
  {
   int *temp,i,j,k;
   i=low;
    j=mid+1;
   temp=(int*)malloc(sizeof(int)*(high-low+1));
   k=0;
   while(i<=mid && j<=high)
     {
if(a[i]<a[j])
   {
    temp[k]=a[i];
    i++;
    k++;
   }
else
    {
     temp[k]=a[j];
     j++;
     k++;
     }
     }
  while(i<=mid)
     {
      temp[k]=a[i];
      i++;
      k++;
      }
   while(j<=high)
      {
       temp[k]=a[j];
j++;
k++;
      }
    k=0;
    for(i=low;i<=high;i++)
       {
a[i]=temp[k];k++;

       }
   }
 void main()
  {
   int g;
   clrscr();
   printf("enter the elements\n");
   for(g=0;g<=9;g++)
    {
     printf("\n enter the %dth element",g+1);
     scanf("%d",&a[g]);
    }
   mergesort(0,9);
   printf("\n the sorted array is");
   for(g=0;g<=9;g++)
     {
      printf(" %d ",a[g]);
      }
  getch();
 }
 

 
Title: Re: Sorting Algo check up!
Post by: TrickyNekro on March 10, 2009, 05:14:18 AM
Thank man, but unfortunately...
It was a little bit hard for me to read...
I made a try to understand merge but it gives me the creeps...
Quick sort is understandable fortunately....

Any other recommendations are more than well come!!!
better in pseudocode...
Title: Re: Sorting Algo check up!
Post by: chelmi on March 10, 2009, 07:41:09 AM
If there in ONE algorithm you shouldn't invent in 2009, it's a sorting algorithm ;)

http://en.wikipedia.org/wiki/Merge_sort (http://en.wikipedia.org/wiki/Merge_sort)

http://en.wikipedia.org/wiki/Quicksort (http://en.wikipedia.org/wiki/Quicksort)