Question

In: Computer Science

Compare radixSort to bubbleSort, SelectionSort, and InsertionSort Compare quickSort to bubbleSort, SelectionSort, and InsertionSort

Compare radixSort to bubbleSort, SelectionSort, and InsertionSort

Compare quickSort to bubbleSort, SelectionSort, and InsertionSort

Solutions

Expert Solution

Answer 1:

Title

Radix Sort

Bubble Sort

Selection Sort

Insertion sort

Definition

Radix sort is a sorting technique that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order.

Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order. The order can be ascending or descending.

Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration.

Example

Let the initial array be [121, 432, 564, 23, 1, 45, 788]

Step 1: [121, 1, 432, 23, 564, 45, 788]

Step 2: [1, 121, 23, 432, 45, 564, 788]

Step 3: [1, 23, 45, 121, 432, 564, 788]

Let the initial array be [-2, 45, 0, 11, -9]

Step 1: [-2, 0, 11, -9, 45]

Step 2: [-2, 0, -9, 11, 45]

Step 3: [-2, -9, 0, 11, 45]

Step 4: [-9, -2, 0, 11, 45]

Let the initial array be [20, 12, 10, 15, 2]

Step 1: [2, 12, 10, 15, 20]

Step 2: [2, 10, 12, 15, 20]

Step 3: [2, 10, 12, 15, 20]

Step 4: [2, 10, 12, 15, 20]

Let the initial array be [9, 5, 1, 4, 3]

Step 1: [5, 9, 1, 4, 3]

Step 2: [1, 5, 9, 4, 3]

Step 3: [1, 4, 5, 9, 3]

Step 4: [1, 3, 4, 5, 9]

Time complexity

Best case : O(nk)

Average Case: O(nk)

Worst case: O(nk)

Where k is maximum digit

Best case : O(n2)

Average Case: O(n2)

Worst case: O(n2)

Best case : O(n2)

Average Case: O(n2)

Worst case: O(n2)

Best case : O(n)

Average Case: O(n2)

Worst case: O(n2)

Space complexity

O(n)

O(1)

O(1)

O(1)

Applications

Radix sort is implemented in

  • DC3 algorithm while making a suffix array.
  • Places where there are numbers in large ranges.

Bubble sort is used in the following cases where

  • The complexity of the code does not matter.
  • A short code is preferred.

The selection sort is used when:

  • a small list is to be sorted
  • cost of swapping does not matter
  • checking of all the elements is compulsory
  • cost of writing to a memory matters

The insertion sort is used when:

  • the array is has a small number of elements
  • there are only a few elements left to be sorted

Answer 2:

Title

Quick Sort

Bubble Sort

Selection Sort

Insertion sort

Definition

Quicksort is an algorithm based on divide and conquer approach in which the array is split into subarrays and these sub-arrays are recursively called to sort the elements.

Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order. The order can be ascending or descending.

Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration.

Example

Let the initial array be [8, 7, 6, 1, 0, 9, 2]

Step 1: [1, 7, 6, 8, 0, 9, 2]

Step 2: [1, 0, 6, 8, 7, 9, 2]

Step 3: [1, 0, 2, 8, 7, 9, 6]

Step 4: [0, 1, 2, 8, 7, 9, 6]

Step 5: [0, 1, 2, 6, 7, 9, 8]

Step 5: [0, 1, 2, 6, 7, 8, 9]

Let the initial array be [-2, 45, 0, 11, -9]

Step 1: [-2, 0, 11, -9, 45]

Step 2: [-2, 0, -9, 11, 45]

Step 3: [-2, -9, 0, 11, 45]

Step 4: [-9, -2, 0, 11, 45]

Let the initial array be [20, 12, 10, 15, 2]

Step 1: [2, 12, 10, 15, 20]

Step 2: [2, 10, 12, 15, 20]

Step 3: [2, 10, 12, 15, 20]

Step 4: [2, 10, 12, 15, 20]

Let the initial array be [9, 5, 1, 4, 3]

Step 1: [5, 9, 1, 4, 3]

Step 2: [1, 5, 9, 4, 3]

Step 3: [1, 4, 5, 9, 3]

Step 4: [1, 3, 4, 5, 9]

Time complexity

Best case : O(log n)

Average Case:O(log n)

Worst case: O(n2)

Best case : O(n2)

Average Case: O(n2)

Worst case: O(n2)

Best case : O(n2)

Average Case: O(n2)

Worst case: O(n2)

Best case : O(n)

Average Case: O(n2)

Worst case: O(n2)

Space complexity

O(log n)

O(1)

O(1)

O(1)

Applications

Quicksort is implemented when

  • the programming language is good for recursion
  • time complexity matters
  • space complexity matters

Bubble sort is used in the following cases where

  • The complexity of the code does not matter.
  • A short code is preferred.

The selection sort is used when:

  • a small list is to be sorted
  • cost of swapping does not matter
  • checking of all the elements is compulsory
  • cost of writing to a memory matters

The insertion sort is used when:

  • the array is has a small number of elements
  • there are only a few elements left to be sorted

Related Solutions

Using this BubbleSort implementation in Java: public class BubbleSort<T extends Comparable<T>> {    private static <T...
Using this BubbleSort implementation in Java: public class BubbleSort<T extends Comparable<T>> {    private static <T extends Comparable<T>>    void swap(T[] data, int index1, int index2)    {       T temp = data[index1];       data[index1] = data[index2];       data[index2] = temp;    }    public void sort(T[] data)    {       int position, scan;       for (position = data.length - 1; position >= 0; position--)       {          for (scan = 0; scan <= position - 1; scan++)          {...
quicksort for 3,9,2,7,4,10,19
quicksort for 3,9,2,7,4,10,19
This is my code for an array using the bubblesort in the function outside of main....
This is my code for an array using the bubblesort in the function outside of main. My bubblesort is not working correctly , and I was told i'm missing a +j instead of +i in the function for void sorter.Can someone please help me with making my sorter work properly? everything else is fine and runs great. Thank you #include <stdio.h> #include <stdlib.h> #include <time.h> void printer(int *ptr, int length); void randomFill(int *ptr, int length); void sorter(int *ptr, int length);...
Develop the code for this sort algorithm: Shaker shakerSort is a variation of the bubbleSort where...
Develop the code for this sort algorithm: Shaker shakerSort is a variation of the bubbleSort where we alternately go up and then down switching out-of-order pairs until done. In it have code that counts the number of moves and number of compares.
Exercises a - b refer to the recursive algorithm SelectionSort (a.) In one part of algorithm...
Exercises a - b refer to the recursive algorithm SelectionSort (a.) In one part of algorithm SelectionSort, the index of the maximum item in a list must be found. This requires comparisons between list elements. In an n-element (unsorted) list, how many such comparisons are needed in the worst case to find the maximum element? How many such comparisons are needed in the average case? (b.) Defining the basic operation as the comparison of list elements and ignoring the amount...
Write a version of the selection sort algorithm in a function called selectionSort that can be...
Write a version of the selection sort algorithm in a function called selectionSort that can be used to sort a string vector object. Also, write a program to test your algorithm. The program should prompt the user for a series of names. The string zzz should end the input stream. Output the sorted list to the console. *Need answer in C++*
JAVA Start with the SelectionSort class in the zip file attached to this item. Keep the...
JAVA Start with the SelectionSort class in the zip file attached to this item. Keep the name SelectionSort, and add a main method to it. Modify the selectionSort method to have two counters, one for the number of comparisons, and one for the number of data swaps. Each time two data elements are compared (regardless of whether the items are in the correct order—we're interested in that a comparison is being done at all), increment the comparison counter. Each time...
quicksort the array step by step 63,19,32,11,87,3,87,24,48,39
quicksort the array step by step 63,19,32,11,87,3,87,24,48,39
Show the contents of the array after the fourth iteration of selectionSort Your answer should be...
Show the contents of the array after the fourth iteration of selectionSort Your answer should be 4 lines The array values horizontally for iteration 1 The array values horizontally for iteration 2 The array values horizontally for iteration 3 The array values horizontally for iteration 4
Show that the worst case of the Quicksort is Ω(n2)
Show that the worst case of the Quicksort is Ω(n2)
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT