Custom Search
searching and sorting in C++
IN THIS PROJECT I HAVE INCLUDED ALL TYPES OF SEARCHING and SORTING.
/*******************************************************
* MYCPLUS Sample Code - http://www.mycplus.com *
* *
* This code is made available as a service to our *
* visitors and is provided strictly for the *
* purpose of illustration. *
* *
* Please direct all inquiries to saqib at mycplus.com *
*******************************************************/
// Declaration of libraries
# include
# include
# include
#include
#include
#include
#include
// Function related to sorting in class sorting
class sorting
{
int array[50],array1[50],final[100],i,n,m,j;
public:
// Function to read an array
void read();
// Function to read arrays for merge sort
void read_mer();
// Function to display an array
void display();
// Function to perform bubble sort
void bub_sort();
// Function to perform selection sort
void Sel_sort();
// Function to perform insertion sort
void Ins_sort();
// Function to perform quick sort
void Qui_sort();
// Function to perform heap sort
void Heap_sort();
// Function to build a heap
void heap(int array[], int n);
// Function to interchange the value of root node with a
// child node in heap sort
void below_heap(int array[], int first, int last);
// Function to perform merges sort
void Mer_sort();
// Function to perform shell sort
void Shell_sort();
// Function to split the array into two halves during quick sort
void partition(int array[], int beg, int end, int *loc);
// Function to called recursively partition itself
void quick_sort(int array[], int n, int l, int u);
// Function to draw a box at front screen
void box(int x1, int y1, int x2, int y2);
};
// Function to draw box at the time of menu display
void sorting::box(int x1, int y1, int x2, int y2)
{
for (int col = x1; col < x2; col++)
{
gotoxy(col, y1);
cprintf("%c", 196);
gotoxy(col, y2);
cprintf("%c", 196);
}
for (int row = y1; row < y2; row++)
{
gotoxy(x1, row);
cprintf("%c", 179);
gotoxy(x2, row);
cprintf("%c", 179);
}
gotoxy(x1, y1);
cprintf("%c", 218);
gotoxy(x1, y2);
cprintf("%c", 192);
gotoxy(x2, y1);
cprintf("%c", 191);
gotoxy(x2, y2);
cprintf("%c", 217);
}
// This function is used to read the values in an array having n elements
void sorting::read()
{
int row = 7;
box(2, 1, 75, 24);
gotoxy(24, 2);
cout << "Enter how many elemnets = ";
cin >> n;
gotoxy(13, 4);
cout << " Input array ";
gotoxy(12, 5);
cout<<"****************";
for (i = 0; i < n; i++)
{
gotoxy(10, row);
cout << " Enter " << (i+1) << " element = ";
gotoxy(30, row);
cin >> array[i];
row++;
}
}
/* Function to read arrays for merge sort. */
void sorting::read_mer()
{
int row = 8;
box(2, 1, 75, 24);
gotoxy(20, 2);
cout << "Enter elements in First Array = ";
cin >> n;
gotoxy(20, 3);
cout << "Enter elemnets in second Array = ";
cin >> m;
gotoxy(24, 22);
cout << "Note:- Please enter sorted data \n";
gotoxy(17, 5);
cout<<"---------------------------------------";
gotoxy(6, 6);
cout << " IST Array";
gotoxy(5, 7);
cout << "************";
for (i = 0; i < n; i++)
{
gotoxy(6, row);
cout << (i+1) << " element = ";
gotoxy(18, row);
cin >> array[i];
row++;
}
row = 8;
gotoxy(25, 6);
cout << " IIND Array";
gotoxy(24, 7);
cout << "*************";
for (i = 0; i < m; i++)
{
gotoxy(25, row);
cout << (i+1) << " element = ";
gotoxy(39, row);
cin >> array1[i];
row++;
}
}
// This function is used to display the sorted elements
// from every sorting technique.
void sorting::display()
{
int row =7;
// box(2, 1, 75, 24);
gotoxy(50, 4);
cout << " Sorted array \n";
gotoxy(49, 5);
cout << "******************";
for (i = 0; i < n; i++)
{
gotoxy(50, row);
cout << (i+1) << " Element is = ";
gotoxy(65, row);
cout << array[i];
row++;
}
}
// This is the method of sorting by which the array element
// are interchanged within its relative values
void sorting::bub_sort()
{
int temp, j;
// Reads the array elements
read();
for (i = 0; i < n - 1; i++)
{
for (j = i+1; j < n; j++)
{
if (array[i] > array[j])
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
gotoxy(25, 18);
textbackground(MAGENTA);
textcolor(5+143);
cprintf(" RESULT OF BUBBLE SORT ");
textbackground(BLACK);
textcolor(2);
// Displays the arrays elements
display();
getch();
}
// This function is used to perform the quick sort
void sorting::Qui_sort()
{
// Inputs the array elements for quick sort
read();
// For quick sort
quick_sort(array, n, 0, n-1);
gotoxy(25, 18);
textbackground(MAGENTA);
textcolor(5+143);
cprintf(" RESULT OF QUICK SORT ");
textbackground(BLACK);
textcolor(2);
// Displays the sorted elements using the display() function
display();
getch();
}
// This function performs the partition changing in the array
// by the quick sort method
void sorting::quick_sort(int array[], int n, int l, int u)
{
int loc;
if (l < u)
{
partition(array, l, u, &loc);
quick_sort(array, n, l, loc-1);
quick_sort(array, n, loc+1, u);
}
}
// Function to perfrom the partition in the array for quick sort
void sorting::partition(int array[], int beg, int end, int *loc)
{
int first, last, flag, temp;
*loc = first = beg;
last = end;
flag = 0;
while (!flag)
{
while (array[last] >= array[*loc] && (*loc != last))
last --;
if (*loc == last)
flag = 1;
else
{
if (array[*loc] > array[last])
{
temp = array[*loc];
array[*loc] = array[last];
array[last] = temp;
*loc = last;
}
}
if (!flag)
{
while ((array[first] <= array[*loc]) && (*loc != first))
first++;
if (*loc == first)
flag = 1;
else
{
if (array[*loc] 0; i--)
{
temp = array[0];
array[0] = array[i];
array[i] = temp;
below_heap(array, 0, i-1);
}
gotoxy(28, 18);
textbackground(MAGENTA);
textcolor(5+143);
cprintf(" RESULT OF HEAP SORT ");
textbackground(BLACK);
textcolor(2);
// Displays the elemnts
display();
getch();
}
// Function which create a heap for heap sort
void sorting::heap(int array[], int n)
{
int counter;
// Bitwise right shift
counter = (n-1) >> 1;
for (i = counter; i >= 0; i--)
below_heap(array, i, n-1);
}
// Function is used to create lower heap in array for heap sort
void sorting::below_heap(int array[], int first, int last)
{
int count, l_child, r_child, max, temp;
if (first == 0)
l_child = 1;
else
// Bitwise left shift
l_child = first << 1;
r_child = l_child + 1;
if (l_child <= last)
{
max = array[l_child];
count = l_child;
if (r_child <= last)
{
if (array[r_child] > max)
{
max = array[r_child];
count = r_child;
}
}
if (array[first] < array[count])
{
temp = array[first];
array[first] = array[count];
array[count] = temp;
below_heap(array, count, last);
}
}
}
// Function is used to make selection sort in an array
void sorting::Sel_sort()
{
// Reads the array elements for selection sort
read();
int small;
int pos;
for (i = 0; i < n-1; i++)
{
small= array[i];
pos = i;
for(int j = i+1 ; j < n; j++)
{
if (array[j] < small)
{
small = array[j];
pos = j;
}
}
if ( pos != i)
{
int temp = array[i];
array[i] = array[pos];
array[pos] = temp;
}
}
gotoxy(28, 18);
textbackground(MAGENTA);
textcolor(5+143);
cprintf(" RESULT OF SELECTION SORT ");
textbackground(BLACK);
textcolor(2);
// Displays the sorted elements
display();
getch();
}
// Function is used to perform the shell sort in an array
void sorting::Shell_sort()
{
// Reads the elements for shell sort
read();
int temp;
for (int inc = n/2; inc>0; inc /= 2)
for (int i = inc; i < n; i++)
{
temp = array[i];
for (int j = i;j >= inc && temp < array[j-inc]; j -= inc)
array[j] = array[j-inc];
array[j] = temp;
}
gotoxy(20, 18);
textbackground(MAGENTA);
textcolor(5+143);
cprintf(" RESULT OF SHELL SORT");
textbackground(BLACK);
textcolor(2);
// displays the sorted elements
display();
getch();
}
// Function is used to perform insertion sort
void sorting::Ins_sort()
{
int temp;
read();
for (int i = 1; i < n; i++)
{
temp = array[i];
for (int j = i; temp < array[j-1]; j--)
array[j] = array[j-1];
array[j] = temp;
}
gotoxy(28, 18);
textbackground(MAGENTA);
textcolor(5+143);
cprintf(" RESULT OF INSERTION SORT ");
textbackground(BLACK);
textcolor(2);
// Displays the sorted elements
display();
getch();
}
// Function is used to perfrom merge sort in two arrays
void sorting::Mer_sort()
{
int row = 8;
// Reads the elements in different arrays
read_mer();
i = j = 0;
int k = 0;
while ((i < n) && (j < m))
{
if (array[i] < array1[j])
{
final[k] = array[i];
k = k + 1;
i = i + 1;
}
else
{
final[k] = array1[j];
k = k + 1;
j = j + 1;
}
}
while (i < n)
{
final[k] = array[i];
k = k + 1;
i = i + 1;
}
while (j < m)
{
final[k] = array1[j];
k = k + 1;
j = j + 1;
}
gotoxy(28, 18);
textbackground(MAGENTA);
textcolor(5+143);
cprintf(" RESULT OF MERGE SORT");
textbackground(BLACK);
textcolor(2);
gotoxy(50, 6);
cout << " Sorted array \n";
gotoxy(49, 7);
cout << "******************";
int t = m + n;
for (i = 0; i < t; i++)
{
gotoxy(50, row);
cout << (i+1) << " Element is = ";
gotoxy(65, row);
cout << final[i];
row++;
}
getch();
}
typedef char option[15];
char menu();
void grap_screen();
void end();
// MAIN PROGRAM
void main()
{
char choice;
sorting sort;
// To display the first screen of sort techniques
// grap_screen();
do
{
choice = menu();
clrscr();
switch (choice)
{
case '1':
sort.bub_sort();
break;
case '2':
sort.Heap_sort();
break;
case '3':
sort.Sel_sort();
break;
case '4':
sort.Ins_sort();
break;
case '5':
sort.Qui_sort();
break;
case '6':
sort.Mer_sort();
break;
case '7':
sort.Shell_sort();
break;
default :
end();
exit(0);
}
} while (choice != 0);
}
// Function used to do screening
void normalvideo(int x, int y, char *str)
{
gotoxy(x, y);
cprintf("%s", str);
}
// Function to reverse the video
void reversevideo(int x, int y, char *str)
{
textcolor(RED);
textbackground(WHITE);
gotoxy(x, y);
cprintf("%s", str);
textcolor(GREEN);
textbackground(BLACK);
}
// Function to display the main menu
char menu()
{
clrscr();
int i, done;
sorting sort;
option a[]=
{
" Bubble-Sort",
" Heap-sort ",
"Selection-Sort",
"Insertion-Sort",
" Quick-sort",
" Merge-sort",
" Shell_sort",
" Quit "
};
clrscr();
sort.box(20, 6, 65, 20);
sort.box(18, 4, 67, 22);
textcolor(5+143);
gotoxy(30, 5);
textbackground(WHITE);
cprintf("S O R T I N G - M E N U");
textbackground(BLACK);
textcolor(22);
for (i = 1; i < 8; i++)
normalvideo(32, i+8, a[i]);
reversevideo(32, 8, a[0]);
reversevideo(32, 8, a[0]);
i = done = 0;
_setcursortype(_NOCURSOR);
do
{
int key = getch();
switch (key)
{
case 00:
key = getch();
switch (key)
{
case 72:
normalvideo(32, i+8, a[i]);
i--;
if (i == -1)
i = 7;
reversevideo(32, i+8, a[i]);
break;
case 80:
normalvideo(32, i+8, a[i]);
i++;
if (i == 8)
i = 0;
reversevideo(32, i+8, a[i]);
break;
}
break;
case 13:
done = 1;
}
} while (!done);
_setcursortype(_NOCURSOR);
return(i+49);
}
// Function to display the front screen of sorting technique
void grap_screen()
{
int driver,mode;
driver = DETECT;
initgraph(&driver, &mode,"c:\tc\big");
setbkcolor(10);
setcolor(5); //set the text color
//set default font,horizontal direction,size of text
settextstyle(0, 0, 7);
outtextxy(50, 100, "Sorting");
outtextxy(50, 300, "Techniques");
delay(2000);
closegraph();
initgraph(&driver, &mode, "c:\tc\big");
setbkcolor(10);
setcolor(1); //set background color to blude
settextstyle(0, 0, 7);
outtextxy(50, 100, "DEVELOPED");
outtextxy(50, 300, " BY ");
delay(2000);
closegraph();
initgraph(&driver, &mode, "c:\tc\bin");
setbkcolor(10);
setcolor(4); //set background color to green
settextstyle(0, 0, 5);
outtextxy(30, 100, "Author " );
outtextxy(120, 200, " & ");
outtextxy(200, 300, "Her Team");
delay(2000);
closegraph();
}
//FUNCTION FOR ANIMATED END.
void end()
{
textmode(1);
for(int ai=0,aj=0, ak=34,al=33;ai<10,aj<17,ak>10,al>17;ai++,aj++,ak--,al--)
{
clrscr();
gotoxy(ai-1, 8);
textbackground(4);
textcolor(15);
cout << " Thanks ";
gotoxy(aj, 16);
cout << " This";
gotoxy(ak-4, 12);
cout << " For using";
gotoxy(al-2, 20);
cout << " Project";
delay(50);
}
//end of for loop
gotoxy(9, 9);
cout << " **********************";
gotoxy(9, 13);
cout << " **********************";
gotoxy(9, 17);
cout << " **********************";
gotoxy(12, 21);
cout << " ***************";
delay(2000);
textmode(2);
textbackground(0);
textcolor(5);
} // end of function
Tags: C++ Programming, Searching, Sorting, Source Code
There are No Comments to this post. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response or TrackBack from your own site.
