Description
Goal:
Understanding of sorting concepts.
Requirements:
-
Write a C program to take a sequence of n integer values and remove duplicate occurrences, i.e. only the first occurrence of each value will remain. n will be the first input value and the sequence may be read using scanf()s. The phases for performing this task are:
-
-
Read input sequence of values, each value giving an ordered pair (value, position indicator).
-
-
-
Sort the pairs in ascending order by value in a stable fashion. If your chosen sort is stable, then the key is just the value. If your chosen sort is unstable, the key must be extended with the position indicator.
-
Using one pass ( Θ(n) time) over the sorted result, remove any occurrences beyond the first one for a key.
-
-
-
Sort the pairs using the (unique) position indicator as the key.
-
-
-
Output the number of unique values followed by the values (without the position indicators).
-
The input will be read from standard input (stdin) as either keyboard typing or as a shell redirect (<) from a file. Prompts/menus are completely unnecessary!
-
Submit your program on Blackboard by 10:45 am (section 004) or 1:45 pm (section 003) on September 13. One of the comment lines should indicate the compilation command used on OMEGA.
Getting Started:
-
You may use any sort you wish, but the standard library qsort() is recommended.
-
Processing for the input:
|
Input: |
a. Array of pairs |
b. After sorting |
c. Remove extras |
d. After sorting |
Output: |
||||||||
|
10 |
0: |
3 |
0 |
0: |
1 |
5 |
0: |
1 |
5 |
0: |
3 |
0 |
7 |
|
3 |
1:31 |
1:24 |
1:24 |
1:72 |
3 |
||||||||
|
3 |
2:72 |
2:28 |
2:30 |
2:53 |
7 |
||||||||
|
7 |
3:53 |
3:30 |
3:46 |
3:24 |
5 |
||||||||
|
5 |
4:24 |
4:31 |
4:53 |
4:15 |
2 |
||||||||
|
2 |
5:15 |
5:37 |
5:72 |
5:46 |
1 |
||||||||
|
1 |
6:46 |
6:46 |
6:99 |
6:99 |
4 |
||||||||
|
4 |
7: |
3 |
7 |
7: |
5 |
3 |
9 |
||||||
|
3 |
8: |
2 |
8 |
8: |
7 |
2 |
|||||||
|
2 |
9: |
9 |
9 |
9: |
9 |
9 |
|||||||
|
9 |
|||||||||||||
