1. Consider an algorithm called AbsurdSort . This algorithm will bring all the d
ID: 665958 • Letter: 1
Question
1. Consider an algorithm called AbsurdSort. This algorithm will bring all the data to be sorted into a large array in main memory. Then the array will randomly rearranged, and then tested to see if it is sorted. The process repeats until the array is sorted.
a. Is this algorithm an internal or external sort?
b. Is this algorithm stable? Explain.
2. The following ask you to demonstrate sorting methods. Use < and > to bracket sorted regions in the array.
a. Show, in the manner of figure 6.2, how selection sort would sort S O R T M E.
b. Show, in the manner of figure 6.3, how insertion sort would sort S O R T M E.
c. Show, in the manner of figure 6.4, how bubble sort would sort S O R T M E.
3. The following refer to inversions.
a. How many inversions are in S O R T M E?
b. Why does bubble sort perform better on a file with fewer inversions?
c. Why is selection sort’s performance not affected by the number of inversions?
4. The following refer to shellsort.
a. Explain how shellsort can improve the worst-case situations that plague bubble sort.
b. Explain why the shellsort increment sequence 1 2 4 8 16 ... is a poor choice that may lead to n2 behavior.
5. Short programming assignment. Implement the shellsort and use it to sort an array with data in reverse order. Use three different increment sequences and give the results.
6. The following refer to pointer and index sorting.
a. What is a pointer sort and what is its benefit for sorting large objects?
b. Suppose you have 1000 records on disk. Each record is 2000 bytes, but the key of each record is only 10 bytes. Explain how index sorting could be used to efficiently output the records in sorted order, and why this is more efficient than sorting all the records in main memory.
7. Show, in the manner of figure 6.17, how key-indexed counting would sort C A B B A D A B.
8. The following refer to performance under quicksort.
a. How many recursive calls will quicksort make in the worst case for a file of N items?
b. Why does increasing the number of duplicate values in the file to be sorted decrease quicksort performance?
c. List and explain the modifications to the basic quicksort algorithm that can mitigate the problem of duplicate values.
d. What is benefit of median-of-three partitioning?
9. Short programming assignment. Test the recursive and non-recursive versions of quicksort on identical sets of random data and record the results
Explanation / Answer
1. Consider an algorithm called AbsurdSort. This algorithm will bring all the data to be sorted into a large array in main memory. Then the array will randomly re arranged, and then tested to see if it is sorted. The process repeats until the array is sorted.
2. The following ask you to demonstrate sorting methods. Use < and > to bracket sorted regions in the array.
The figures 6.2, 6.3 and 6.4 are not given in the Chegg question. Hence I had to assume an array for S O R T M E.
Let S O R T M E = {5, 12, 4, 3, 7, 10, 13, 2, 16 , 20, 1,6,9,11, 14, 15, 17}
cout << endl << “Array before sorting: “ ;
for (int i = 0; i<n; i++) cout << “ “ << CheggArray[i];
for(int x=0; x<n; x++) {
int MinimumElementsIndex = x; // stores the index of smallest
for(int y=x; y<n; y++) {
if(CheggArray[MinimumElementsIndex]>CheggArray[y]) {
// if any other array element is smaller, then store
// that element in MinimumElement’sIndex
MinimumElementsIndex = y;
} // end if
} // end for y=x to n
int temp = CheggArray[x]; // a 3 point swap using temp location
CheggArray[x] = CheggArray[MinimumElementsIndex];
CheggArray[MinimumElementsIndex] = temp;
}// end for x = 0 to n
cout << endl << “Array after sorting by selection sort: “ ;
for ( i = 0; i<n; i++) cout << “ “ << CheggArray[i];
Sample output:
Array before Sorting: 5, 12, 4, 3, 7, 10, 13, 2, 16 , 20, 1,6,9,11, 14, 15, 17
Array after sorting by selection sort: <1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17>
#include<stdio.h>
#include <iostream.h>
int main(){
int i,j,s,temp,a[20];
printf("Please Input number of CheggArray entities: ");
scanf("%d",&s);
printf("Please Input %d CheggArray entities: ",s); // read in from user, the array size
for(i=0;i<s;i++) scanf("%d",&a[i]); // get individual array elements or entities
printf(" Array before sorting: "); for(i=0;i<s;i++) printf(" %d",a[i]);
cout << endl << “Stages of array during every iteration of the loop: “ ;
for(i=1;i<s;i++){ // we will swap a[i] and a[j+1] using temp as intermediate storage
temp=a[i]; j=i-1; // run the for loop from 1 to array size s while printing out the stage of //array as well
while((temp<a[j])&&(j>=0)){ a[j+1]=a[j]; j=j-1; } // end while
a[j+1]=temp; // originally a[i] was in temp now it is getting in place of a[j+1]
cout << endl << “Stage “ << i << “ : insert “ << a[i] << “ before “ << a[j+1] ; } // end for
printf(" Array after sorting: ");
for(i=0;i<s;i++) printf(" %d",a[i]); // end for
return 0; } // end main
Sample output:
Array before sorting: 5, 2, 3, 1, 4
Stages of array during every iteration of the loop:
Stage 1: insert 2 before 5
<2>,5,3,1,4
Stage 2: insert 3 inbetween 2 and 5
<2,3>,5,1,4
Stage 3: send 1 to the beginning
<1,2,3>,5,4
Stage 4: last but not the least, insert 4 in between 3 and 5
<1,2,3,4>,5
Array after sorting: <1,2,3,4,5>
c. Show, in the manner of figure 6.4, how bubble sort would sort S O R T M E.
#include<stdio.h>
#include<conio.h>
void CheggsBubbleSort(int[], int);
void main() {
int arr[30], number, i;
printf(" Please Input total number of elements :");
scanf("%d", &number);
printf(" Please Input array elements :");
for (i = 0; i < number; i++)
scanf("%d", &arr[i]);
CheggsBubbleSort (arr, number);
getch();
}
void CheggsBubbleSort(int iarr[], int number) {
int i, j, k, temp;
printf(" Array before sorting:");
for (k = 0; k < number; k++) {
printf("%5d", iarr[k]);
}
for (i = 1; i < number; i++) { // outer for loop to run from 1 to array sixe
for (j = 0; j < number - 1; j++) { // size less one
if (iarr[j] > iarr[j + 1]) { // the usual swap using temp
temp = iarr[j]; // swap array[j] and array[j+1] using temp
iarr[j] = iarr[j + 1];
iarr[j + 1] = temp;
} // end if
} // end for j
printf(" After stage %d : ", i);
for (k = 0; k < number; k++) {
printf("%5d", iarr[k]);
} // end for k
} // end for i
} // end main
Sample output:
Please Input number of elements :5
Please Input array elements :10 4 55 21 6
Array before sorting: 10 4 55 21 6
After stage 1 : 4 10 21 6 55
After stage 2 : 4 10 6 21 55
After stage 3 : 4 6 10 21 55
After stage 4 : 4 6 10 21 55
3. The following refer to inversions.
a. How many inversions are in S O R T M E? n-1 inversions where n is the array size. For example, in our sample out put above, when there are 5 elements in the array, it took 4 stages .
b. Why does bubble sort perform better on a file with fewer inversions? Bubble sort is faster when the array elements are less or when the number of data is small. This is because bubble sort is comparing two neighboring elements at a time (like array[i] and array[i+1]). There is very little amount of extra operations and over head in the case of bubble sort hence it performs better with fewer inversions – may be up to 100 array elements. When he data is small, recursive algorithms can loose performance. In those cases, they can resort to bubble sort.
c. Why is selection sort’s performance not affected by the number of inversions?
Selection sort is an in place sort. It compares elements in place and hence minimizing the number of data movements inside the array.
The way Selection Sort works is as follows:
There is an outer loop that will visit each item in the array to find out whether it is the smallest of all the elements after it. If it is not the smallest, it will get swapped with whatever item in the rest of the array is the smallest.
There is a helper function, IntCheggArraySmall() to find the position of the minimum value in the rest of the array. This function has a parameter, begin to indicate where we wish to begin the search. So as you can see from the loop in IntCheggArraySelectionSort(), when we are looking at position i, we are searching for the smallest from position i + 1 to the end of the array.
As an example, consider an array of 10 elements, this means that i runs from 0 to 9. When we look at position 0, we test to find the position of the smallest element in positions 1..9. If the minimum is not already present at position i, we do swap the minimum into place. Then we start considering i=1 and take a look at positions 2..9. And so on and so forth.
4. The following refer to shellsort.
a. Explain how shellsort can improve the worst-case situations that plague bubble sort.
Shell sort permits swapping of indexes that are far apart in the array, but bubble sort only swaps items that are adjacent. Hence shell sort improves at worst-case situation than bubble sort.
b. Explain why the shellsort increment sequence 1 2 4 8 16 ... is a poor choice that may lead to n2 behavior.
Each number is a double value ( multiply by 2) of previous item in the array. Shell sort starts to swap elements that are farther apart - not near by - now 1 and 16 are farther apart and then again 2 and 8 will be farther apart - always requiring a swap hence O(n^2) .
5. Short programming assignment. Implement the shellsort and use it to sort an array with data in reverse order. Use three different increment sequences and give the results.
public static void IntCheggArrayShellSort (int[] data, int[] intervals)
{
int i, j, k, m;
int N = data.Length;
// The intervals for the shell sort must be sorted, ascending
for (k=intervals.Length-1; k>=0; k--) {
int interval = intervals [k];
for (m=0; m<interval; m++) {
for (j=m+interval; j<N; j+=interval) {
for (i=j; i>=interval && data[i]<data[i-interval]; i-=interval) {
exchange (data, i, i - interval);
}
}
}
}
}
6. The following refer to pointer and index sorting.
6.a.1). What is a pointer sort and (6.a.2) what is its benefit for sorting large objects?
6.a.1) Pointer sort is nothing but a sorting mechanism that makes use of a secondary array as an auxilary to hold pointers to the array of items that are supposed to get sorted.
//Pointer Sort Using Indexes
//( A[0].key = a value lower than any thing in the array = smallest valued data)
//Run Ptr from 0 to .. n // Not n-1 because of the sentinel value
Read in records ptrAray[1] through ptrArayA[n] // Initialize the data
int i, j, temp; // temp is an int as only indexes are swapped
for( i = 2; i<=n; i++ )
{ j = i;
while( ptrAray[Ptr[j]].key < ptrArayA[Ptr[j-1]].key ) // compare keys indirectly thru P
{ temp = Ptr[j]; // swap index pointers
Ptr[j] = Ptr[j-1];
Ptr[j-1] = temp;
j --;
}
}
// First Re Arrange the index pointers, then print out the data in sorted order by a for loop
for( i = 1; i<= n; i++ ) cout << ptrAray[Ptr[i]];
// code snippet to copy from array A to a second array in sorted order
for( i = 1; i <= n; i++ ) Sorted2ndArray[i] = ptrAray[Ptr[i]];
6.a.2:)Benefits of sorting large objects using pointer sort:
Obviously pointer sort is a champion when it comes to storing and sorting large objects or large number of elements in an array. The reasons are multifold.
Example: National Census Database of the whole North America (all states) to make Yellow Pages Phone Book:
6.b. Suppose you have 1000 records on disk. Each record is 2000 bytes, but the key of each record is only 10 bytes. Explain how index sorting could be used to efficiently output the records in sorted order, and why this is more efficient than sorting all the records in main memory.
Key is smaller than the record. Index sorting is better as explained below:
7. Show, in the manner of figure 6.17, how key-indexed counting would sort C A B B A D A B.
8. The following refer to performance under quicksort.
a. How many recursive calls will quicksort make in the worst case for a file of N items?
In worst case quick sort consumes a complexity Order of N square - that is O(N2) And it makes N2/2 recursive calls.
Which means for example, to sort an array of 100 items ( where N = 100), quick sort will make 100 * 100 / 2 recursive calls = 5000 recursive calls - which means it will call the same function again and again recursively for 5000 times. Very resource expensive in worst cases.
This may happen in the following cases:
b. Why does increasing the number of duplicate values in the file to be sorted decrease quicksort performance?
c. List and explain the modifications to the basic quicksort algorithm that can mitigate the problem of duplicate values.
d. What is benefit of median-of-three partitioning?
9. Short programming assignment. Test the recursive and non-recursive versions of quicksort on identical sets of random data and record the results
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.