Topics: intro to arrays, sorting algorithms Given the existence of an array call
ID: 3904587 • Letter: T
Question
Topics: intro to arrays, sorting algorithms Given the existence of an array called "list" declared as follows: intl list- (25,-45,88,3,10,-5,48,66,15,20,-24,100,16,-31,70,73; For each subproblem, assume we begin with the original array a) Show how the contents of the array would be reordered after 3 passes of b) Show how the contents of the array would be reordered after 3 passes of c) Show how the contents of the array would be reordered after 3 passes of the bubble sort the insertion sort the selection sortExplanation / Answer
ScreenShot
a) Show the contents of the array after 3rd iteration using buble sort
Bubble sort:-
In this algorithm each pair of adjacent elements compare if less then swap.so each round largest elements move into right.and smallest move into left.
public class SortArray {
public static void bubbleSort(int[] arr) {
//Iterate until array length
for (int i = 1; i<arr.length; ++i)
{
//arr[0] to length-1 elements compare and largest element goes to end and smallest elemnet comes to first
for (int j = 0; j<((arr.length)- i); ++j)
if (arr[j]>arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
//After each iteration check if it is 3rd then print values
if(i==3) {
System.out.println("Array after"+i+"th bubble sort");
for (int k = 0; k<arr.length; ++k)
System.out.print(" "+arr[k]);
}
}
}
//Test method
public static void main(String[] args) {
int[] list = { 25,-45,88,3,10,-5,48,66,15,20,-24,100,16,-31,17,7 };
bubbleSort(list);
}
}
Output
Array after3th bubble sort
-45 3 -5 10 25 15 20 -24 48 16 -31 17 7 66 88 100
--------------------------------------------------------
Insertion sort
Compare each element and smaller elements insert sublist to generate sorting
public class SortArray {
public static void insertionSort(int arr[])
{
int n = arr.length;
//Loop continue until the length of the array
for (int i=1; i<n; ++i)
{
//First elment set as key
int key = arr[i];
//Loop start from next element compare less than key then change key into that value otherwise continues to next element
int j = i-1;
while (j>=0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
if(i==3) {
System.out.println("Array after"+i+"th bubble sort");
for (int k = 0; k<arr.length; ++k)
System.out.print(" "+arr[k]);
}
}
}
//Test method
public static void main(String[] args) {
int[] list = { 25,-45,88,3,10,-5,48,66,15,20,-24,100,16,-31,17,7 };
insertionSort(list);
}
}
Output
Array after3th insertion sort
-45 3 25 88 10 -5 48 66 15 20 -24 100 16 -31 17 7
-------------------------------------------------------------------
c)Selection sort
Each iteration find minimum element and place it left .Then next iterartion starts from next element.
public class SortArray {
public static void selectionSort(int arr[])
{
int n=arr.length;
// One by one move boundary of unsorted subarray
for(int i=0;i<n;++i) {
for(int j=i+1;j<n;++j){
if(arr[i]>arr[j])
//compare each element with ith element change accordingly
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
//Third iteration result
if(i==3) {
System.out.println("Array after"+i+"th selection sort");
for (int k = 0; k<arr.length; ++k)
System.out.print(" "+arr[k]);
}
}
}
//Test method
public static void main(String[] args) {
int[] list = { 25,-45,88,3,10,-5,48,66,15,20,-24,100,16,-31,17,7 };
selectionSort(list);
}
}
Output
Array after3th selection sort
-45 -31 -24 -5 88 25 48 66 15 20 10 100 16 3 17 7
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.