，min sort, bubble sort, insertion sort, quick sortmerge sort.
Introduction
Putting items into a sorted order is one of the most common tasks in Computer Science, and so as a result there are myriad library routines that will do this task for youbut that does not absolve you of the obligation of understanding how it is done, and in fact it behooves you to understand the various algorithms in order to make wise choices.
The best that can be accomplished (the lower bound) for sorting using comparisons is (n log n) where n is the number is elements to be sorted. If the universe of elements to be sorted is limited (small), then we can do better using a Count Sort, where is O(n), where we count the number of occurrences of each element in an array, or a Radix Sort, which is also O(n) with a constant proportional to the maximum number of digits in the numbers being sorted.
What is this O and stuff? It’s how we talk about the execution time (or space) of programs. We will discuss it in class, and you will see it again in CMPS 101.
min-Sort
Perhaps the simplest sorting method is to look for the smallest element (the minimum) and move it to the top. We could do this by making a copy of that element, and then shifting everything down by one, and then placing the copy in the top slot. But that seems silly, why move all of those elements? Let’s just exchange (swap) the top element with the smallest element.
At this point what do we know? We know that the smallest element is at the top. Since that is true and it will not change (we call this an invariant), we can forget about it and move on. Let’s consider the second element:
Why not just do what we did the first time? If we do that, then what do we know? We now know that the top (first) element is the smallest, and the second element is the second smallest (or the same, if there are duplicates). We can repeat this for each element in the array, in succession, up to but not including the last element. By the method of induction, we can show that the array is sorted.
Why do we not need to concern ourselves with the last element? The answer is that if it were not the smaller element when we were at the last step, then it was exchanged with the penultimate element, and thus must necessarily be the largest (and consequently, last) element in the array.
To get you started, here is the code for minSort. Notice that it is composed of two functions: minIndex which finds the location of the smallest element, and minSort which actually performs the sorting.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
uint32_t minIndex(uint32_t a[], uint32_t first, uint32_t last)
#123;
uint32_t smallest = first;
for (uint32_t i = first; i lt; last; i += 1)
#123;
smallest = a[i] lt; a[smallest] ? i : smallest;
#125;
return smallest;
#125;
void minSort(uint32_t a[], uint32_t length)
#123;
for (uint32_t i = 0; i lt; length - 1; i += 1)
#123;
uint32_t smal㹥㱳‽⼠㹭㱩㵩∬≧㹴ㅨ㈩㰻⼼㹮㰾⼠㸯㰾㵳∽≥㸢ㄾ㌠㰠⼠㹡㱮⽡㹳㱳⼽㹹൷੯•‾‼ ⁰㰾⼠㹭ൡ੬⁴†‡‽†
†‼㱳㵳∽≭㹥൮ੴ•‾ †⁉⁴‧†㱬㹴㱯⁰㴠≹≥㹬‼⠯䄾‼㩳⁰†⤲㰳⼻㹡㱮⽲㸠㰯㵳≳≮㹥•‾†㴠†⠨䅡⥛㱳⽭㹳㱴†⽡㹛㱩 㴼≢∼㹳⁰㱳⼽㹥㰢†⼠㸠㰣‼㴾∼∾㸼⁰•㵬㰠⼣㸼㰯⽮㸾㰼‾㴠≣∽㸢†㵰ㅮ†ⴽㄢ㱲⽮㹡㱮‼⼯㹳㱰㵳≰≬㹡‽••䄾ⴲㄵ‼㭰䅮㰯⽰㸊㰠†⼠㸠㰠†㴍∊∠㸠††‼ ⁴‾⠠䄼ⵢㅯⱹ‾䄍⥴㱡⽢㸊㰼‾⼍㸊㰼㵴≨≭㹥†⁰⁸㵩㰿⼠㹫㱥⽳㸠㱴㵴≨≲㸠⁰††㰠⽳㹨㱡⁴⽨㹥㰠†㵥≣∠㹬⁴㰮⼠㸠㱷⽤㸠㱳⁴㵩≣≴㹨⁴†⁴㴠†ㅩ㱳⼠㸬㰠⁴⼠㹷㱥㵯≯≲㹴††㱰⼠㹥㱥⽡㹴㰠㵭≡≯㸠⁉㰠⽷㹷㱥⽯㹫㰠⽴㹥ഠ††⁹⁴†㱮⽯㹥൲ਠ†⁰㰮⼠㹩൳ਠ⁰㰠⽩㹣൵ੴ㱥⽤㹴ഠਭ㰠⽦㹲൳ੴ㰩㍴㵳∬䤠ⴠ≤㸠䥯㱷⽥㍣㹡൬੬㰠㹩䥮⁰⁴†Ⱐ⁴⁰†⁵⁴⁴⁓⁴†⸩䤼⁰†⁵Ⱐ⁷†⁹⁷䔠Ⱐ⁴⁵⁵†⁵†††⁴⸠㱩⁃⼠㹡൬㱡㵲∠†≬㹵㱥⼠㹩൳ਠ㱩㹥൮੩⁴†㱦㹥ഠੳ⁷⁰†⁰㱡㹯൮ਮ†⁁†⁶†⁰㱲㵴∠≤㹶ൡ੮⁴††⁴†㱭㹯㰠㴠≩≵㹭ㅥ㱮⽴㹮㰮⼠㸯㰾㵣≬∢㹨㉩㱧⽨㹴㰠‾⼼㸯㱦㵡≢∊㸠㌠㰠⼠㹤㱹 ⼠㸠㰠†㴊∠∠㸠㐠㰠⼠㹤㰠⽳㹳㰽⁴㴊∠∠㸠㔠㰠⼠㹲㱥⽰㹡㱮㵮≥∯㹳㙰㱡⽮㸠㰯⽰㹡㱮㵮≥∯㹳㝰㱡⽮㸠㰯⽰㹡㱮㵮≥∯㹳㡰㱡⽮㸠㰯⽰㹡㱮㵮≥∯㹳㥰㱡⽮㸠㰯⽰㹡㱮㵮≥∯㹳ㅰち㱮⼾㸯㰾⁰⽲㹥㰾†㴠∠≴㹤ㄾㄍ㰊⼠㸠㰠†⼠㸠㰼⽴㹬ൡੳ‽••‾ †㰠⼠㸠ഠਠ††††‼⁰‾‼⁰㱡㴢≬∾㸼൳ੰ†‽•㱴㸣㰠㵳∽≡㸭⡉䅎⁓㩔⁒⁔‼⥢㱲⼠㹰㱡⽬㹡㱳㵳≰≬㹡㴢‾ㄣ†⁰⡳䅳⤽㰢⽭㹫㱥⽲㹤㰢㵰≡≗㹁⁐
⁸†㴣‱䄲㱵⽩㹟㱴†⼽㸠㱸†㴠≹∠㸻†※†⁶㵥⁃⁵⁴ㄠ㰫⼽㸣㰱※⼼㸯㱳‼㴾∼∾㸼⁰•㭮㵥•〾‼䄠㬢㰢⼾㹰㱡⽬㹡㱳㵹≷∾㹥‼ 䅰‾⬼ ㅳ㵮‾䄼㱡⽮㸠㰯⽰㹡㱮㵮≥≰㹡†‽㴢⁴ⵡ•ㄾ㰣⼠㹮㰠⽳㹳㰽㵯≲≥㹦‼㱁⽐㸠㱹‣⼱㸲㰳㴠≴∠㸻†⁸†‽䄠※⬠⁹ㄠ†㵸†㰠⼣㸼㰯⽮㸾㰼㴯∾≮㸠‽㱮⽥㹰㱡⽬㹡㱳㴠∼∠㹣㱹⽷㸾㱥⽦㸼㰯⽳㸾഼ਯ⁰‾‼ ⁰‾㰼⽢㸯ാ਼ ⁰‾ †㰠⼠㸠ഠਠ††††㰼⼯㸠ഠਠ㰠⼠㹴൲ਾ㰍⼊㸠ഠਠ㰼㹴‾‼‾″䥲㽴‼″⁰⁴Ⱪ††⁴㰬⼠㹸ൣ੨㱡㍧㵨≥ⴠ≯㹶⁴⡩⥡㱮⽤㍮㹯ഠੰ㱡㹲⁴†⁴⁙†⁴Ɱ†⁴ⱦ†䉴Ⱐ†††⁴⁵䥳†⁴‾‼†⁴䍯Ɑ⁰†㱲⽥㸠൮ਠ㱰㹩䙲Ⱐ⁸⁴†⁴㨭†⠲⥰†⁃⁇⁷㭩⡤⥦††‸⁰†ⱶ⡺⥨⁴㱴⽥㹥൲ੳ㰠㹲Ɐ††⁵††⁹ⱱ⁵⁶⁴⸠⁵†㰠⽴㸠റਰ㰱㸠Ⱐ‵‰ ‾Ⱐ†⁹ †‼⸠††Ɽ†Ⱳ•††⸼㰯⽳㹡൮ਾ㰼㹲‼†′ ‽ ‾ †‴Ⱟ‾⁰•⸼ ‾⁰ⱥ•‼‾‾‾ ⸠䥬Ⱪ‸†‹‾†•‾‾ⱡ‼††⸠†⁴㽥††⁴⡧⁴⥩†⹉⁴䐠††Ɽ†⁶†⁴⠠⥦⁴†⁴㰠⽧㹥ഠੴ㱨㵯≲†≴㹨㱥⼠㹩൯੮㰠㹥൮⁵⁴㱥㹩൳ੴ†††㱮㹥ഠ⁴†⁷㱨⁹㵮≩≳㸠൳੯⁴‼ ⁰‾ ‼㱰㹡㱴⁴㵥≣≮㸠ㅴ㱩⽭㸠㱴⼠㹡㱬⁴㵥≴≵㹯㈻㱳⼠㹭㱥⽡㹴㰠㵮≳≬㹥㍮㱧⽴㹯㱮⽰㹥㱳㵗≥≧㹥㐠㱴⽨㹯㱮†⽬㹩㱳㴠≮≡㹶㕥㰠⼨㹯㱲
⼠㹲㱵㵴≨≗㹥㘠㱰⽲㹳㱥⼠㹥㱬⁴㵩≮≩㹳㜠㱰⽡㹗㱥⽷㸠㱮⁴㴬∠≭㹡㡮㱹⼠㹳㰠⼠㹷㱥㵡≲∠㹷㥩㱴⽨㹮㱴†⽴㹨㱥⁵㵧≥∠㹧ㅲづ㱡⽴㹨㱡⼿㸠㱔㵩≳∠㹮ㄮㄠ㱔⽨㹲㱳⽡㹳㱥㴠≴≯㹦ㄠ㉯㱵⽲㹯㱲⽭㸠㱩㵮∩∠㸯ㄾ㌍㰊⼼㹲㱥⽡㹳㱳㵴∠≯㹮ㄢ㐾㰼⼯㹲㱥 ⼼㹴㱡㴼≴∾㸍ㄊ㔠㰠⼠㸠㰼‾⼍㸊㰠†㴠∼≬㹡ㅳ㙳㰽⼢㹥㱲⼊㸠㰠⼠㸠ഠਠ†††‼⁰‾‼⁰㱮⼠㹡൳ੳ‽••‾‱‼ 㱰‾㴾∼∠㹣൬‽••‾′‼㰯㹮㰾 㵮∠≳㸽㰢•㵰≡∼㹳㱰㵬≩≳㹰㰼⽢㸼㱰㵬≩∼㸯㰯⼾㹮㰠㵥∢≡㹮⠾⥢㱲⼠㹰㩡㱮⼠㹳㰽⼢㸢㰾 ⽳㹰㱡㵰≡≡㹳‽㰢•㵰≡∾㸼㱡⽮㹳⡮⤢‾㬯㱰㵳≰≳㹳〽㰢⽬㸾㨱㰰⼼㹮㰾⼠㸯㰾㵳∽≥㸢‾‱‱‼‾㴼㰯㵳≳∢㸾〱㰲⼼㹮㰼⽢㸼㱳⼠㹣㱬•㴾∱≰㹡‾‼‼㵳⁰㰠⽣㸽㰢⽥㸢㰾㵢≲≳㹰†㴽•㱮⽥㸼㰯⽮㸾㰼‾㴠≣∽㸢 㵳⁰㰾⼼㸾㰼⽮㸠㱣‽㴢∾≳㹰‾‼㱢‼㵣≬≮㹥㰸⼼㹮‾㱲㵬≡≥㸢㰹⼼㹮‾㩢㱲⼠㹰㱡⽬㹡㱳㴰∼≮㸾‼† ‾㰼†㴽∢∱㸼㱰⽡㹲†‾㴼㵳⁰㩡㱳⽳㹮㱥′⼲㸼㰯‾㴾∼∠㹣‽•⸾⡡⤾㰼⽢㸼㱳⼠㹣㱬•㴾∲≰㹡‾‼†㰯㵳≳∾㸲㱰⽡㹲†‾㭰㩳㱳⼽㹥㰢‶⼼㸯㱳‼㴼≳≣㹬‽•⸷⠾⥢㱲⼠㹰㱡⽬㹡㱳㴸∼≮㸾‼† ‾㰼†㴽∢∹㸼㱮⼾㸯㨾㰼⽳㹣㱬⼽㸢㱬‾㵰≡≲㸠 ‾‼ ⁰‾⸠⠠⤼㰯⽴㸠㰠†⼠㸠㰠‼㵡≳≯㹤•‾㰊†㴠∠≰㹡㱳⼽㹥•⡡⥦⁵⭮⬢‾⡳⥹㱷⽯㹤㱥 ⽳㹰㱡㵬≡≴㹩⁴㱥㵴∼≳㹰㱬⽡㹰㩡㱲⽡㸨㱩⽳㸩㰼㵰≡≳㹰‾‼㱢‼㵣≬≮㹥㱰⽡㹡㰢⽫㹲㱤⽦㸼㰯⽳㸾ഠ੬†
⁴
†㱴⼻㹳൰†‽㰢⽮㹢ੲ•‾‱‼㰯⽳㸼യੳ㱰⽡㸠യਾ㰼⽳㹡൮ਠ㱣㍡㴢≬䵩ⴠ≩㹤䵤†㱥⽮㍩㹴੭㱳㸠䴯‽ ‾†•‾†⁴䤾 ‽††ⱳ‽•⁝Ᵽ⁌㱬⽦㸯൳ੰ㱡㸾‼†‾䴠㩩⁝⠠⤢‾‾••†
†䩰Ɱ⁴†⁴‼⁰‼㰠⽣㹡൳ੳ㰽㹬䅩†⡓ⱴ
Ⱨ⁴⥡ ⱡ‾†‣㩴⠼⥳⁰‼‾†ㅩ‾†ⱳ⁰†⡣⥳⁵•‼㉳‽⁵Ɱ‾⁰‾‼†‾†‽⁷‼㍳䵮‾ ⠨ ⤼‼㍳†•ㅮ⁴‣㈠†⁴‼‾‽‾†‼†㍣⸢‾†⁴㼠‼⡥⥷‾†Ɫ‼⡳⥮†††‽‣‾‼•ㅬ‾㈠⸠††‾‾⁴⁴⁰‾ †ㄠ††⁴㉥Ɑ⁝⁛‼‼ †㌠⸠㰠⼠㸠ഠ੬㰠㸽†㍢‱‾ †⁴⁔ㅨⱥ†⁴††•†⁰㉹• ⰾ›ㄽ•㈢ⰾ††⁴㍥㱌⽩㹴൛ੲ㱝㸯⁰‾‼㰠㸼䕳††††‼••‾‾ⸯ㰾⼼㹡൮ਠ‽•㱩㸢⸼⁰‽⡭⥥‣⁹‼⁰‾⁰⸢㰾⼠㸠ഠਠ‼⁰㱮⼠㹡൳ੳ‽•㱹⽷㹤ഢਾ㰼㹰†⁴⁴‼ Ɱ†•†††㱴⽌㹴൛੬⁝‼ 㱰㸾䄼‽‾䔠䄠䐠䴠䔠†‽•⁰㱰⽡㸼ൢੲ† ‾‼㱳㹮††‽⁏⁴†㱬⽥㹮൴ੳ‼ ⁰㱡㸼‾‾†㉳⸽㰢⽫㹷൯ੲ•‾㱬㸼 ‾‾†††㱴⽛㸼യੳ㱰⽡㸼br /> r += 1
|
Your Task
You task is to:
- Implement a testing harness for sorting algorithms. You will do this using getopt.
- Implement five specified sorting algorithms.
- Gather statistics about their performance.
Specifics
You must use getopt to parse the command line arguments. To get you started, here is a hint.
1
|
while ((c = getopt( argc, argv, " AmbiqMp : r : n :" )) != -1)
|
- -A means employ all sorting algorithms.
- -m means enable minSort.
- -b means enable bubbleSort.
- -i means enable insertionSort.
- -q means enable quickSort.
- -M means enable mergeSort.
- -p n means print the first n elements of the array. The default value is 100.
- -r s means set the random seed to s. The default is 8222022.
- -n c means set the array size to c. The default value is 100.
It is important to read this carefully. None of these options is exclusive of any other (you may specify any number of them, including zero).
- Your random numbers should be 24 bits, no larger(2^24 - 1 = 16777215).
- You must use rand() and srand(), not because they are good (they are not), but because they are what is specified by the C99 standard.
- Your program must be able to sort any number of random integers up to the memory limit of the computer. That means that you will need to dynamically allocate the array using calloc().
- Your program should have no memory leaks.
A large part of this assignment is understanding and comparing the performance of various sorting algorithms. Consequently, you must collect some simple statistics on each algorithm. In particular,
- The size of the array,
- The number of moves required (each time you transfer an element in the array, that counts), and
- The number of comparisons required (comparisons only count for elements, not for logic).
Submission
You must turn in your assignment in the following manner:
- Have file called Makefile that when the grader types make will compile your program. At this point you will have learned about make and can create your own Makefile.
- CFLAGS=-Wall -Wextra -Werror -pedantic must be included.
- CC=gcc must be specified.
- make clean must remove all files that are compiler generated.
- make should build your program, as should make all.
- You program must have the source and header files:
- minsort.h specifies the interface to minSort().
- minsort.c implements minSort().