data.txt 33 34 12 29 6 49 24 19 87 8 95 25 35 77 9 45 83 43 75 70 94 30 73 76 78

Question

data.txt

33
34
12
29
6
49
24
19
87
8
95
25
35
77
9
45
83
43
75
70
94
30
73
76
78
7
10
22
88
91
41
71
96
55
80
97
16
3
31
64
18
46
61
21
5
23
89
11
98
82
53
79
86
39
54
72
15
52
4
56
57
99
63
40
67
28
69
90
92
2
68
47
60
36
38
44
93
37
42
20
48
51
59
62
32
58
74
1
66
13
17
84
81
50
14
26
65
27
85

The link to the main.cpp file:
https://unr.instructure.com/courses/12160/files/731932/download?download_frd=1

Modified from Programming Problem 4 on Page 94 Implement the algorithm ksmall, discussed in Section 24,4, as a C++ function. Use the first value of the array as the pivot. Use the main file that tests the class with data from a text file Ga. Your code should work for any given file that has integers enumerated in a file (one value per line. Deliverables 1. Source code for your class 2. Updated main file 3. Test output of your code (ie.. the kth smallest value with given data file 2) 4. A log file of traces (i e. log.txt) showing pivot value and state of the array after the partitioning of each round main.cpp #include kiostream> #include

Explanation / Answer

As your link doesn't give me code for main I have used mine. Also you have not provided what pivot algo you needed. But I spent a lot of time figuring out you wanted a in place quick sort partition using first pivot element and I have used that.

Here is the code.

It would be more helpful if we have more details on question.

#include<iostream>
#include<climits>
#include <fstream>
using namespace std;

int size = 0;

int partition(int arr[], int l, int r);

// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around last element and get
// position of pivot element in sorted array
int pos = partition(arr, l, r);

// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return kthSmallest(arr, l, pos-1, k);

// Else recur for right subarray
return kthSmallest(arr, pos+1, r, k-pos+l-1);
}

// If k is more than number of elements in array
return INT_MAX;
}

void exchange(int& a, int& b)
{
int t;
t = a;
a = b;
b = t;
}

int partition(int a[], int first, int last)

// partitions the elements from first to last in
// the array t so that all the elements less than
// the first element are placed at the beginning
// of the array and all the elements greater than
// the first element are placed at the end of the
// array. The original element appears between the
// two partitions at the position indicated by
// pivindex.

{
int pivot;
int up,down;
pivot = a[first];
up = first;
down = last;
int pivIndex = 0;
int arr[last-first + 1];

int j = 0;
for (int i = first+1; i <= last; i++)
{
if(a[i] < pivot)
{
arr[j++] = a[i];
}
}
pivIndex = first + j;
arr[j++] = pivot;
for (int i = first+1; i <= last; i++)
{
if(a[i] > pivot)
{
arr[j++] = a[i];
}
}
cout << "Pivot: " << pivot << endl;
for(int i = 0; i < j; i++)
{
a[i+first] = arr[i];
}

cout << "[ ";
for(int i = 0; i < pivIndex; i++)
{
cout << a[i] << " ";
}
cout << "] [" << a[pivIndex] << "] [";
for(int i = pivIndex+1; i < size; i++)
{
cout << a[i] << " ";
}
cout <<"]" << endl;
return pivIndex;
}

// Driver program to test above methods
int main()
{
int arr[100];

ifstream file;

file.open("data.txt");
cout << "Ok ";
int n = 0;

string line;
while (file >> arr[n++]);
n = n-1;
size = n;
file.close();

int k = 6;
cout << "k = " << k <<endl;
cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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