Homework SourseC Searching Sorting 5 Sort the following list using the sel
C++ Searching & Sorting
5. Sort the following list using the selection sort algorithm. Show the list after each iteration of the outerforloop.
36, 55, 17, 35, 63, 85, 12, 48, 3, 66
6. Consider the following list: 5, 18, 21, 10, 55, 20
The first three keys are in order. To move 10 to its proper position using the insertion sort as described in this chapter, exactly how many key comparisons are executed?
7. Consider the following list: 7, 28, 31, 40, 5, 20
The first four keys are in order. To move 5 to its proper position using the insertion sort as described in this chapter, exactly how many key comparisons are executed?
8. Consider the following list: 28, 18, 21, 10, 25, 30, 12, 71, 32, 58, 15
This list is to be sorted using the insertion sort algorithm. Show the resulting list after six
passes of the sorting phase – that is, after six iterations of the for loop.
9. Perform the insertion sort algorithm using the following list of keys: 18, 8, 11, 9, 15, 20, 32, 61, 22, 48, 75, 83, 35, 3
Show the list after each iteration. Exactly how many key comparisons are executed to sort this list using insertion sort?
10. a. The performance of bubble sort can be improved if we stop the sorting process as soon as we find that in an iteration, no swapping of elements takes place. Write a function that implements bubble sort algorithm using this fact.
b. Using the algorithm that you designed in part (a), find the number of iterations that are needed to sort the list: 65, 14, 52, 43, 75, 25, 80, 90, 95.
11. Suppose that L is a sorted list of 4096 elements. What is the maximum number of comparisons made by binary search to determine whether an item is in L?
12. Suppose that the elements of a list are in descending order, and they need to be put in ascending order. Write a C++ function that takes as input an array of items in descending order and the number of elements in the array. The function must not incorporate any sorting algorithms, that is, no item comparisons should take place.
Solution
# include <iostream.h>
# include <conio.h>
# include <iomanip.h>
#include <stdlib.h>
#include <graphics.h>
#include <stdio.h>
#include <dos.h>
// 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 \ \";
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 \ \";
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] <array[first])
{
temp = array[*loc];
array[*loc] = array[first];
array[first] = temp;
*loc = first;
}
}
}
}
}
// Function is used to perform the heap sort technique
void sorting::Heap_sort()
{
// Reads the elements in array
read();
int temp;
heap(array, n);
for (i = n-1; i > 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 \ \";
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);
}
