Intro class. no code to be written. Trace selection sort on the following array

Question

Intro class. no code to be written.

Trace selection sort on the following array of letters (sort into alphabetical order):

After each pass (outer loop iteration) of selection sort, show the contents of the array and the number of letter-to-letter comparisons performed on that pass (an exact number, not big-O).Trace insertion sort on the following array of letters (sort into alphabetical order):

After each pass (outer loop iteration) of insertion sort, show the contents of the array and the number of letter-to-letter comparisons performed on that pass (an exact number, not big-O).

Explanation / Answer

// C++ code
#include <iostream>
#include <string.h>
#include <cstring>
#include <vector>
#include <fstream>

using namespace std;

void swap(char *a, char *b)
{
char temp = *a;
*a = *b;
*b = temp;
}

void selectionSort(char array[], int n)
{
int min;

for (int i = 0; i < n-1; i++)
{
int count = 0;

min = i;
for (int j = i+1; j < n; j++)
{
count++;
if (array[j] < array[min])
min = j;
}
swap(&array[min], &array[i]);

cout << " Comparisons in paas " << (i+1) << ": " << count << endl;
cout << "Array: ";
for (int k = 0; k < n; ++k)
{
cout << array[k] << " ";
}
}
}

void insertionSort(char array[], int n)
{
int ky;
for (int i = 1; i < n; i++)
{
int count = 0;
ky = array[i];
int j = i-1;

while (j >= 0 && array[j] > ky)
{
count++;
array[j+1] = array[j];
j = j-1;
}
array[j+1] = ky;

cout << " Comparisons in paas " << i << ": " << count << endl;
cout << "Array: ";
for (int k = 0; k < n; ++k)
{
cout << array[k] << " ";
}
}
}

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

int main()
{
cout << "Selection sort ";
char array[] = {'X', 'A', 'T', 'B', 'Q', 'S', 'B'};
int n = 7;
selectionSort(array, n);
cout << " Sorted array: ";
display(array, n);

cout << " Insertion sort ";
char array1[] = {'X', 'A', 'T', 'B', 'Q', 'S', 'B'};
insertionSort(array1, n);
cout << " Sorted array: ";
display(array1, n);

return 0;
}

/*

output:

Selection sort

Comparisons in paas 1: 6
Array: A X T B Q S B
Comparisons in paas 2: 5
Array: A B T X Q S B
Comparisons in paas 3: 4
Array: A B B X Q S T
Comparisons in paas 4: 3
Array: A B B Q X S T
Comparisons in paas 5: 2
Array: A B B Q S X T
Comparisons in paas 6: 1
Array: A B B Q S T X
Sorted array: A B B Q S T X

Insertion sort

Comparisons in paas 1: 1
Array: A X T B Q S B
Comparisons in paas 2: 1
Array: A T X B Q S B
Comparisons in paas 3: 2
Array: A B T X Q S B
Comparisons in paas 4: 2
Array: A B Q T X S B
Comparisons in paas 5: 2
Array: A B Q S T X B
Comparisons in paas 6: 4
Array: A B B Q S T X
Sorted array: A B B Q S T X
*/

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.