Write a program that generates an array of N positive integers randomly. Allow t
ID: 3678516 • Letter: W
Question
Write a program that generates an array of N positive integers randomly. Allow the user to enter any integer bigger than 0. Then sort them using Insertion Sort. The algorithm is as follows (this is pseudo-code so it isn't real Java code): for i 1 to length(Array) - 1 j i while j > 0 and Array[j-1] > Array[j] swap Array[j] and Array[j-1] j j - 1 end while end for
Requirements: You need the following methods. Call these from main: int[] createRandomArray(int n): Create an array of int of n size. Don't worry about duplicates. Then use a for loop to create n random numbers to store in the array. The numbers should be chosen in a range from 1 to 2 x n. void sort(int array[]): Pass in random array and sort the numbers in ascending order. You don't need to pass back the array as Insertion sort works on the array. Swaping elements in the array can be done in a separate method but this is optional. void printArray(int array[]): Print out entire array.
Explanation / Answer
#include <stdio.h>
#include <math.h>
/* Function to sort an array using insertion sort*/
void Sort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
// A utility function ot print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf(" ");
}
/* Driver program to test insertion sort */
int main()
{
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
Sort(arr, n);
printArray(arr, n);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.