NOTE:
HERE WE DID THE PROGRAM WITH C++ LANGUAGE
HERE TWO PROGRAMS ARE SHOWN IN C++
FIRST ONE IS DONE WITH OpenMP AND SECOND ONE WITH CONVENTIONAL PROCESS.
HERE WE TOOK LARGE AMOUNT OF DATA THROUGH RANDOM WAY.
AFTER QUICK SORT , HERE THE SORTED OUTPUTS ARE NOT SHOWN. BUT DISPLAY FUNCTIONS ARE WRITTEN IN BOTH THE CODE AND THEY ARE IN COMMENT SECTION.
ACTUALLY OpenMP FUNCTION IS USED TO REPRESENT PARALLEL PROGRAMMING. SO IT CAN SAVE THE EXECUTION TIME BY FASTER PROCESSING.
HERE THE PROCESSING TIMES FOR BOTH WITH AND WITHOUT OpenMP FUNCTION ARE CALCULATED AND SHOWN HOW OpenMP IS FASTER PROCESS TO SORT DATA.
/* PROGRAM WITH OpenMP FUNCTION */
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
/* prototype of the function */
void quicksort(int *,int,int);
int partition(int *,int,int);
void sort_display(int *,int);
/* quicksort function defined */
void quicksort(int *a,int p,int r)
{
int u;
if(p < r)
{ /* pivot value stored at j */
u = partition(a,p,r);
quicksort(a,p,u-1);
quicksort(a,u+1,r);
}
}
/* partition function defined to generate pivot value */
int partition(int *a, int p, int r)
{
int i,j,t,k_val;
k_val=a[p];
i=p+1;
j=r;
while(1)
{
while(i<r &&
k_val>=a[i])
{
i++;
}
while(k_val<a[j])
{
j--;
}
if(i<j)
{
t=a[i];
a[i]=
a[j];
a[j]= t;
}
else
{
t=a[p];
a[p]=a[j];
a[j]=t;
return j;
}
}
}
/* display in sorted form */
void sort_display(int *a,int n)
{
int i;
cout<<endl<<"Sorted array is:"<<endl;
for(i=0;i<n;i++)
{
cout<<" " <<a[i];
}
}
/* main function with OpenMP function */
int main()
{
int i,j,start_time,stop_time,N;
int a[500000];
cout<<endl<<"How many elements:";
cin>>N;
/* start time of the program */
start_time=clock();
/* taking random values */
for(i=0;i<N;i++)
{
a[i]=rand()%N;
}
/* returning the pivot element of array */
j = partition(a,0,N-1);
#pragma openMP parallel sections //
use of openMP
{
#pragma openMP
section
{
/* openMP is
used to quick sort left part of array with thread 1 */
quicksort(a,0, j - 1);
}
#pragma openMP
section // use of openMP
{
/* openmp is
used to quick sort right part of array with thread 2 */
quicksort(a, j + 1,
N-1);
}
}
/* finish time of the sorting */
stop_time=clock();
// sort_display(a,N);
/* total sorting time required with openMP */
cout<<endl<<endl<<"Total Time taken
with OpenMP:"<<(double)(stop_time -
start_time)/CLOCKS_PER_SEC;
}
SCREEN SHOT
OUTPUT
/* PROGRAM WITHOUT OpenMP*/
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
/* prototype of the function */
void quicksort(int *,int,int);
int partition(int *,int,int);
void sort_display(int *,int);
void swap_value(int &,int &);
/* swap_value function defined to swap values for ascending
order */
void swap_value(int* a,int* b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
/* partition function defined to generate pivot value */
int partition(int *a,int p,int r)
{
int pv_val,i,j;
pv_val=a[r];
i=p-1;
for(j=p;j<=r-1;j++)
{
if(a[j]<pv_val)
{
i++;
/* call by
reference */
swap_value(&a[i], &a[j]);
}
}
swap_value(&a[i+1],&a[r]);
return(i+1);
}
/* quicksort function defined */
void quicksort(int *a, int p, int r)
{
int u;
if(p<r)
{ /* pv_val value stored at j */
u=partition(a,p,r);
quicksort(a,p,u-1);
quicksort(a,u+1,r);
}
}
/* display in sorted form */
void sort_display(int *a,int n)
{
int i;
cout<<endl<<"Sorted array is:"<<endl;
for(i=0;i<n;i++)
{
cout<<" " <<a[i];
}
}
/* main function without OpenMP function */
int main()
{
int i,j,start_time,stop_time,N;
int a[500000];
cout<<endl<<"How many elements:";
cin>>N;
/* start time of the program */
start_time=clock();
/* taking random values */
for(int i=0;i<N;i++)
{
a[i]=rand()%N;//filling random
value
}
quicksort(a, 0, N - 1);
stop_time=clock();
//sort_display(a,N);
cout<<endl<<endl<<"Total Time taken
without OpenMP:"<<(double)(stop_time -
start_time)/CLOCKS_PER_SEC;
}
SCREEN SHOT
OUTPUT
OUTPUT EXPLANATION:
HERE 450000 INTEGER VALUES ARE TAKEN FOR SORTING
IN FIRST CASE FOR OpenMP FUNCTION THREAD1 AND THREAD2 SORT LEFT AND RIGHT PORTION OF ARRAY IN PARALLEL.
SO IT TAKES LESS TIME 0.136 AS COMPARED TO NON OpenMP PROGRAM OF SORTING TIME 0.183
NOTE:
HERE NON OpenMP PROGRAM IS INTRODUCED ONLY TO GENERATE BETTER UNDERSTANDING OF OpenMP FUNCTION.
Given an integer array a[ ] of N elements. Please write an OpenMP function to sort...
Given an array and a starting position write a function replaceFromN, that takes an integer array 'array', the size of the array size and a starting positions 'n' as parameters and replaces the elements starting from that index onward with the sequence 1,2,3,... The function returns nothing. void replaceFromN(int array[], int size, int n) For example, given array= {15,12,4,9,2,3} n =2 the function should modify array to be {15,12,1,2,3,4}
c++ please read all question edit the program to test different random sizes of the array and give me the time in a file will be like random size of the array and next to it the time it took for each size Im trying to do time analysis for Quick sort but i keep getting time = 0 also i want edit the program to test different random sizes of the array and give me the time in a...
1. Write a recursive function that computes the sum of all numbers from 1 to n, where n is given as parameter. Here is the method header: public static int sum (int n){...} 2. Write a recursive function that finds and returns the minimum value in an array, where the array and its size are given as parameters. Here is the method header: public static int minValue (int [] data, int size){...} 3. Write a recursive function that reverses the...
Sorting algorithm: quick sort Exercise One (20 marks) Given the following program body for implementing Quick sort, complete the program by writing code where required import java.util.Random; public class QuickSort public void quickSectlinti] A) QuickSort/A, O, A.length-1); private void guickSortlin Aiat low.int high) //Complete the code for the quicksort method (5 marks] private void swaplint[] a, int indexl, int index2) //Complete the code for the swap method [3 marks] private int setPivotlint low, int high) Random rand = new Random();...
Write a C++ function that prints an array, skipping over a number of elements. Use the following header: void printArraySkip(int array[], int elems, int skip) { } Where 'array' is an input array of 'elem' integer elements, and 'skip' is the number of elements to skip over. For example, if the function is called like this: int array[6] = { 5, 7, 11, 12, 18, 19 }; printArraySkip(array, 6, 2); The output would be: 11 19 in c++. Thanks
Modify the sorts (selection sort, insertion sort, bubble sort, quick sort, and merge sort) by adding code to each to tally the total number of comparisons and total execution time of each algorithm. Execute the sort algorithms against the same list, recording information for the total number of comparisons and total execution time for each algorithm. Try several different lists, including at least one that is already in sorted order. ---------------------------------------------------------------------------------------------------------------- /** * Sorting demonstrates sorting and searching on an...
Given a sorted (in ascending order) integer array nums of n elements and a target value, write a method to perform a binary search for a target value in nums. If target exists, then return its index, otherwise return -1. Analyze the running time, T(n). public int search(int[] nums, int target) { // YOUR CODE GOES HERE } // end search
JAVA Objectives: 1. Apply linear search algorithm 2. Apply select sort algorithm 3. Apply array iteration skill Problem description: Write the following eight methods and write a main function to test these methods // return the index of the first occurrence of key in arr // if key is not found in arra, return -1 public static int linearSearch(int arr[], int key) // sort the arr from least to largest by using select sort algorithm public stati void selectSort(int arr[])...
[5 marks] Using selection sort algorithm to sort the array int array[7]-5, 6, 2, 7, 9, 4, 3). Assuming we call the following function using statement selection sort (int array, 7); Please fill the table to show the changes of the array int_array after each iteration. The first column is filled. void selection_sort (int list[], int list_size) for (int i = 0; i < list size - 1; 1++) int current min = list[1]; int current_min_index-i for (int j -...
#include <assert.h> #include <stdio.h> #include <stdlib.h> // initialize_array is given an array "arr" of "n" elements. // It initializes the array by setting all elements to be "true" (any non-zero value). void initialize_array(int *arr, int n) { // TODO: Your code here. assert(0); } // mark_multiples is given an array "arr" of size n and a (prime) number "p" less than "n" // It assigns "false" (the zero value) to elements at array indexes 2*p, 3*p, 4*p,.., x*p (where x*p...