:: DATA STRUCTURE :: solve these problems according to data structure course. it

Question

:: DATA STRUCTURE ::

solve these problems according to data structure course.

its preferred to use JAVA language in coding.

2. Determine the worst-case complexity of the following program void transpose (int al llMAX SIZE] int ii, temp; for i 0; i MAX SIZE-1, i++) for J i 1; j MAX SIZE; j++) SWAP (a[i][jkalj][il,temp); 3. Please write down the code to do selection sort a) Analysis the worst-case complexity of the selection sort b) Write down the code to do the performance measurement of the selection sort

Explanation / Answer

public class SelectionSortExample {
public static void selectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
  
  
   // to find the index of the smallest number
   int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < arr[index]){
index = j;//searching for lowest index
}
}

//swaping of numbers
int smallerNumber = arr[index];   
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
  
public static void performanceMeasurement(int n)
{
   //
   //. Let's say that selection sort takes approximately n^2/10 seconds for n elements
   System.out.println(" for sorting "+n+" elements it takes "+n*n/10+"seconds");
  
}

public static void main(String a[]){
int[] arr1 = {9,14,3,2,43,11,58,22};
System.out.println("Before Selection Sort");
for(int i:arr1){
System.out.print(i+" ");
}
System.out.println();
  
selectionSort(arr1);//sorting array using selection sort

System.out.println("After Selection Sort");
for(int i:arr1){
System.out.print(i+" ");
}
performanceMeasurement(100);
performanceMeasurement(10000);
System.out.println("as you can see when n increases by factor of 10 elements ");
System.out.println("as you can see when time increases by factor of 100000 elements ");

System.out.println();
}
}

----------------------------------------------------------

analysis:

Selection sort loops over indices in the array; for each index, selection sort finds indexOfMinimum and swaps. If the length of the array is n, there are n indices in the array.

How many lines of code are executed by a single call to swap? In the usual implementation, it's three lines, so that each call to swap takes constant time. i.e O(1)

How many lines of code are executed to find indexOfMinimum? We have to account for the loop inside indexOfMinimum. How many times does this loop execute in a given call to indexOfMinimum? It depends on the size of the subarray that it's iterating over. If the subarray is the whole array (as it is on the first step), the loop body runs n times.

For example, let's say the whole array is of size 8 and think about how selection sort works.
In the first call of indexOfMinimum, it has to look at every value in the array, and so the loop body in indexOfMinimum runs 8 times.
In the second call of indexOfMinimum, it has to look at every value in the subarray from indices 1 to 7, and so the loop body in indexOfMinimum runs 7 times.
In the third call, it looks at the subarray from indices 2 to 7; the loop body runs 6 times.
In the fourth call, the subarray from indices 3 to 7; the loop body runs 5 times.
…
In the eighth and final call of indexOfMimimum, the loop body runs just 1 time.
If we total up the number of times the loop body of indexOfMinimum runs, we get 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 times.

i.e n^2/2+n/2

we take only n^2 and ignore rest since it is very small

0(n^2)

Adding up the running times for the we have (n^2)+O(1)=O(n^2) since we discard constant as it is negligible

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.