Question

in python Generates 50,000 random numbers and puts them in an array. Sorts the numbers using...

in python

  1. Generates 50,000 random numbers and puts them in an array.
  2. Sorts the numbers using any sorting technique (Selection sort is fine, but you can try another one). This should take a few minutes to run.
  3. Ask the user for a number between 0 and 20,000,000 and search for it in your sorted array using a simple linear search. Is this a good idea?
  4. Ask the user for a number between 0 and 20,000,000 and search for it in your sorted array using a binary search.

Homework Answers

Answer #1
Linear search algorithms worst time complexity is of order N where N is the size of the array, while binary search algorithm worst time complexity is log(N), for higher number of N log(N) < N, which means time taken to find a number using binary search is far less than searching the element using linear search.

Note: binary search can only be done on sorted array, if the array is not sorted we have to do linear search only.

=========================
Below is the python code.
=========================
===============================================================================

import random


# Sorts the numbers using any sorting technique (Selection sort is fine, but you can try another one). This should take a few minutes to run.
def selection_sort(num_list):
    for i in range(len(num_list)):
        min_index = i
        for j in range(i + 1, len(num_list)):
            if num_list[min_index] > num_list[j]:
                min_index = j
        num_list[i], num_list[min_index] = num_list[min_index], num_list[i]


# Generates 50,000 random numbers and puts them in an array.
random_num_list = []
for _ in range(50000):
    random_num_list.append(random.randint(0, 20000000))
print('Random numbers generated..')
# sorting the numbers using selection sort
print('Sorting the random numbers..')
selection_sort(random_num_list)

print(random_num_list)

# Ask the user for a number between 0 and 20,000,000 and
# search for it in your sorted array using a simple linear search.
# Is this a good idea?
search_num = int(input('Enter a number between 0 and 20,000,000: '))

print('Searching a number using simple linear search on a sorted list....')
for i in range(len(random_num_list)):
    if random_num_list[i] == search_num:
        print('Number found at index: {}'.format(i))
        break
if not (i < len(random_num_list)):
    print('Number not found.')

print('Searching a number using binary search on a sorted list..')
search_num = int(input('Enter a number between 0 and 20,000,000: '))
left = 0
right = len(random_num_list)
flag=True
while left < right:
    mid = (right+left) // 2
    if random_num_list[mid] == search_num:
        print('Number found at index: {}'.format(mid))
        flag=False
        break
    elif random_num_list[mid] < search_num:
        left = mid + 1
    else:
        right = mid
if flag:
    print('Number not found.')

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
In JAVA Find the code for sorts in your language some where online. You will copy...
In JAVA Find the code for sorts in your language some where online. You will copy code from the internet (with citation!) and modify it to test. Make a random array of integers, then perform each search on them. LINEAR SEARCH Write a linear search method to find a number in the list. Call this before each of your sort methods. Include a comment explaining how Linear Search works, when to use it, when you cannot. BINARY SEARCH Write a...
Write a Java program that randomly generates an array of 500,000 integers between 0 and 499,999,...
Write a Java program that randomly generates an array of 500,000 integers between 0 and 499,999, and then prompts the user for a search key value. Estimate the execution time of invoking the linearSearch method in Listing A below. Sort the array and estimate the execution time of invoking the binarySearch method in Listing B below. You can use the following code template to obtain the execution time: long startTime = System.currentTimeMillis(); perform the task; long endTime = System.currentTimeMillis(); long...
Using C++, Python, or Java, write a program that: In this programming exercise you will perform...
Using C++, Python, or Java, write a program that: In this programming exercise you will perform an empirical analysis of the QuickSort algorithm to study the actual average case behavior and compare it to the mathematically predicted behavior. That is, you will write a program that counts the number of comparisons performed by QuickSort on an array of a given size. You will run the program on a large number of arrays of a certain size and determine the average...
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
Part 1: Benchmarking Sorting Algorithms The same task can take vastly different amounts of time, depending...
Part 1: Benchmarking Sorting Algorithms The same task can take vastly different amounts of time, depending on the algorithm that is used to perform the task. You are familiar with simple sorting algorithms such as insertion sort and selection sort. (See Section 7.4 in the textbook.) While these methods work fine for small arrays, for larger arrays they can take an unreasonable amount of time. The question is whether we can do any better. Java has some built-in sorting methods....
Write a code in c++ using linear insertion following the steps below. Comment your work. 1....
Write a code in c++ using linear insertion following the steps below. Comment your work. 1.    Ask the user for the name of a file containing data. If it does not exist, the program should display an error, then ask for a new file name. Entering an asterisk (*) as the first and only character on a line should terminate the program. 2.     You can use a statically-allocated one-dimensional array of doubles for this with length 100. You...
IN JAVA Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort: <-- (I need the...
IN JAVA Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort: <-- (I need the code to be written with these) I need Class river, Class CTRiver and Class Driver with comments so I can learn and better understand the code I also need a UML Diagram HELP Please! Class River describes river’s name and its length in miles. It provides accessor methods (getters) for both variables, toString() method that returns String representation of the river, and method isLong()...
Topics Arrays Accessing Arrays Description Write a C++ program that will display a number of statistics...
Topics Arrays Accessing Arrays Description Write a C++ program that will display a number of statistics relating to data supplied by the user. The program will ask the user to enter the number of items making up the data. It will then ask the user to enter data items one by one. It will store the data items in a double array. Then it will perform a number of statistical operations on the data. Finally, it will display a report...
Write a java program that creates an integer array with 50 random values, prompts the user...
Write a java program that creates an integer array with 50 random values, prompts the user to enter the index of an element in the array between 0 and 49, then displays the corresponding element value. If the specified index is out of bounds, display an error message (e.g. “Out of Bounds”) and ask the user to enter another index. Use a while loop that will keep prompting the user until a valid input is received. To handle invalid inputs,...
Create a program that generates a file of random numbers, and then prints them in neat...
Create a program that generates a file of random numbers, and then prints them in neat fashion to another file, and also saves to that file the average and standard deviation of those numbers. I) First, you would need to generate a file of random numbers that consists of N random numbers (100 < N < 1000). Each random digit should be a real number (type double) between 0 and 50. This file and its digits would now serve as...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT