From a39b0d92cf9f84139439cc86fe1c7dc6a357e8a7 Mon Sep 17 00:00:00 2001
From: Kyle K <kylek389@gmail.com>
Date: Sat, 11 Dec 2010 17:21:43 -0600
Subject: bubblesort: implement swapped condition

---
 sorts.c | 31 +++++++++++++++++++++++--------
 1 file changed, 23 insertions(+), 8 deletions(-)

diff --git a/sorts.c b/sorts.c
index 46e3f2d..6cc74dc 100644
--- a/sorts.c
+++ b/sorts.c
@@ -26,7 +26,7 @@ FILE *out = NULL;
 void insrt_sort(int *, int);
 void select_sort(int *, int);
 void bubble_sort(int *, int);
-void prnt_arr(int *, int);
+void print_arr(int *, int);
 int *mk_rand_arr(int, int);
 void mergesort(int *, int, int);
 void merge(int *, int, int, int);
@@ -52,8 +52,10 @@ void quicksort(int low, int high, int *arr)
             /* seek until we find strings that need to be swapped */
             while ((lo < high) && (arr[lo] < mid))
                 ++lo;
+
             while ((hi > low) && (arr[hi] > mid))
                 --hi;
+
             /* swap */
             if (lo <= hi)
             {
@@ -65,9 +67,11 @@ void quicksort(int low, int high, int *arr)
                 --hi;
             }
         }
+
         /* sort the left partition */
         if (low < hi)
             quicksort(low, hi, arr);
+
         /* sort the right partition */
         if (lo < high)
             quicksort(lo, high, arr);
@@ -154,12 +158,14 @@ void insrt_sort(int *arr, int elem)
     {
         tmp = arr[i];
         j = i - 1;
+
         /* tmp is compared to all elements that were already inserted and are in order */
         while ( (j >= 0) && (tmp < arr[j]) )
         {
             arr[j+1] = arr[j];
             j--;
         }
+
         arr[j+1] = tmp;
     }  
 }
@@ -179,12 +185,15 @@ void select_sort(int *arr, int elem)
             }
 }
 
-/* pretty fast on nearly sorted array with extra code */
+/* pretty fast on nearly sorted array with extra swapped code */
 void bubble_sort(int *arr, int elem)
 {
-    int i, j, tmp;
+    int i, j, tmp, swapped;
     
     for (i = 0; i < elem; i++)
+    {
+        swapped = 0;
+
         for (j = 0; j < elem - i - 1; j++)
         {
             if (arr[j] > arr[j+1])
@@ -192,11 +201,17 @@ void bubble_sort(int *arr, int elem)
                 tmp = arr[j];
                 arr[j] = arr[j+1];
                 arr[j+1] = tmp;
+                swapped = 1;
             }
         }
+
+        /* is not swapped implies already sorted array */
+        if (!swapped)
+            break;
+    }
 }
 
-void prnt_arr(int *arr, int elem)
+void print_arr(int *arr, int elem)
 {
     if (arr == NULL)
         fputs("nothing to print", stderr);
@@ -262,21 +277,21 @@ int main(int argc, char **argv)
 #else
     printf("unsorted:\n");
 #endif
-    prnt_arr(arr, ARR_SIZE);
+    print_arr(arr, ARR_SIZE);
 
-    //bubble_sort(arr, ARR_SIZE);
+    bubble_sort(arr, ARR_SIZE);
     //select_sort(arr, ARR_SIZE);
     //insrt_sort(arr, ARR_SIZE);
     //mergesort(arr, 0, ARR_SIZE - 1);
     //shell_sort(arr, ARR_SIZE);
-    quicksort(0, ARR_SIZE, arr);
+    //quicksort(0, ARR_SIZE, arr);
 
 #ifdef PRINT_FILE
     fprintf(out, "sorted:\n");
 #else
     printf("sorted:\n");
 #endif
-    prnt_arr(arr, ARR_SIZE);
+    print_arr(arr, ARR_SIZE);
 
 #ifdef PRINT_FILE
     fclose(out);
-- 
cgit v1.2.3