lib_sort.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #include "lib_sort.h"
   5 #include "lib_ll.h"
   6 #include "lib_vstack.h"
   7
   8 void sort_selection(int list[], int lo, int hi)
   9 {
  10         int s, j;
  11         for(j = lo; j < hi; j++)
  12         {
  13                 s = sort_get_smallest(list, j ,hi);
  14                 sort_swap(list, j, s);
  15         }
  16 }
  17
  18 void sort_insertion(int list[], int lo, int hi)
  19 {
  20         int j, k, key;
  21         for(j = lo+1; j <= hi; j++)
  22         {
  23                 key = list[j];
  24                 k = j -1;
  25                 while(k >= lo && key < list[k])
  26                 {
  27                         list[k+1] = list[k];
  28                         --k;
  29                 }
  30                 list[k+1] = key;
  31         }
  32 }
  33
  34 void sort_heap(int num[], int n)
  35 {
  36         int k, item;
  37         for(k = n/2; k >= 1; k--) sort_shift_down(num[k], num, k, n);
  38         for(k = n; k > 1; k--)
  39         {
  40                 item = num[k];
  41                 num[k] = num[1];
  42                 sort_shift_down(item, num, 1, k-1);
  43         }
  44 }
  45
  46 void sort_quick(int a[], int lo, int hi)
  47 {
  48         if(lo < hi)
  49         {
  50                 int dp = sort_partition(a, lo, hi);
  51                 sort_quick(a, lo, dp-1);
  52                 sort_quick(a, dp+1, hi);
  53         }
  54 }
  55
  56 void swap(int list[], int i, int j) {
  57         int hold = list[i];
  58         list[i] = list[j];
  59         list[j] = hold;
  60 }
  61
  62 int partition2(int a[], int lo, int hi)
  63 {
  64         int pivot = a[lo];
  65         --lo; ++hi;
  66         while(lo < hi) {
  67                 do --hi; while(a[hi] > pivot);
  68                 do ++lo; while(a[lo] < pivot);
  69                 if(lo < hi) swap(a, lo, hi);
  70         }
  71         return hi;
  72 }
  73
  74 void sort_quick_norecurse(int a[], int lo, int hi)
  75 {
  76         int stackItems = 1, maxStackItems = 1;
  77         int dp;
  78         Stack_Head *pHead = vstack_new();
  79         Stack_Node *pNode = NULL;
  80         Sort_Data *pData = NULL;
  81         pNode = vstack_push(pHead);
  82         pNode->pData = sort_data_new(lo, hi);
  83         while(pHead->count != 0)
  84         {
  85                 --stackItems;
  86                 pNode = vstack_peek(pHead);
  87                 pData = pNode->pData;
  88                 vstack_pop(pHead);
  89                 if(pData->left < pData->right){
  90                         dp = partition2(a, pData->left, pData->right);
  91                         if(dp - pData->left + 1 < pData->right - dp) {
  92                                 vstack_push_data(pHead, sort_data_new(dp+1, pData->right)); /* update the push function to accept data */
  93                                 vstack_push_data(pHead, sort_data_new(pData->left, dp));
  94                         } else {
  95                                 vstack_push_data(pHead, sort_data_new(pData->left, dp));
  96                                 vstack_push_data(pHead, sort_data_new(dp+1, pData->right));
  97                         }
  98                         stackItems += 2;
  99                 }
 100                 if(stackItems > maxStackItems)maxStackItems = stackItems;
 101         }
 102 }
 103
 104 void sort_shift_down(int key, int num[], int root, int last)
 105 {
 106         int bigger = 2 * root;
 107         while(bigger <= last)
 108         {
 109                 if(bigger < last)
 110                                 if(num[bigger+1] > num[bigger]) bigger++;
 111                 if(key >= num[bigger]) break;
 112                 num[root] = num[bigger];
 113                 root = bigger;
 114                 bigger = 2 * root;
 115         }
 116         num[root] = key;
 117 }
 118
 119 int sort_partition(int a[], int lo, int hi)
 120 {
 121         int pivot = a[lo];
 122         int last_sm = lo, j;
 123         for(j = lo + 1; j <= hi; j++)
 124         {
 125                 if(a[j] < pivot)
 126                 {
 127                         ++last_sm;
 128                         sort_swap(a, last_sm, j);
 129                 }
 130         }
 131         sort_swap(a, lo, last_sm);
 132         return last_sm;
 133 }
 134
 135 int sort_get_smallest(int list[], int lo, int hi)
 136 {
 137         int j, small = lo;
 138         for(j = lo + 1; j <= hi; j++)
 139                 if(list[j] < list[small]) small = j;
 140         return small;
 141 }
 142
 143 void sort_swap(int list[], int i , int j)
 144 {
 145         int hold = list[i];
 146         list[i] = list[j];
 147         list[j] = hold;
 148 }
 149
 150 Sort_Data *sort_data_new(int a, int b)
 151 {
 152         Sort_Data *pData = malloc(sizeof(Sort_Data));
 153         pData->left = a;
 154         pData->right = b;
 155         return pData;
 156 }