Các thuật toán sắp xếp nâng cao trong lập trình C++

Bài viết được sưu tầm từ daynhauhoc.com
Nov '14
MERGE SORT POLYPHASE (ĐA PHA)

#include"time.h"
#include"iostream"
#include"time.h"
#include"algorithm"
#include"fstream"
#include<conio.h>
#include<stdio.h>
using namespace std;

#define TRACE 0
void Swap(int** a, int** b)
{
 int* temp = *a;
 *a = *b;
 *b = temp;
}
void Swap(int&a, int&b)
{
 int temp = a;
 a = b;
 b = temp;
}
void Copy(int source[], int target[], int n)
{
 for (int i = 0; i < n; i++) target[i] = source[i];
}
void Print(char name[], int a[], int n)
{
 cout << name << ": ";
 for (int i = 0; i < n; i++)
  if (a[i] != -842150451) cout << a[i] << " ";
 cout << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
 long start = clock();

    /* reading number of lines */
ifstream fin1(fileName);
if (!fin1) // fin1 == NULL
{
 cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
 return NULL;
}
n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

/* reading each line, and assign to int array */
int* a = new int[n];
ifstream fin2(fileName);
int i = 0;
while (fin2 >> a[i++]);
fin2.close();

long end = clock();
cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
return a;
}
void Write2TextFile(int a[], int n, char* fileName)
{
 long start = clock();

    ofstream fout(fileName);
for (int i = 0; i < n; i++)
 fout << a[i] << endl;
fout.close();

long end = clock();
cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}
int* InitRandom(int&n)
{
 cout << "Enter n = "; cin >> n;
 int* a = new int[n];
 srand((unsigned int)time(0));
 for (int i = 0; i < n; i++)
 {
  //a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
  a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
 }
 return a;
}
int CountRuns(int Arr[], const int&numOfElemes)
{
 int counter = 0, i = 0;
 while (i<numOfElemes)
 {
  while (Arr[i] <= Arr[i + 1] && i<numOfElemes - 1)
   i++;
  i++;
  counter++;
 }
 return counter;
}
void Merge(int A[], int B[], int Target[], int&nA, int&nB, int&nTarget)
{
 int i = 0, j = 0;
 while (i<nA && j<nB)
 {
  int tempIndexA = i;
  int tempIndexB = j;
  while (A[i] <= A[i + 1] && i + 1<nA)
   i++;
  while (B[j] <= B[j + 1] && j + 1<nB)
   j++;
  while (tempIndexA <= i && tempIndexB <= j)
  {
   if (A[tempIndexA] <= B[tempIndexB])
    Target[nTarget++] = A[tempIndexA++];
   else
    Target[nTarget++] = B[tempIndexB++];
  }
  while (tempIndexA <= i)
   Target[nTarget++] = A[tempIndexA++];
  while (tempIndexB <= j)
   Target[nTarget++] = B[tempIndexB++];
  i++;
  j++;
 }
 nA -= i;
 nB -= j;
 for (int k = 0; k<nA; k++)
  A[k] = A[k + i];
 for (int k = 0; k <= nB; k++)
  B[k] = B[k + j];
}
void Distribute(int Arr[], int fixBasket[], int DynamicBasket[], const int&nArr, int&nfixBasket, int&nDyncBasket)
{
 int i = 0;
 int counter = 0;
 while (i<nArr)
 {
  int indexKeeper = i;
  while (Arr[i] <= Arr[i + 1] && i<nArr - 1)
   i++;
  if (counter % 2 == 0)
   for (int j = indexKeeper; j <= i; j++)
    fixBasket[nfixBasket++] = Arr[j];
  else
   for (int j = indexKeeper; j <= i; j++)
    DynamicBasket[nDyncBasket++] = Arr[j];
  counter++;
  i++;
 }
}

void MergeSort(int Arr[], const int&n)
{
 if (CountRuns(Arr, n) == 1) return;

    int * A = new int[n];
int * B = new int[n];
int * C = new int[n];
int nA = 0, nB = 0, nC = 0;
Distribute(Arr, A, B, n, nA, nB);

int pass = 0; // for TRACE
if (1)
{
 cout << "----------------------" << endl;
 cout << "Pass " << ++pass << endl;
 Print("A", A, nA);
 Print("B", B, nB);
}
do
{
 if (1)
 {
  cout << "----------------------" << endl;
  cout << "Pass " << ++pass << endl;
 }
 if (nA == 0)
 {
  Merge(B, C, A, nB, nC, nA);
  if (1) Print("A", A, nA);
  if (nC != 0)
  {
   if (1) Print("C", C, nC);
  }
  else if(nB != 0)
  {
   if (1) Print("B", B, nB);
  }
  if (CountRuns(A, nA) == 1 && nB == 0 && nC == 0)
  {
   Copy(A, Arr, n);
   break;
  }
  if (CountRuns(A, nA) != 1 && nB == 0 && nC == 0)
  {
   Distribute(A, B, C, nA, nB, nC);
   nA = 0;
   if (1)
   {
    cout << "----------------------" << endl;
    cout << "Pass " << ++pass << endl;
    Print("B", B, nB);
    Print("C", C, nC);
   }
  }
 }
 else if(nB == 0)
 {
  Merge(A, C, B, nA, nC, nB);
  if (1) Print("B", B, nB);
  if (nC != 0)
  {
   if (1) Print("C", C, nC);
  }
  else if(nA != 0)
  {
   if (1) Print("A", A, nA);
  }
  if (CountRuns(B, nB) == 1 && nA == 0 && nC == 0)
  {
   Copy(B, Arr, n);
   break;
  }
  if (nA == 0 && nB == 0 && CountRuns(B, nB) != 1)
  {
   Distribute(B, A, C, nB, nA, nC);
   nB = 0;
   if (1)
   {
    cout << "----------------------" << endl;
    cout << "Pass " << ++pass << endl;
    Print("A", A, nA);
    Print("C", C, nC);
   }
  }
 }
 else
 {
  Merge(A, B, C, nA, nB, nC);
  if (1) Print("C", C, nC);
  if (nA != 0)
  {
   if (1) Print("A", A, nA);
  }
  else if(nB != 0)
  {
   if (1)Print("B", B, nB);
  }
  if (CountRuns(C, nC) == 1 && nA == 0 && nB == 0)
  {
   Copy(C, Arr, n);
   break;
  }
  if (CountRuns(C, nC) != 1 && nA == 0 && nB == 0)
  {
   Distribute(C, A, B, nC, nA, nB);
   nC = 0;
   if (1)
   {
    cout << "----------------------" << endl;
    cout << "Pass " << ++pass << endl;
    Print("A", A, nA);
    Print("B", B, nB);
   }
  }
 }
} while (true);
}

void MergeSort_2(int Arr[], const int&n)
{
 if (CountRuns(Arr, n) == 1) return;

    int * NonKeeper1 = new int[n];
int * NonKeeper2 = new int[n];
int * Keeper = new int[n];
int nNonKeeper1 = 0, nNonKeeper2 = 0, nKeeper = 0;
Distribute(Arr, NonKeeper1, NonKeeper2, n, nNonKeeper1, nNonKeeper2);

int pass = 0; // for TRACE
if (1)
{
 cout << "----------------------" << endl;
 cout << "Pass " << ++pass << endl;
 Print("NonKeeper1", NonKeeper1, nNonKeeper1);
 Print("NonKeeper2", NonKeeper2, nNonKeeper2);
}
do
{
 Merge(NonKeeper1, NonKeeper2, Keeper, nNonKeeper1, nNonKeeper2, nKeeper);
 if (1)
 {
  cout << "----------------------" << endl;
  cout << "Pass " << ++pass << endl;
  Print("Keeper", Keeper, nKeeper);
  Print("NonKeeper1", NonKeeper1, nNonKeeper1);
  Print("NonKeeper2", NonKeeper2, nNonKeeper2);
 }
 if (nNonKeeper1 == 0 && nNonKeeper2 == 0)
 {
  if (CountRuns(Keeper, nKeeper) == 1)
  {
   Copy(Keeper, Arr, n);
   break;
  }
  else
  {
   Distribute(Keeper, NonKeeper1, NonKeeper2, nKeeper, nNonKeeper1, nNonKeeper2);
   nKeeper = 0;

   if (1)
   {
    cout << "----------------------" << endl;
    cout << "Pass " << ++pass << endl;
    Print("NonKeeper1", NonKeeper1, nNonKeeper1);
    Print("NonKeeper2", NonKeeper2, nNonKeeper2);
   }
  }
 }
 if (nNonKeeper1 == 0)
 {
  Swap(&NonKeeper1, &Keeper);
  Swap(nKeeper, nNonKeeper1);
 }
 else if(nNonKeeper2 == 0)
 {
  Swap(&NonKeeper2, &Keeper);
  Swap(nKeeper, nNonKeeper2);
 }
} while (true);
}

void main()
{
 if (TRACE)
 {
  int a[] = { 5, 11, 8, 13, 9, 7, 10, 12, 4, 2, 1, 6, 3 };
  //int a[] = {2,12,17,16,14,30,17,2,50,65,20,32,48,58,16,20,15,10,30,45,16};
  //int a[] = {2,5,3,60,34,22,45,56,43,54,23,32,5,8,6,9,44};
  int n = sizeof(a) / sizeof(*a);

     cout << "------- BEFORE -------" << endl;
 Print("BEFORE", a, n);

 MergeSort(a, n);
 //MergeSort_2(a, n);

 cout << "------- AFTER -------" << endl;
 Print("AFTER", a, n);
 _getch();
}
else
{
 // read init data from textfile
 int n;
 int* a = InitRandom(n);
 if (!a) return; // a == NULL

 // sort data
 long start = clock();
 MergeSort(a, n);
 //MergeSort_2(a, n);
 long end = clock();
 cout << "MergeSort.Polyphase is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;

 // write sorted data to textfile
 Write2TextFile(a, n, "output.txt");
 _getch();
}
}
MERGE SORT ĐỆ QUY

#include"time.h"
#include"algorithm"
#include"fstream"
#include"string"
#include"iostream"
using namespace std;

int* InitRandom(int&n)
{
 cout << "Enter n = "; cin >> n;
 int* a = new int[n];
 srand((unsigned int)time(0));
 for (int i = 0; i <n; i++)
 {
  //a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
  a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
 }
 return a;
}

void Write2TextFile(int a[], int n, char* fileName)
{
 long start = clock();

    ofstream fout(fileName);
for (int i = 0; i <n; i++)
 fout << a[i] << endl;
fout.close();

long end = clock();
cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
 long start = clock();

    /* reading number of lines */
ifstream fin1(fileName);
if (!fin1) // fin1 == NULL
{
 cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
 return NULL;
}
n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

/* reading each line, and assign to int array */
int* a = new int[n];
ifstream fin2(fileName);
int i = 0;
while (fin2 >> a[i++]);
fin2.close();

long end = clock();
cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
return a;
}
void Merge(int A[], int left, int mid, int right)
{
 int i = left, j = mid + 1, n = mid, m = right;
 int *temp = new int[right - left + 1];
 int pos = 0;
 while ((i <= n) && (j <= m))
 {
  if (A[i] <A[j])
  {
   temp[pos] = A[i];
   ++i; ++pos;
  }
  else
  {
   temp[pos] = A[j];
   ++j; ++pos;
  }
 }
 while (i <= n)
 {
  temp[pos] = A[i];
  ++i; ++pos;
 }
 while (j <= m)
 {
  temp[pos] = A[j];
  ++j; ++pos;
 }

    for (i = 0; i < pos; ++i)
 A[left + i] = temp[i];
delete temp;
}

void MergeSort(int A[], int left, int right)
{
 if (left<right)
 {
  int mid = (left + right) / 2;
  MergeSort(A, left, mid);
  MergeSort(A, mid + 1, right);

     Merge(A, left, mid, right);
}
}


void print(int a[], int n)
{
 for (int i = 0; i<n; i++)
 {
  cout << a[i] << " ";
 }
 cout << endl;
}

void main()
{
 int n;
 int *a = InitRandom(n);


    //int a[8]={5,9,8,1,7,3,4,6};
cout << "Before: " << endl;
print(a, n);
cout << "---------------------" << endl;
long start = clock();
MergeSort(a, 0, n - 1);
long end = clock();
cout << "---------------------" << endl;
cout << "After: " << endl;
print(a, n);

cout << "Merge Sort (n= " << n << ") = " << end - start << " (ms)" << endl;
Write2TextFile(a, n, "output.txt");
Read2TextFile(n,"output.txt");

system("pause");
}
MERGE SORT NATURAL (TỰ NHIÊN)

#include"time.h"
#include"iostream"
#include"time.h"
#include"algorithm"
#include"fstream"
#include<conio.h>
#include<stdio.h>
using namespace std;

#define TRACE 0
int* Read2TextFile(int&n, char* fileName)
{
 long start = clock();

    /* reading number of lines */
ifstream fin1(fileName);
if (!fin1) // fin1 == NULL
{
 cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
 return NULL;
}
n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

/* reading each line, and assign to int array */
int* a = new int[n];
ifstream fin2(fileName);
int i = 0;
while (fin2 >> a[i++]);
fin2.close();

long end = clock();
cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
return a;
}
void Write2TextFile(int a[], int n, char* fileName)
{
 long start = clock();

    ofstream fout(fileName);
for (int i = 0; i < n; i++)
 fout << a[i] << endl;
fout.close();

long end = clock();
cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}
int* InitRandom(int&n)
{
 cout << "Enter n = "; cin >> n;
 int* a = new int[n];
 srand((unsigned int)time(0));
 for (int i = 0; i < n; i++)
 {
  //a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
  a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
 }
 return a;
}
void Print(char name[], int a[], int n)
{
 cout << name << ": ";
 for (int i = 0; i < n; i++)
  if (a[i] != -842150451) cout << a[i] << " ";
 cout << endl;
}
/* ref: khai.huynhminh92@gmail.com (HSU.K10) */
int CountRuns(int Arr[], const int&numOfElemes)
{
 int counter = 0, i = 0;
 while (i<numOfElemes)
 {
  while (Arr[i] <= Arr[i + 1] && i<numOfElemes - 1)
   i++;
  i++;
  counter++;
 }
 return counter;
}
void Merge(int A[], int B[], int Target[], int&nA, int&nB, int&nTarget)
{
 int i = 0, j = 0;
 while (i<nA && j<nB)
 {
  int tempIndexA = i;
  int tempIndexB = j;
  while (A[i] <= A[i + 1] && i + 1<nA)
   i++;
  while (B[j] <= B[j + 1] && j + 1<nB)
   j++;
  while (tempIndexA <= i && tempIndexB <= j)
  {
   if (A[tempIndexA] <= B[tempIndexB])
    Target[nTarget++] = A[tempIndexA++];
   else
    Target[nTarget++] = B[tempIndexB++];
  }
  while (tempIndexA <= i)
   Target[nTarget++] = A[tempIndexA++];
  while (tempIndexB <= j)
   Target[nTarget++] = B[tempIndexB++];
  i++;
  j++;
 }
 while (i<nA)
  Target[nTarget++] = A[i++];
 while (j<nB)
  Target[nTarget++] = B[j++];
 nA = nB = 0; //reset to 0
}
void Distribute(int Arr[], int fixBasket[], int DynamicBasket[], int&nArr, int&nfixBasket, int&nDyncBasket)
{
 int i = 0;
 int counter = 0;
 while (i<nArr)
 {
  int indexKeeper = i;
  while (Arr[i] <= Arr[i + 1] && i<nArr - 1)
   i++;
  if (counter % 2 == 0)
   for (int j = indexKeeper; j <= i; j++)
    fixBasket[nfixBasket++] = Arr[j];
  else
   for (int j = indexKeeper; j <= i; j++)
    DynamicBasket[nDyncBasket++] = Arr[j];
  counter++;
  i++;
 }
 nArr = 0;
}
void MergeSort(int a[], int n)
{
 int pass = 0; // for TRACE

    int* b = new int[n];
int* c = new int[n];
while (CountRuns(a, n) > 1)
{
 int nb = 0, nc = 0;
 Distribute(a, b, c, n, nb, nc);
 if (1)
 {
  cout << "----------------------" << endl;
  cout << "Pass " << ++pass << endl;
  Print("b", b, nb);
  Print("c", c, nc);
 }
 Merge(b, c, a, nb, nc, n);
 if (1)Print("a", a, n);
}
}


void main()
{
 if (TRACE)
 {
  //int a[] = {12,2,8,5,1,6,4,15};
  //int a[] = {5,1,2,8,4,17,10,12,4,3,24,1,4};
  int a[] = { 2, 5, 3, 60, 34, 22, 45, 56, 43, 54, 23, 32, 5, 8, 6, 9, 44 };
  int n = sizeof(a) / sizeof(*a);

     cout << "------- BEFORE -------" << endl;
 Print("a", a, n);

 MergeSort(a, n);

 cout << "------- AFTER -------" << endl;
 Print("a", a, n);
 _getch();
}
else
{
 // read init data from textfile
 int n;
 int* a = InitRandom(n);
 if (!a) return; // a == NULL

 // sort data
 long start = clock();
 MergeSort(a, n);
 long end = clock();
 cout << "MergeSort.Natural is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;

 // write sorted data to textfile
 Write2TextFile(a, n, "ouput.txt");
 _getch();
}
}
HEAP SORT

#include"time.h"
#include"algorithm"
#include"fstream"
#include"string"
#include"iostream"
using namespace std;

int* InitRandom(int&n)
{
 cout << "Enter n = "; cin >> n;
 int* a = new int[n];
 srand((unsigned int)time(0));
 for (int i = 0; i <n; i++)
 {
  //a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
  a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
 }
 return a;
}

void Write2TextFile(int a[], int n, char* fileName)
{
 long start = clock();

    ofstream fout(fileName);
for (int i = 0; i <n; i++)
 fout << a[i] << endl;
fout.close();

long end = clock();
cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
 long start = clock();

    /* reading number of lines */
ifstream fin1(fileName);
if (!fin1) // fin1 == NULL
{
 cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
 return NULL;
}
n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

/* reading each line, and assign to int array */
int* a = new int[n];
ifstream fin2(fileName);
int i = 0;
while (fin2 >> a[i++]);
fin2.close();

long end = clock();
cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
return a;
}
void print(int *a, int n)
{
 for (int i = 0; i<n; i++)
 {
  cout << a[i] << " ";
 }
 cout << endl;
}
void Swap(int&a, int&b) // Hoan vi
{

    int c = a;
a = b;
b = c;
}
void Shift(int a[], int left, int right){
 int x, curr, joint;
 curr = left; joint = 2 * curr + 1;
 x = a[curr];
 while (joint <= right){
  if (joint <right){
   if (a[joint] <a[joint + 1]){
    joint = joint + 1;
   }
  }
  if (a[joint]<x){
   break;
  }
  a[curr] = a[joint];
  curr = joint;
  joint = 2 * curr + 1;
 }
 a[curr] = x;
}
void CreateHeap(int a[], int n)
{
 int l;
 l = n / 2;
 while (l >= 0)
 {
  Shift(a, l, n);
  l = l - 1;
 }
}
void HeapSort(int *a, int&n)
{
 int dem = 1;
 int r;
 CreateHeap(a, n);
 r = n - 1;
 while (r > 0)
 {
  Swap(a[0], a[r]);
  r = r - 1;
  Shift(a, 0, r);
  cout << "Lan " << dem << " :" << endl;
  print(a, n);
  dem++;
 }
}
void main()
{

    int n = 8;
int *a=InitRandom(n);
Write2TextFile(a,n,"input.txt");
a=Read2TextFile(n,"input.txt");
//int a[8] = { 11, 3, 5, 4, 9, 15, 19, 7 };
cout << "Before: ";
print(a, n);
cout << "-----------------------" << endl;
HeapSort(a, n);
cout << "-----------------------" << endl;
cout << "After: ";
print(a, n);
Write2TextFile(a,n,"output.txt");
system("pause");
}
RADIX SORT

#include"time.h"
#include"algorithm"
#include"fstream"
#include"string"
#include"iostream"
#include"stdio.h"
using namespace std;
#define MAX 10000
#define SHOWPASS

int* InitRandom(int&n)
{
 cout << "Enter n = "; cin >> n;
 int* a = new int[n];
 srand((unsigned int)time(0));
 for (int i = 0; i <n; i++)
 {
  //a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
  a[i] = ((rand() << 15) | rand()) % (n * 10) + 1; // [0:n-1] + 1 = [1:n]
 }
 return a;
}

void Write2TextFile(int a[], int n, char* fileName)
{
 long start = clock();

    ofstream fout(fileName);
for (int i = 0; i <n; i++)
 fout << a[i] << endl;
fout.close();

long end = clock();
cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
 long start = clock();

    /* reading number of lines */
ifstream fin1(fileName);
if (!fin1) // fin1 == NULL
{
 cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
 return NULL;
}
n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

/* reading each line, and assign to int array */
int* a = new int[n];
ifstream fin2(fileName);
int i = 0;
while (fin2 >> a[i++]);
fin2.close();

long end = clock();
cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
return a;
}


void Write_sorted(int *a, int n, char* fileName)
{
 long start = clock();
 int dem = 1;
 ofstream fout(fileName);
 fout << "lan  " << dem << " ";
 dem++;
 for (int i = 0; i <n; i++)
  fout << a[i] << " ";

    fout.close();

long end = clock();
}

void print(int *a, int n)
{
 int i;
 for (i = 0; i <n; i++)
  cout << a[i] << " ";

}

void radixsort(int *a, int n, char *fileName)
{
 int dem = 1;

    ofstream fout(fileName);
int i, b[MAX], m = a[0], exp = 1;
for (i = 1; i <n; i++)
{
 if (a[i] > m)
  m = a[i];
}

while (m / exp > 0)
{
 int bucket[10] =
 { 0 };
 for (i = 0; i <n; i++)
  bucket[(a[i] / exp) % 10]++;
 for (i = 1; i < 10; i++)
  bucket[i] += bucket[i - 1];
 for (i = n - 1; i >= 0; i--)
  b[--bucket[(a[i] / exp) % 10]] = a[i];
 for (i = 0; i <n; i++)
  a[i] = b[i];
 exp *= 10;

 #ifdef SHOWPASS

 cout << "\nPASS " << dem++ << " :";
 print(a, n);

 fout << "lan  " << dem << " : ";

 for (int i = 0; i <n; i++)
  fout << a[i] << " ";


 fout << endl;
#endif

    }
fout.close();
}

void main()
{

    int n;
int *a = InitRandom(n);
Write2TextFile(a, n, "input.txt");
a = Read2TextFile(n, "input.txt");
//int a[100]={170, 45, 75, 90, 802, 2,24, 66};
radixsort(a, n, "sorted.txt");
cout << endl;
Write2TextFile(a, n, "output.txt");
system("pause");
}
SHELL SORT

#include"time.h"
#include"algorithm"
#include"fstream"
#include"string"
#include"iostream"
using namespace std;

int* InitRandom(int&n)
{
 cout << "Enter n = "; cin >> n;
 int* a = new int[n];
 srand((unsigned int)time(0));
 for (int i = 0; i <n; i++)
 {
  //a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
  a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
 }
 return a;
}

void Write2TextFile(int a[], int n, char* fileName)
{
 long start = clock();

    ofstream fout(fileName);
for (int i = 0; i <n; i++)
 fout << a[i] << endl;
fout.close();

long end = clock();
cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
 long start = clock();

    /* reading number of lines */
ifstream fin1(fileName);
if (!fin1) // fin1 == NULL
{
 cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
 return NULL;
}
n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

/* reading each line, and assign to int array */
int* a = new int[n];
ifstream fin2(fileName);
int i = 0;
while (fin2 >> a[i++]);
fin2.close();

long end = clock();
cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
return a;
}

void print(int a[], int n)
{
 for (int i = 0; i<n; i++)
 {
  cout << a[i] << " ";
 }
 cout << endl;
}

void sort(int a[], int n)
{
 cout << "Before: ";
 print(a, n);
 cout << "-----------------------------------" << endl;
 long start = clock();
 int i, j, gap[8] = { 701, 301, 132, 57, 23, 10, 4, 1 };
 int temp;

    for (int k = 0; k<8; k++)
{
 for (i = gap[k]; i <n; i += 1)
 {
  temp = a[i];
  for (j = i; j >= gap[k] && a[j - gap[k]] > temp; j -= gap[k])
  {
   a[j] = a[j - gap[k]];
  }
  a[j] = temp;
 }

 cout << "gap =" << gap[k] << endl;
 print(a, n);
}
cout << "-----------------------------------" << endl;
cout << "After: ";
print(a, n);
long end = clock();
cout << "Sort time: " << end - start << endl;
}

void main()
{

    int n;
int *a = InitRandom(n);
Write2TextFile(a, n, "input.txt");
a = Read2TextFile(n, "input.txt");
sort(a, n);
Write2TextFile(a, n, "output.txt");
system("pause");
}

Comments

Post a Comment

Popular posts from this blog

Duyệt cây nhị phân theo chiều rộng _Lập trình C++

Image
*) Đối tượng hướng đến:   - Các bạn đang học cấu trúc dữ liệu và giải thuật, biết cách sử dụng con trỏ, biết về stack, queue   - Các bạn khác đọc tham khảo *)Nội dung:     Có rất nhiều cách duyệt cây nhị phân, mỗi cách phù hợp với từng nhu cầu riêng của lập trình viên. Thường thì chúng ta duyệt theo chiều sâu (tức là duyệt LNR, LRN, NLR,...). Nhưng ít đề cập đến việc duyệt cây theo chiều rộng. Vậy nên mình sẽ chia sẻ với các bạn một phần nhỏ về kiến thức duyệt cây theo chiều rộng. - Đầu tiên cần biết duyệt cây theo chiều rộng tức là sẽ xuất các giá trị trên cây theo thứ tự từ trái qua phải và từ trên xuống dưới, xét cây sau: nếu xuất theo chiều rộng thì thứ tự xuất sẽ là: 40 5 45 35 56 15 48 13 16 47 49 Để làm được điều này chúng ta cần sư dụng một hàng đợi (queue), hàng đợi này lần lượt sẽ chứa các nút theo thứ tự trên, tức là chứa 40-> 5-> 45-> 35-> 56-> 15-> 48-> 13 ->16-> 47-> 49. Mà theo quy luật của hàng đợi, thì phần tử và...
Read more

Duyệt cây không dùng đệ quy và stack _Lập trình C++ căn bản

* )Giới thiệu: - Những thao tác trên cây thường rất đa dạng, mỗi loại thao tác lại có những phương thức và cách thao tác khác nhau. Thường thì người ta sẽ dùng đệ quy để tránh sự dài dòng, rắc rối. Chính vì đó, trong các tài liệu học tập trên trường học người ta ít đề cập đến việc thao tác với cây mà KHÔNG cần dùng đệ quy. Vậy hôm nay mình xin giới thiệu với các bạn cách duyệt cây nhị phân tìm kiếm theo kiểu InOrder(duyệt LNR) để minh họa.  Các kiểu duyệt khác (PreOrder, PostOrder,...) các bạn tự điều chỉnh lại cho phù hợp. *) Đối tượng hướng đến :  - Các bạn đang học lập trình C++, cấu trúc dữ liệu và giải thuật, có kiến thức vững chắc về con trỏ, cây nhị phân. *) Nội dung:  từ trước đến nay, khi tạo một cây thì chúng ta luôn thấy các nút lá có 2 con trỏ left và right là NULL(đây là dấu hiệu để nhận biết nó là nút lá(nói hơi thừa 😁😁😁😁)), ta sẽ lợi dụng các nút trống này để kết nối với các Node "tổ tiên" của nó. Những tác vụ này khiến các Node trên cây sẽ liên ...
Read more

Bài toán Upper Bound và Lower Bound trên cây nhị phân tìm kiếm

     Cây nhị phân tìm kiếm là một cấu trúc dữ liệu phổ biến được dùng để lưu trữ thông tin một cách có tổ chức, mọi thông tin trên cây đều tuân thủ quy luật nhất định, từ đó, việc quản lý và tìm kiếm dữ liệu được tối ưu hơn. Các thao tác trên cây thường rất đa dạng và đơn giản, nhưng không phải thao tác nào cũng đơn giản, ví dụ như thuật toán tìm Upper bound và Lower bound, nó đòi hỏi bạn phải biết cách dùng đệ quy khéo léo(à quên giới thiệu về Upper và lower bound, cứ hiểu đơn giản như sau,  Cho một dãy số, tìm trong dãy các số lower bound của x (số lớn nhất mà nhỏ hơn x) và upper bound của x (số nhỏ nhất mà lớn hơn x) ), để làm được bài này thì có rất nhiều cách, chẳng hạn sử dụng mảng để lưu trữ có sắp xếp, sau đó duyệt tuyến tính hoặc dùng BinarySearch để tìm kiếm, hoặc dùng danh sách liên kết đơn, kép, vòng,..tùy các bạn. Nhưng có lẽ tốt hơn hết là dùng cây nhị phân tìm kiếm,  việc thêm vào và tìm kiếm sẽ nhanh hơn nhiều. Giả sử bài toán được "biến tấu" ...
Read more