You are here:

C++/Sorting algorithm

Advertisement


Question
Hello!  I need help in this program.  My friend gave it to me about a program on selection sort.  How would I change the program from that sort into a cocktail shaker sort?  Here's my program:

#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#include <iostream.h>

#define NUM_ELEMENTS 250

#define CLIP_ON 1

typedef  int   array [NUM_ELEMENTS];


void draw_arrow(int x, int y);
void selection();
void start_time();
void end_time();

struct dostime_t t,reset;

array a,b,c;
int col,pass,i,hold,j,k,begin,end;
unsigned size;
void *buf;

int main(void)
{
  /* request autodetection */
  int gdriver = DETECT, gmode, errorcode;

  /* initialize graphics and local variables */
  initgraph(&gdriver, &gmode, "");

  errorcode = graphresult();
  if (errorcode != grOk)  /* an error occurred */
  {
     printf("Graphics error: %s\n", grapherrormsg(errorcode));
     printf("Press any key to halt:");
     getch();
     exit(1); /* terminate with an error code */
  }

randomize();
int ctr,ctr2;
ctr2=250;
for (ctr = 0; ctr < NUM_ELEMENTS ; ctr++){
 a[ctr] = ctr2;
 --ctr2;
}
setviewport(200,55,600,345,CLIP_ON);

col = 0;
for (ctr = 0; ctr <NUM_ELEMENTS; ctr++)
{
bar(col,a[ctr],col,a[ctr]);
col++;
}

 start_time();

 for (pass = 1; pass <=NUM_ELEMENTS -1 ;pass++)
  for (col = 0 ; col <=NUM_ELEMENTS -2 ; col++)
      if ( a[col] > a[col+1] ) {
      j=col+1;
      k=col+2;
      hold = a[col];

      //get the first image
      size = imagesize(col,a[col],col,a[col]);
      buf = malloc(size);
      getimage(col,a[col],col,a[col],buf);
      // erase the first image
  putimage(col,a[col],buf,XOR_PUT);
      // move the first image
      for (int ctr = col;ctr<= col+1 ; ctr++)
      { putimage(ctr,a[col],buf,XOR_PUT);
   putimage(ctr,a[col],buf,XOR_PUT);
      }

   putimage(ctr,a[col],buf,XOR_PUT);
   a[col] = a[col + 1];
      //get the second image
      size = imagesize(k,a[k],k,a[k]);
      buf = malloc(size);
      getimage(k,a[k],k,a[k],buf);
      // erase the second image
  putimage(k,a[k],buf,XOR_PUT);
      // move the second image
      for ( ctr = k;ctr>= j ; ctr--)
      { putimage(ctr,a[k],buf,XOR_PUT);
   putimage(ctr,a[k],buf,XOR_PUT);
      }

   putimage(ctr,a[k],buf,XOR_PUT);

   a[col]=a[col+1];
   a[col+1]=hold;
}
end_time();
  delay (5000);
  closegraph();
  cout << end << "seconds ";
  getch();
  return 0;
}

void start_time()
{
reset.hour    = 1;
reset.minute  = 0;
reset.second  = 0;
begin = reset.second;
reset.hsecond = 0;
_dos_settime(&reset);
}

void end_time()
{
 _dos_gettime(&t);
 end = t.second - begin;
}

And here's my cocktail shaker:

#include <stdio.h>

int array[100];

void exchange (int array[], int i, int j)
{
  int temp;
  temp=array[i];
  array[i]=array[j];
  array[j]=temp;
}


void db_sort (int array [], int low, int up)
{
  int i, j;
  while (up>low)
  {
     j=low;          
     for (i=low;i<up; i++)   
   if (array[i]>array[i+1])
   {
     exchange (array, i, i+1);   
     j=i;
   }
     up=j;          
     for (i=up;i>low; i--)      
   if (array[i]<array[i-1])
   {
     exchange (array, i, i-1);   
     j=i;
   }
     low=j;          
  }
}

 I hope you can help me... I hope this question is not so lengthy.  

Answer
Hi,
  Please test the following code. I have typed that in notepad. Please test it before use. I am using pointer instead of the whole copy of array which you have used.
Also, I have modified the exchange logic to a safer one.
Hope it would work.

Thanks,
Dharmender Rai

#include <stdio.h>

// j should be the uppermost limit of the array
// i should be 0, lowest limit of the array
void exchange (int * array, int i, int j)
{
array[i]^=array[j];
array[j]^=array[i];
array[i]^=array[j];
}


void db_sort (int * array, int low, int up)
{
 int x, y;
 int swap = 1;
 while (swap) {
    for (x = low; x <= up ; ++x) {
  for (y = x; y <= up; ++y) {
         if (array[x] > array[y] {
         swap ||= 1;
         exchange (array, x, y)
         }
     else swap &&=0;
         }
    }
    for ( x = up ; x >= low; --x) {
       for (y = x; y >= low; --y) {
        if (array[x] < array[y] {
         swap ||= 1;
         exchange (array, x, y)
         }
        else swap &&=0;
         }
    }
}  

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Dharmender Rai

Expertise

I can answer general and system level C/C++ questions.

Experience

I have 5 years of experience in C++.

©2016 About.com. All rights reserved.