May 29, 2009

資料結構作業八之一:QUICK SORT

#include<iostream>
#include<time.h>

using namespace std;

#define gStackSize 100
#define gLimit StackSize -1

int gSP = 0;
int stack[gStackSize];

void CreateDataArray(int *DataArray, int Input);
bool QuickSort(int *DataArray, int n);

void main(void)
{
 int Input;
 int *DataArray;


 cout << "Please input the number of node: ";
 cin >> Input;
 DataArray = new int[Input];
 
 CreateDataArray(DataArray, Input);

 for(int i= 0; i<Input; i++)
 {
  cout << DataArray[i] << " ";
 }
 cout << endl;


 QuickSort(DataArray, Input);
 for(int i= 0; i<Input; i++)
 {
  cout << DataArray[i] << " ";
 }
 cout << endl;
}

void PUSH(int data)
{
 stack[gSP] = data;
 gSP++;
}

int POP(void)
{
 int data;

 gSP--;
 data = stack[gSP];

 return data;
}

void CreateDataArray(int *DataArray, int Input)
{

 int n, i, Data;

 for(n = 0; n < Input; n++)
 {
  time_t t;
  tm NOW;
  while(1)
  {
   int Flag = 0;
   time(&t);
   localtime_s(&NOW, &t);

   Data = ((rand()<<15) | rand() * NOW.tm_sec) % 100;
   for(i = 0; i <n; i++)
   {
    if(DataArray[i] == Data)
     Flag = 1;
   }
   if (!Flag)
    break;
  }
  DataArray[n] = Data;
 }
}

bool QuickSort(int *DataArray, int n)
{
 int Left, Right, Scan, Counter, RPosition, NRight1, NRight2, NLeft;
 int temp1, temp2;

 Left = 0;
 Right = n-1;

 PUSH(Left);
 PUSH(Right);

PASS1:
 if(gSP < 0)
  return false;

 Right = POP();
 Left = POP();

 if(Left == Right)
  goto PASS1;

 Counter = 0;
 Scan = Left + 1;

 do
 {
  if(DataArray[Left] >= DataArray[Scan])
   Counter++;

  Scan++;
 }while(Scan <= Right);

 RPosition = Left + Counter;

 if(!(RPosition <= Left))
 {
  NRight1 = RPosition - 1;
  PUSH(Left);
  PUSH(NRight1);
 }
 NLeft = RPosition +1;

 if(!(NLeft > Right))
 {
  NRight2 = Right;
  PUSH(NLeft);
  PUSH(NRight2);
 }

 if(!(RPosition == Right))
 {
  if(!(RPosition == Left))
  {
   temp1 = DataArray[Left];
   DataArray[Left] = DataArray[RPosition];
   DataArray[RPosition] = temp1;
   Scan = Left;
  } else {
   goto PASS1;
  }
 } else {
   int temp;
   temp = DataArray[Left];
   DataArray[Left] = DataArray[RPosition];
   DataArray[RPosition] = temp;
   goto PASS1;
 }

 do
 {
  if(!(Scan < RPosition))
  {
   if(Scan > RPosition)
   {
    if(DataArray[RPosition] >= DataArray[Scan])
    {
     temp2 = POP();
     temp1 = DataArray[temp2];
     DataArray[temp2] = DataArray[Scan];
     DataArray[Scan] = temp1;
    }
   }
  } else {
   if(!(DataArray[RPosition] >= DataArray[Scan]))
    PUSH(Scan);
  }
  
  Scan++;
 }while(!(Scan > Right));

 goto PASS1;
}

=============================================
Please input the number of node: 15
24 4 16 60 28 0 76 56 12 84 64 96 52 8 80
0 4 8 12 16 24 28 52 56 60 64 76 80 84 96
請按任意鍵繼續 . . .
=============================================

Today's Visitors: 0 Total Visitors: 34
Personal Category: 台北科技大學 Topic: learning / education / advanced edu.
Previous in This Category: 搞死人的資料結構作業七:BST(Add / Del)   Next in This Category: 資料結構作業八之二:WINNER TREE(SELECTION TREE)
[Trackback URL]

Post A Comment









Yes No



Please input the magic number:

( Prevent the annoy garbage messages )
( What if you cannot see the numbers? )
Please input the magic number

誰來收藏
Loading ...
unlog_NVPO 0