|
Heap sort is generally used in database systems. It fastens the sort process comparing to other sort algorithms. To show the efficiency of the algorithm a student record database is created. Records are sorted using two way merge and heap sort algorithms. C Source Code Display Language is TURKISH File Name: HEAPMRG.CPP #include<heapmrg.h>
void draw_main_menu(char x, char y) {
gotoxy(x, y); printf(" -========¬ ");
gotoxy(x, y+1);printf(" ¦ MENU ¦ ");
gotoxy(x, y+2);printf("-=====¦========¦======¬");
gotoxy(x, y+3);printf("¦ 1.---> Giris ¦");
gotoxy(x, y+4);printf("¦ 2.---> Heap Sort ¦");
gotoxy(x, y+5);printf("¦ 3.---> 2 Way Merge ¦");
gotoxy(x, y+6);printf("¦ 4.---> Liste ¦");
gotoxy(x, y+7);printf("¦ 5.---> Exit ¦");
gotoxy(x, y+8);printf("L=====================-");
}
void draw_static(int x, int y) {
gotoxy(x, y); printf("Öğrenci No :");
gotoxy(x, y+1);printf("Adı :");
gotoxy(x, y+2);printf("Soyadı :");
gotoxy(x, y+3);printf("Not 1 :");
gotoxy(x, y+4);printf("Not 2 :");
gotoxy(x, y+5);printf("Not 3 :");
}
// Öğrenci bilgilerinin tutulduğu bloğun boşaltılması işlemi
void erase_record_content(ogr_kayit *ogr) {
int i;
ogr[0].no = 0;
for(i=0;i<14;i++) ogr[0].adi[i]= 0;
for(i=0;i<14;i++) ogr[0].soyadi[i]= 0;
ogr[0].d1=0;
ogr[0].d2=0;
ogr[0].d3=0;
}
// fopen ile açılan dosyalar için C'de file uzunluğunu veren standart bir
// fonksiyon yok. Dosya uzunluğu aşağıdaki fonksiyonla bulunur.
long filesize(FILE *stream)
{
long curpos, length;
curpos = ftell(stream);
fseek(stream, 0L, SEEK_END);
length = ftell(stream);
fseek(stream, curpos, SEEK_SET);
return(length);
}
int giris() {
FILE *file_handle;
char ch;
int record_num=0, written;
ogr_kayit ogr;
if ((file_handle = fopen("hkayit.dat","a+b")) == NULL )
if ((file_handle = fopen("hkayit.dat","w+b")) == NULL ) {
clrscr();
printf("Dosya açılamadı veya oluşturulamadı. ");sleep(2);
return(-1);
}
// Öğrenci bilgilerinin girilmesi...
do {
clrscr();
printf(" ************* Bilgi Girişi *************");
draw_static(1, ypos);
gotoxy(xpos, ypos);scanf("%d", &ogr.no);
gotoxy(xpos, ypos+1);scanf("%s", ogr.adi);
gotoxy(xpos, ypos+2);scanf("%s", ogr.soyadi);
gotoxy(xpos, ypos+3);scanf("%d", &ogr.d1);
gotoxy(xpos, ypos+4);scanf("%d", &ogr.d2);
gotoxy(xpos, ypos+5);scanf("%d", &ogr.d3);
record_num++;
// Blok dolmuş ise dosyaya yazılıp diğer bloğa geçilir.
if ((record_num > (record_num_b-1))) {
fseek(file_handle, 0L, SEEK_END);
fwrite(&ogr, one_block, 1, file_handle);
erase_record_content(&ogr);
record_num = 0;
written = 1;
}
else written = 0;
gotoxy(1, ypos+7);
printf("Tekrar kayıt girecekmisiniz(E/H)?");ch = getch();
} while ((ch=='e') || (ch=='E'));
// Yukardaki döngüden çıkıldığında dosyaya yazılmamış ise
// son bulunulan blok dosyaya yazılır.
if ( written == 0) {
fseek(file_handle, 0L, SEEK_END);
fwrite(&ogr, one_block, 1, file_handle);
}
fclose(file_handle);
return(0);
}
int heap_tree(int nn, ogr_kayit A[] ) {
int i, med;
ogr_kayit tmp;
med =nn / 2 ;
for(i=0;i<med;i++)
if ((A[i].no > A[i+i].no) && ((i+i) <= nn)) {
tmp = A[i];
A[i] = A[i+i];
A[i+i] = tmp;
heap_tree(nn, A);
}
else if((A[i].no > A[i+i+1].no) && ((i+i+1) <= nn)) {
tmp = A[i];
A[i] = A[i+i+1];
A[i+i+1] = tmp;
heap_tree(nn, A);
}
return(0);
}
int heap_sort() {
FILE *file_handle;
long num_of_records, place;
int i, j, m ,caunt, t;
ogr_kayit x, A[5];
if ((file_handle = fopen("hkayit.dat","r+b")) == NULL ) {
clrscr();
printf("Dosya açılamadı. ");sleep(2);
return(-1);
}
num_of_records = filesize(file_handle) / one_block;
caunt = num_of_records / record_num_b;
for(t=0;t<caunt;t++) {
fseek(file_handle, block_size_bytes*t,SEEK_SET);
for(i=0;i<5;i++) {
if (fread(&A[i], one_block, 1, file_handle) != 1) {
printf("\n %d. adresten itibaren okuma yapılamadı", ftell(file_handle));
sleep(1);return(-1);
}
}
heap_tree(record_num_b, A);
m = record_num_b;
for(i=0;i<record_num_b;i++) {
x = A[0];
for(j=0;j<(record_num_b-1);j++)
A[j] = A[j+1];
A[record_num_b-1] = x;
m--;
heap_tree(m, A);
}
fseek(file_handle, -block_size_bytes, SEEK_CUR);
for(i=0;i<record_num_b;i++)
fwrite(&A[i], one_block, 1, file_handle);
}
fclose(file_handle);
return(0);
}
// A[n], B[m]:20 record. C[k]:30 record.
int merge(int n, ogr_kayit A[], int m, ogr_kayit B[], ogr_kayit C[]) {
int i=0, j=0, k=-1, t;
while((j < m) && (i < n)) {
k++;
if (A[i].no < B[j].no) {
C[k] = A[i];
i++;
}
else {
C[k] = B[j];
j++;
}
}
if (i < n)
for(t=i;t<=n;t++) {
k++;
C[k] = A[t];
}
if (j < m)
for(t=j;t<=m;t++) {
k++;
C[k] = B[t];
}
return(0);
}
int start_two_way_merge() {
int small, small_piece, big_piece, m, i, j, n1, m1, k1;
long place, record_num;
ogr_kayit A[20], B[20], C[30];
FILE *file_handle;
if ((file_handle = fopen("hkayit.dat","r+b")) == NULL ) {
clrscr();
printf("Dosya açılamadı. ");sleep(2);
return(-1);
}
record_num = filesize(file_handle) / one_block; // = 30
big_piece = record_num / (record_num_b * 2); // = 3; record bazında işlem için
small_piece = record_num / record_num_b; // = 6
small = record_num_b; // = 5
while(big_piece > 1) {
m = 0;
fseek(file_handle, 0L, SEEK_SET);
for(i=0;i<big_piece;i++) {
j = 0;
while( (j < small) && (m < record_num) ) {
fseek(file_handle, m*one_block, SEEK_SET);
if (fread(&A[j], one_block, 1, file_handle) != 1) {
clrscr();
printf("hkayit.dat dosyasından %d. adresten itibaren okunamadı.", ftell(file_handle));
sleep(2);
return(-1);
}
else {
j++;
m++;
}
}
n1 = j;
j = 0;
while( (j < small) && (m < record_num) ) {
if (fread(&B[j], one_block, 1, file_handle) != 1) {
clrscr();
printf("hkayit.dat dosyasından %d. adresten itibaren okunamadı.", ftell(file_handle));
sleep(2);
return(-1);
}
else {
j++;
m++;
}
}
m1 = j;
if (m1 != 0) { //
if (merge(n1, A, m1, B, C) == -1) {
gotoxy(1,18);
printf("\n Hata!\nMerge işlemi yapılamadı.\nbig_piece :%d\nsmall_piece:%d\nsmall
:%d",big_piece, small_piece, small) ;
sleep(2);
return(-1);
}
}
else {
printf("\nSon bölüme geldik. Burada B[20] dizisinin okunmuş olması gerek.\n");
small = small << 1;
j = 0;
m = 0;
fseek(file_handle, 0L, SEEK_SET);
while( (j < small) && (m < record_num) ) {
if (fread(&B[j], one_block, 1, file_handle) != 1) {
clrscr();
printf("hkayit.dat dosyasından %d. adresten itibaren okunamadı.", ftell(file_handle));
sleep(2);
return(-1);
}
else {
j++;
m++;
}
}
m1 = j;
if (merge(n1, A, m1, B, C) == -1) {
gotoxy(1,18);
printf("\n Hata!\nMerge işlemi yapılamadı.\nbig_piece :%d\nsmall_piece:%d\nsmall :%d"
,big_piece, small_piece, small) ;
sleep(2);
return(-1);
}
}
k1 = n1 + m1;
place = k1 * one_block;
if (place < filesize(file_handle))
fseek(file_handle, -place, SEEK_CUR);
else
fseek(file_handle, 0L, SEEK_SET);
for(j=0;j<k1;j++)
fwrite(&C[j], one_block, 1, file_handle);
}
small_piece++;
small_piece = small_piece >> 1; // x = x / 2 işlemini yapar
big_piece++;
big_piece = big_piece >> 1; // x = x / 2
small = small << 1; // x = x * 2
}
fclose(file_handle);
return(0);
}
int liste() {
FILE *file_handle;
int ogr_no, i, j, found;
ogr_kayit ogr[record_num_b];
struct text_info ti;
gettextinfo(&ti);
if ((file_handle = fopen("hkayit.dat","r+b")) == NULL ) {
clrscr();
printf("Dosya açılamadı... ");
sleep(2);
return(-1);
}
clrscr();
printf(" -==== Öğr. No ====== Adı ===== Soyadı === Ders1 = Ders2 = Ders3 =====¬\n");
j = 1;
do {
erase_record_content(ogr);
if (fread(&ogr, block_size_bytes, 1, file_handle) == 0) {
printf("Kayit.dat dosyasında okuma işlemi yapılamadı...\n");
sleep(3);
fclose(file_handle);
return(-1);
}
for(i=0;i<record_num_b;i++) {
if (ogr[i].no > 0) {
gotoxy( 1, wherey());printf(" ¦");
gotoxy( 8, wherey());printf("%d.",j);
gotoxy(13, wherey());printf("%d", ogr[i].no);
gotoxy(24, wherey());printf("%s", ogr[i].adi);
gotoxy(35, wherey());printf("%s", ogr[i].soyadi);
gotoxy(49, wherey());printf("%2d", ogr[i].d1);
gotoxy(57, wherey());printf("%2d", ogr[i].d2);
gotoxy(66, wherey());printf("%2d", ogr[i].d3);
gotoxy(71, wherey());printf(" ¦\n");
}
if (wherey() == ti.screenheight ) {
gotoxy(1,ti.screenheight);
printf(" L===============================================
=====================-");
getch();
clrscr();
printf(" -==== Öğr. No ====== Adı ===== Soyadı === Ders1 = Ders2 = Ders3 =====¬\n");
}
j++;
}
} while (filesize(file_handle) != ftell(file_handle));
if (wherey() < ti.screenheight )
printf(" L=======================================================
=============-");
getch();
fclose(file_handle);
return(0);
}
void menu() {
char ch;
struct text_info ti;
gettextinfo(&ti);
while ((ch!='5') && (ch!=27)) {
clrscr();
draw_main_menu(25, 2);
gotoxy(ti.screenwidth, ti.screenheight);
ch = getch();
switch (ch) {
case '1': { giris(); break; }
case '2': { heap_sort();break; }
case '3': { start_two_way_merge(); break; }
case '4': { liste(); break;}
case '5': break;
case 27 : break;
}
}
}
void main() {
menu();
}
File Name: HEAPMRG.H //*******************************************
// Include Section
//*******************************************
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<dos.h>
//*******************************************
// Definition Section
//*******************************************
#define xpos 13
#define ypos 5
#define block_size_bytes 190
#define one_block 38
#define record_num_b 5
//*******************************************
// Global Variables Section
//*******************************************
typedef struct {
int no;
char adi[15], soyadi[15];
int d1;
int d2;
int d3;
} ogr_kayit;
//ogr_kayit A[5];
//*******************************************
// Function Definitions Section
//*******************************************
void draw_main_menu(char x, char y);
void draw_static(int x, int y);
void erase_record_content(ogr_kayit *ogr);
int giris();
int heap_tree(int nn, ogr_kayit A[]);
int heap_sort();
int two_way_merge();
int start_two_way_merge();
long filesize(FILE *stream);
int liste();
void menu();
Sample Execution Random 30 record: Page 1 
Random 30 record: Page 2 
After the Heap Sort: Page 1 
After the Heap Sort: Page 2 
After Two Way Merge: Page 1 
After Two Way Merge: Page 2 
| | 
Studies 
