aboutsummaryrefslogtreecommitdiff
path: root/CS2501/sorting
diff options
context:
space:
mode:
Diffstat (limited to 'CS2501/sorting')
-rw-r--r--CS2501/sorting/sortAssignment1.c80
-rw-r--r--CS2501/sorting/sortAssignment2.c94
2 files changed, 174 insertions, 0 deletions
diff --git a/CS2501/sorting/sortAssignment1.c b/CS2501/sorting/sortAssignment1.c
new file mode 100644
index 0000000..1ff5662
--- /dev/null
+++ b/CS2501/sorting/sortAssignment1.c
@@ -0,0 +1,80 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+
+printData(d,n)
+int *d,n;
+{
+ int i;
+ for (i=0; i<n; i++)
+ printf("data[%d] = %d\n", i, d[i]);
+}
+
+
+selectionSortAscending(d, n)
+int *d, n;
+{
+ int i, j, tmp;
+
+ for (i = 0; i < n; i++) {
+ tmp = d[i];
+ for (j = i + 1; j < n; j++) {
+ if(tmp > d[j]){
+ d[i] = d[j];
+ d[j] = tmp;
+ tmp = d[i];
+ }
+ }
+
+ }
+}
+
+insertionSortDescending(d, n)
+int *d, n;
+{
+ int i,j,tmp;
+
+ for (i = 1; i < n; i++){
+ for (j = i; d[j] > d[j-1] && j != 0; j--){
+ tmp = d[j];
+ d[j] = d[j-1];
+ d[j-1] = tmp;
+ }
+ }
+}
+
+
+
+
+main(argc, argv, envp)
+int argc;
+char **argv, **envp;
+{
+ char buf[1024];
+ int n, *data, i;
+ if (argc !=2 ) {
+ printf("usage: sortAssignment1 #elements\n");
+ exit(1);
+ }
+
+ n = atoi(argv[1]);
+ data = calloc(n, sizeof(int));
+ for (i=0; i<n; i++) {
+ gets(buf);
+ data[i] = atoi(buf);
+ }
+
+
+ printf("unsorted data:\n"); sleep(1);
+ printData(data, n);
+
+
+ selectionSortAscending(data, n);
+ printf("After selection sort\n"); sleep(1);
+ printData(data, n);
+
+ insertionSortDescending(data, n);
+ printf("After insertion sort\n"); sleep(1);
+ printData(data, n);
+}
diff --git a/CS2501/sorting/sortAssignment2.c b/CS2501/sorting/sortAssignment2.c
new file mode 100644
index 0000000..508690d
--- /dev/null
+++ b/CS2501/sorting/sortAssignment2.c
@@ -0,0 +1,94 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+
+printData(d,n)
+int *d,n;
+{
+ int i;
+ for (i=0; i<n; i++)
+ printf("data[%d] = %d\n", i, d[i]);
+}
+
+
+/* implement (only) one of your choosing */
+quickSort(d, n)
+int *d, n;
+{
+}
+
+mergeSort(d, n)
+int *d, n;
+{
+ if (n == 1)
+ return;
+
+
+ int i, n1, n2, *tmp1, *tmp2;
+
+ n1 = n/2;
+ n2 = (n%2 == 0) ? n1 : (n1 + 1);
+
+ /*
+ printf("recursion!%d %d %d %x\n", n1, n2, n, d );
+ */
+ mergeSort(d, n1);
+ mergeSort(&d[n1], n2);
+
+ tmp1 = malloc(sizeof(int) * n1);
+ tmp2 = malloc(sizeof(int) * n2);
+
+ memcpy(tmp1, d, sizeof(int) * n1);
+ memcpy(tmp2, &d[n1], sizeof(int) * n2);
+
+
+ for (i = n-1; i >= 0; i--) {
+ if(n2 == 0)
+ d[i] = tmp1[--n1];
+
+ else if (n1 == 0)
+ d[i] = tmp2[--n2];
+ else
+ d[i] = (tmp1[n1-1] < tmp2[n2-1]) ? tmp1[--n1] : tmp2[--n2];
+ }
+ printf("\n");
+ free(tmp1);
+ free(tmp2);
+ return;
+}
+
+heapSort(d, n)
+int *d, n;
+{
+}
+
+
+
+
+main(argc, argv, envp)
+int argc;
+char **argv, **envp;
+{
+ char buf[1024];
+ int n, *data, i;
+ if (argc !=2 ) {
+ printf("usage: sortAssignment1 #elements\n");
+ exit(1);
+ }
+
+ n = atoi(argv[1]);
+ data = calloc(n, sizeof(int));
+ for (i=0; i<n; i++) {
+ gets(buf);
+ data[i] = atoi(buf);
+ }
+
+
+ printf("unsorted data:\n"); sleep(1);
+ printData(data, n);
+
+ mergeSort(data, n);
+ printf("After sort\n");
+ printData(data, n);
+}