C++ Help! Implement the findMin and sortArr functions in the provided code file.
ID: 3820542 • Letter: C
Question
C++ Help!
Implement the findMin and sortArr functions in the provided code file. findMin takes three arguments: the array as a, the size of the array as s, and the index that you should start searching at as from. This function should start by looking at the index from and go to the end of the array. Once it has determined what the index of the smallest value between from and s is, it should return that index. If the index provided for from is invalid (larger than or equal to s), return -1 instead. sortArr takes two arguments: the array as a, and the size of the array as s. Implement selection sort for this function. The selection sort algorithm divides the input list into two parts: the subarray of items already sorted, which is built up from left to right at the front (left) of the array, and the subarray of items remaining to be sorted that occupy the rest of the array. Initially, the sorted subarray is empty and the unsorted subarray is the entire input array. The algorithm proceeds by finding the smallest element in the unsorted subarray, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the subarray boundaries one element to the right. This algorithm performs directly on the array passed to the function. You will not need decided unsorted and sorted arrays since you can just use the array passed in to the function. NOTE: Wikipedia has a good animation of the process in the Selection Sort article. The printArr and swapVals functions have already been implemented. So has main. Make use of the swapVals function when implementing your selection sort.
**********Sample Output: Console (note: no user interaction needed)
Unsorted array:
8 38 25 4 47 47 38 36 3 33 2 19 16 30 5 47 16 38 13 1
Sorted Array:
1 2 3 4 5 8 13 16 16 19 25 30 33 36 38 38 38 47 47 47
Here's what I've got started:
Explanation / Answer
#include <iostream>
using namespace std;
void printArr(const int a[], int s);
void swapVals(int& v1, int& v2);
int findMin(const int a[], int s, int from);
void sortArr(int a[], int s);
int main()
{
const int s = 20;
int arr[s] = {8, 38, 25, 4, 47, 47, 38, 36, 3, 33, 2, 19, 16, 30, 5, 47, 16, 38, 13, 1};
cout << "Unsorted array: ";
printArr(arr, s);
cout << " ";
sortArr(arr, s);
cout << "Sorted Array: ";
printArr(arr, s);
cout << " ";
return 0;
}
int findMin(const int a[], int s, int from)
{
int min = a[from];
int minIndex = from;
for(int i=from; i<s; i++){
if(min > a[i]){
min = a[i];
minIndex = i;
}
}
return minIndex;
}
void sortArr(int a[], int s)
{
for (int i = 0; i < s; i++)
{
int index = i;
int min = findMin(a,s,i);
swapVals(a[i] , a[min]);
}
}
void swapVals(int& v1, int& v2)
{
int temp = v1;
v1 = v2;
v2 = temp;
}
void printArr(const int a[], int s)
{
for (int i=0; i<s; i++)
{
cout << a[i];
if (i != s-1)
cout << " ";
}
}
Outpu:
sh-4.2$ g++ -o main *.cpp
sh-4.2$ main
Unsorted array:
8 38 25 4 47 47 38 36 3 33 2 19 16 30 5 47 16 38 13 1
Sorted Array:
1 2 3 4 5 8 13 16 16 19 25 30 33 36 38 38 38 47 47 47
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.