Author Topic: Sorting Algo check up!  (Read 1095 times)

0 Members and 1 Guest are viewing this topic.

Offline TrickyNekroTopic starter

  • Contest Winner
  • Supreme Robot
  • ****
  • Posts: 1,207
  • Helpful? 15
  • 1.6L Peugeot 307 tuner
Sorting Algo check up!
« 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
For whom the interrupts toll...


P.S. I've been inactive for almost a year... Don't give promises but I'll try to complete my tutorials. I'll let you know when..

Cheers!

Offline superchiku

  • Supreme Robot
  • *****
  • Posts: 953
  • Helpful? 5
  • cooll
Re: Sorting Algo check up!
« Reply #1 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();
 }
 

 
JAYDEEP ...

IT AND ROBOTICS ENGINEER

"IN THE END IT DOESNT EVEN MATTER"

Offline TrickyNekroTopic starter

  • Contest Winner
  • Supreme Robot
  • ****
  • Posts: 1,207
  • Helpful? 15
  • 1.6L Peugeot 307 tuner
Re: Sorting Algo check up!
« Reply #2 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...
For whom the interrupts toll...


P.S. I've been inactive for almost a year... Don't give promises but I'll try to complete my tutorials. I'll let you know when..

Cheers!

Offline chelmi

  • Supreme Robot
  • *****
  • Posts: 496
  • Helpful? 15
Re: Sorting Algo check up!
« Reply #3 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/Quicksort


 


Get Your Ad Here

data_list