1. Using C/C++, define two integer arrays; each has 30 integers within [0, 999].
ID: 3555771 • Letter: 1
Question
1. Using C/C++, define two integer arrays; each has 30 integers within [0, 999]. Use loop
and rand() to assign random integers to the arrays; then implement Selection and
Insertion sort algorithms to sort the two arrays in ascending order, respectively (i.e.
using selection to sort the 1
st
, and insertion to sort the 2
nd
. For each array, print all
array elements after sorting to verify the results.
2. Given a set of integer numbers as int A[ ] = { 12, 6, 51, 4, 3, 7, 19, 8, 0, 21}, please
write down the divide and conquer procedure of quick sort (step by step), include all
left and right positions adjustment, and overwriting.
3. Using C/C++, define an integer array with 100 integers and assign random numbers,
implement Quick Sort algorithm to sort and output the result.
Explanation / Answer
1. <link>http://ideone.com/tiibYq</link>
<code>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <ctime>
using namespace std;
void selection_sort(int arr[], int n) {
for(int i=0; i<n-1; i++) {
int min_idx = i;
for(int j=i+1; j<n; j++) {
if(arr[min_idx] > arr[j]) {
min_idx = j;
}
}
if(min_idx != i) {
swap(arr[i], arr[min_idx]);
}
}
cout << " Selection sort ascending order ";
for(int i=0; i<n; i++) {
cout << arr[i] << " ";
}
}
void insertion_sort(int arr[], int n) {
for(int i=1; i<n; i++) {
int tmp = arr[i];
int j = i-1;
while(j >= 0 && arr[j] > tmp) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = tmp;
}
cout << " Selection sort ascending ";
for(int i=0; i<n; i++) {
cout << arr[i] << " ";
}
}
int main(int argc, char **argv) {
int A[30], B[30];
srand(time(NULL));
for(int i=0; i<30; i++) {
A[i] = rand() % 1000;
B[i] = rand() % 1000;
}
selection_sort(A, 30);
cout << endl;
insertion_sort(B, 30);
return 0;
}
</code>
2. <link>http://ideone.com/KzTK1W</link>
<code>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <ctime>
using namespace std;
int pivot(int* arr, int first, int last) {
int p = first;
int _pivot = arr[first];
for(int i=first+1; i<=last; i++) {
if(arr[i] <= _pivot) {
p++;
swap(arr[i], arr[p]);
}
}
swap(arr[p], arr[first]);
return p;
}
void quick_sort_work(int* arr, int first, int last) {
int _pivot;
if(first < last) {
_pivot = pivot(arr, first, last);
quick_sort_work(arr, first, _pivot-1);
quick_sort_work(arr, _pivot+1, last);
}
}
void quick_sort(int* arr, int n) {
quick_sort_work(arr, 0, n-1);
cout << " Quick sort ascending ";
for(int i=0; i<n; i++) {
cout << arr[i] << " ";
}
}
int main(int argc, char **argv) {
int A[ ] = {12, 6, 51, 4, 3, 7, 19, 8, 0, 21};
quick_sort(A, 10);
return 0;
}
</code>
3. <link>http://ideone.com/K3oVM6</link>
<code>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <ctime>
using namespace std;
int pivot(int* arr, int first, int last) {
int p = first;
int _pivot = arr[first];
for(int i=first+1; i<=last; i++) {
if(arr[i] <= _pivot) {
p++;
swap(arr[i], arr[p]);
}
}
swap(arr[p], arr[first]);
return p;
}
void quick_sort_work(int* arr, int first, int last) {
int _pivot;
if(first < last) {
_pivot = pivot(arr, first, last);
quick_sort_work(arr, first, _pivot-1);
quick_sort_work(arr, _pivot+1, last);
}
}
void quick_sort(int* arr, int n) {
quick_sort_work(arr, 0, n-1);
cout << " Quick sort ascending ";
for(int i=0; i<n; i++) {
cout << arr[i] << " ";
}
}
int main(int argc, char **argv) {
int A[100];
srand(time(NULL));
for(int i=0; i<100; i++) {
A[i] = rand() % 1000;
}
quick_sort(A, 100);
return 0;
}
</code>
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.