ZuoTi.Pro
Question

Selection Sort is a common algorithm to sort the elements of an array. First, it scans...

Selection Sort is a common algorithm to sort the elements of an array. First, it scans the elements of the array to find the smallest value and places it at index 0, thus creating a sorted “subarray” of size 1 that contains the smallest value. Then it scans the remaining unsorted values for the new smallest value and places it at index 1, creating a sorted subarray of size 2 that contains the 2 smallest values. It continues in this way until the sorted subarray grows to contain all of the array elements, and therefore the entire array is sorted. Based on this description, what is the best big O estimate for Selection Sort? (Try to think about this for a bit before looking up the solution)

O(n)

O(log n)

O(n log n)

O(n2)
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1


d)

O(n2)

each iteration for finding smallest number taken O(n) complexity.

since this is done n times.

total time complexity = n*O(n) = O(n2)

0 0
Add a comment
Know the answer?
Add Answer to:
Selection Sort is a common algorithm to sort the elements of an array. First, it scans...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Question 5 (10 Points) Write a well-documented, Python program, hmwk305.py that implements the Selection-Sort algorithm. Selection-Sort...

    Question 5 (10 Points) Write a well-documented, Python program, hmwk305.py that implements the Selection-Sort algorithm. Selection-Sort segments the list into sorted and unsorted elements. The algorithm continues to remove the smallest element of the unsorted list and adds it to the sorted segment. Implement the algorithm that accepts an unsorted list and returns a sorted one - in ascending order. 5 3 8 Initial List 4 6 18 4 6 Minimum Swaps Position: Sorted List Length 1 Minimum Swaps Position:...

  • please help with python Write a well-documented, Python program, hmwk305.py that implements the Selection-Sort algorithm. Selection...

    please help with python Write a well-documented, Python program, hmwk305.py that implements the Selection-Sort algorithm. Selection Sort segments the list into sorted and unsorted elements. The algorithm continues to remove the smallest element of the unsorted list and adds it to the sorted segment. Implement the algorithm that accepts an unsorted list and returns a sorted one - in ascending order. 5 3 8 4 6 Initial List Minimum Swaps Position: Sorted List Length 1 Minimum Swaps Position: Sorted List...

  • Implement in C SharpCreate a new algorithm based on the algorithm, selection sort. The new algorithm...

    Implement in C SharpCreate a new algorithm based on the algorithm, selection sort. The new algorithm should be able to sort an array like this: Input: an array that has n elements, and the values of its elements are assigned randomly, for example: Index 0 1 2 3 4 5 value 7 3 6 2 1 5 Output: an array - its first n/2 elements are sorted in ascending order and its second n/2 elements sorted in descending order. That...

  • 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. E...

    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...

  • Sorting Sort the following array using the quick sort algorithm: (4 Marks) a. 12 26 8...

    Sorting Sort the following array using the quick sort algorithm: (4 Marks) a. 12 26 8 9 7 0 4 Pivot selection is defined to be the first element of each sub-list. Show the array before and after each quicksort round (when the array is partitioned after placing the pivot at its correct position). Also, clearly highlight the pivot in each partition b. Consider an unsorted array of integers of size n. Write a Java program to arrange the array...

  • //CODE 16-02.cpp //Demonstrates a template function that implements //a generic version of the selection sort algorithm....

    //CODE 16-02.cpp //Demonstrates a template function that implements //a generic version of the selection sort algorithm. #include <iostream> using std::cout; using std::endl; template<class T> void sort(T a[], int numberUsed); //Precondition: numberUsed <= declared size of the array a. //The array elements a[0] through a[numberUsed - 1] have values. //The assignment and < operator work for values of type T. //Postcondition: The values of a[0] through a[numberUsed - 1] have //been rearranged so that a[0] <= a[1] <=... <= a[numberUsed -...

  • Show the execution of the selection sort algorithm on the following array. Hint: The yellow or...

    Show the execution of the selection sort algorithm on the following array. Hint: The yellow or shaded squares should be the remaining unsorted values. Pass # 0 1 2 3 4 5 6 7 0 16 11 21 32 41 20 3 9 1 2 3 4 5 6 7 Show the execution of the insertion sort algorithm on the following array. Hint: The yellow or shaded squares should be the remaining unsorted values. Pass # 0 1 2 3...

  • please check my answers if it wrong answer me a) (25 points) Suppose that you are...

    please check my answers if it wrong answer me a) (25 points) Suppose that you are asked to analyze the performance. Algorithms operate on 1D array of size nor 2D a of the algorithms below, write down the Big O or order of grow terms of n. If the algorithm cannot be applied to the array, write 0(1), O(log n), O(n), O(n logn), 90), O(n"), O(n!). The will only be given for reasonable Big O answers. & algorithms for their...

  • Assume that you are sorting an array of 8 elements with quick sort. You just finished...

    Assume that you are sorting an array of 8 elements with quick sort. You just finished the first pass and the array looks like below. Which statement is true for the pivot value? 4 8 12 16 18 20 22 24 QUICKSORT ALGORITHM Quicksort selects a specific value called a pivot and rearranges the array into two parts (called partioning). If the array is randomly ordered, it does not matter which element is the pivot. For simplicity, the first element...

  • I want to sort my array by pushing the findMax number to the end of the...

    I want to sort my array by pushing the findMax number to the end of the list with this idea The Idea of sort the arraylist: (assume that the arraylist has n elements)Search the n elements of the arraylist for the maximum value then put this maximum value at the last position of the arraylist. Hence at index n-1. Move all other elements forward. Search the first n- 1 elements of the arraylist for the maximum value then put this...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT