1. Understand the algorithm being analysed. Your must briefly describe the algor
ID: 3731380 • Letter: 1
Question
1. Understand the algorithm being analysed. Your must briefly describe the algorithm.
2. Expain the algorithm’s predicted (theoretical) average-case efficiency with respect to its ‘basic operation’.
3. Explain clearly the choice of basic operation for the particular algorithm of interest.
4. Summarise the expected time efficiency of the algorithm with respect to the size of its input(s). This should be expressed as the algorithm’s predicted average-case efficiency and/or order of growth.
Algorithm NegBeforePos(A[0..n -1]) // Puts negative elements before positive (and zeros, if any) in an array //Input: Array A(0..n - 1] of real numbers //Output: Array A[0..n -1] in which all its negative elements precede nonnegative j do IiExplanation / Answer
1) the above algo segregate the negative and positive numbers in a array in way that the negative numbers will come before the positiive numbers
since there are two counter variable i and j
i starts from 0 and j starts from last element of the array
2) the average case efficiency is o(n/2) since we are iterating over the half of the array only
3) the basic operation used is the swapping of the elements if element at a[i] is a positive number that element wil be swapped with the a[j] element where the a[j] element is the negarive number
c# code
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rextester
{
class Program
{
static void NegBeforePos(int[] array, int size)
{
int val, j;
for (int k = 1; k<size; k++) {
val = array[k];
if (val > 0)
continue;
j = k-1;
while (j >= 0 && array[j] > 0) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = val;
}
}
static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
public static void Main(string[] args)
{
int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };
Console.Write(" Array Before: ");
printArray(arr, 9);
int n = arr.Length;
NegBeforePos(arr, n);
Console.Write(" Array After: ");
printArray(arr, n);
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.