Previous: 10.8 Exercises
Up: 10 Sorting and Searching
Previous Page: 10.8 Exercises

10.9 Problems

1. Write a function that sorts an array of integers in decreasing order.

2. Write a function that sorts an array of integers in either increasing or in decreasing order as specified by an argument.

3. Write a binary search function that searches an array of integers sorted in decreasing order.

4. Write a binary search function that searches an array of integers sorted in either increasing or in decreasing order as specified by an argument.

5. Write a function that uses insertion sort to sort an array of input numbers, either in increasing or in decreasing order.

6. Write a function that uses insertion sort to sort an existing array of integers.

7. Write a program to read an array of integers from a file. Write a function that takes two arguments: low and high. Low and high specify the low and high indices of an effective array. Function finds indices for the maximum and the minimum elements in the specified effective array. Use the function with zero for low and the highest valid index for high. Print the values of maximum and minimum.

8. Repeat the last problem, but this time swap the largest element in the effective array with the one at the high index, say index n; swap the smallest element with the one at the low index.

9. Repeat the last problem, but this time after the swap of the elements change the effective array so low is 1 and high is n - 1. Repeat the process so the largest and smallest elements are found in the array from index 1 through n - 1. Swap the next largest element with the one at index n - 1, and swap the next smallest with the one at index 1. The next swap considers the array from index 2 through n - 2, etc until all elements of the array are in increasing order. This is another way of sorting an array.

10. Compare the operations involved in the above sorting with that for bubble sort. What are the approximate comparisons required to sort an array of n items by the two methods.

11. Write a menu_driven program that allows the following commands: get data from a file, add data, delete data, sort data, search data, save data to a file, help, quit. Assume that data records consist of id numbers and exam scores. Sorting must be done either by id numbers or by exam scores and it must be either in ascending or descending order.

12. Repeat the last problem, but get data uses insertion sort to read data in sorted form by id numbers.

13. Write a program that reads integers into an array A. Use another array P of the same size to store each index of the array A in the following way. The index in A with the smallest element is stored at index 0 of P, the index of the next smallest element in A is stored at index 1 of P, and so on. Print the array A, and print the elements of A ordered in the sequence given by each succeeding index stored in P.

14. Repeat Problem 11, but use the approach of Problem 13 to sort the data.

15. Repeat Problem 11, but use insertion sort to read data in sorted form by id numbers. The sort command then uses approach of Problem 13 to sort the data by exam scores.

16. Compare the operations required for sorting in Problems 11 and 14.

17. Write a program to merge two sorted arrays A and B into a third array S as follows. Start with initial index, ia, of the element to be merged from A and also the index, ib, of the element from B. If the element from A is smaller than the element from B, append that element of A to the array S and increment ia; if the element of B is smaller than that of A, add the element from B to S and increment ib. If they are equal, add both elements to S and increment both ia, ib. If either array is exhausted, copy the elments from the other array into S. Repeat until both arrays are exhausted. Print A, B, and S.

18. Develop a sort method using the merging of two arrays as in the last problem. Given an array with 8 elements, assume it is split into as many arrays as there are elements. Merge each adjacent pair into 4 arrays of two elements each. Merge each pair again into 2 arrays of 4 elements each. Finally, merge the two into a sorted array. The method can be applied to any array and is called merge sort method. Write a program that sorts an array by merge sort.

19. Write a program that sorts the characters in a string.

20. Write a program that reads strings; for each string compute the frequency of occurrence of each character.

21. Write a program that reads text from a file and computes cumulative frequency of occurrence of each character.

22. Write a program that searches a string for a specified character and returns the index of its first occurrence.

23. Write a program that returns the first occurrence of a character in a string starting at some specified index.

24. Write a program to find all occurrences of a character in a string.

25. Write a program that replaces all the occurrences of a character in a string by another character.

26. Write a program that sorts characters in a string according to a different order than that of the ASCII values. Use a function to compare two characters and return whether one is greater than, equal to, or less than the other. The function first converts all lower case letters to upper case and then compares their ASCII values. The program sorts characters ignoring case.

27. Write a sort program similar to the above problem for integers. Use a function that compares the absolute values of two integers. The program sorts by absolute values.

28. Write a character sort program that uses a function, cmpchrs(), to compare two characters by an arbitrary criteria. Assume that an array stores all ASCII printable characters in an assumed increasing order: vowels first, consonants next, digits next, all others next. The function, cmpchrs(), looks up the corresponding indices of characters to compare characters. The result of comparing the indices is returned by the function. The program sorts characters in an order specified by cmpchrs().