KrautwiggerlRoyal Member

Beiträge: 1603Registriert: 12.12.2000
|
Datei "sort.h":
$this->bbcode_second_pass_code('', '// abstract implementation
template<class T> class AbstractSort { protected: void swap(T *a, T *b); public: virtual void sort(T *arr, int l, int r)=0; };
template<class T> void AbstractSort<T>::swap(T *a, T *b) { T temp = *a; *a = *b; *b = temp; }
template<class T> class Insertion: public AbstractSort<T> { protected: void insertsort(T *arr, int l, int r, int step); };
template<class T> void Insertion<T>::insertsort(T *arr, int l, int r, int step) { for (int i=l+step; i<=r; i+=step) { int j=i; while ((j>l) && (arr[j-step] >= arr[j])) { swap(&arr[j-step], &arr[j]); j -= step; } } }
// bubblesort
template<class T> class BubbleSort: public AbstractSort<T> { public: void sort(T *arr, int l, int r); };
template<class T> void BubbleSort<T>::sort(T *arr, int l, int r) { for(int i=r-1;i>=l;i--) { bool switched = false; for(int pos=l;pos<r;pos++) { if(arr[pos]>arr[pos+1]) { swap(&arr[pos],&arr[pos+1]); switched = true; } } if (!switched) break; } }
// selection sort
template<class T> class SelectionSort: public AbstractSort<T> { public: void sort(T *arr, int l, int r); };
template<class T> void SelectionSort<T>::sort(T *arr, int l, int r) { for(int i=l; i<=r; i++) { int minPos = i; int minVal = arr[i]; for(int j=i+1;j<=r;j++) { if (arr[j]<arr[minPos]) { minPos = j; minVal = arr[j]; } } swap(&arr[i], &arr[minPos]); } }
// insertion sort
template<class T> class InsertionSort: public Insertion<T> { public: void sort(T *arr, int l, int r); };
template<class T> void InsertionSort<T>::sort(T *arr, int l, int r) { insertsort(arr, l, r, 1); };
// shellsort
template<class T> class ShellSort: public Insertion<T> { public: void sort(T *arr, int l, int r); };
template<class T> void ShellSort<T>::sort(T *arr, int l, int r) { int step = r-l; do { step = (int) ceil(((float)step-1)*5/11); for (int i=0;i<step;i++) insertsort(arr, l+i, r, step); } while (step > 1); }
// heapsort
template<class T> class HeapSort: public AbstractSort<T> { protected: int k; void heapify(T *arr, int l, int q, int r); void buildheap(T *arr, int l, int r); public: HeapSort(int k=3) { this->k = k; } void sort(T *arr, int l, int r); };
template<class T> void HeapSort<T>::heapify(T *arr, int l, int q, int r) { int largest = l+k*(q-l)+1; if (largest <= r) { int p = largest+k-1; for (int i=largest+1; i<=p; i++) { if ((i <= r) && (arr[i]>arr[largest])) largest = i; } if (arr[largest]>arr[q]) { swap(&arr[q], &arr[largest]); heapify(arr, l, largest, r); } } }
template<class T> void HeapSort<T>::buildheap(T *arr, int l, int r) { for (int i = (int)((r-l-1)/k); i>=0; i--) heapify(arr, l, l+i, r); }
template<class T> void HeapSort<T>::sort(T *arr, int l, int r) { buildheap(arr, l, r); for (int i=r; i>l; i--) { swap(&arr[l], &arr[i]); heapify(arr, l, l, i-1); } }
// quicksort, getuned mit Insertsort
template<class T> class QuickSort: public Insertion<T> { protected: int partition(T *arr, int l, int r); public: void sort(T *arr, int l, int r); };
template<class T> int QuickSort<T>::partition(T *arr, int l, int r) { int x = (l+r)/2; int i = l-1; int j = r+1; if (arr[x] > arr[r]) swap(&arr[x], &arr[r]); if (arr[l] > arr[r]) swap(&arr[l], &arr[r]); if (arr[l] > arr[x]) swap(&arr[l], &arr[x]); while (true) { do {j--;} while (arr[j] > arr[x]); do {i++;} while (arr[i] < arr[x]); if (i < j) { swap(&arr[i], &arr[j]); if (i == x) { x = j; } else if (j == x) { x = i; } } else { return j; } } }
template<class T> void QuickSort<T>::sort(T *arr, int l, int r) { if (r-l > 30) { int q = partition(arr, l, r); sort(arr, q+1, r); sort(arr, l, q); } else { insertsort(arr, l, r, 1); } }
// mergesort
template<class T> class MergeSort: public AbstractSort<T> { protected: void merge(T *arr, int l, int q, int r); public: void sort(T *arr, int l, int r); };
template<class T> void MergeSort<T>::merge(T *arr, int l, int q, int r) { T *target = new T[r+1]; int i, j; for(i=l; i<=q; i++) target[i] = arr[i]; for(j=q+1; j<=r; j++) target[r+q+1-j] = arr[j]; i = l; j = r; for(int k=l; k<=r; k++) { if (target[i] <= target[j]) { arr[k] = target[i]; i++; } else { arr[k] = target[j]; j--; } } delete[] target; }
template<class T> void MergeSort<T>::sort(T *arr, int l, int r) { if (l < r) { int q = (l+r)/2; sort(arr, l, q); sort(arr, q+1, r); merge(arr, l, q, r); } } ')
Hierbei handelt sich sich um Standardimplementierungen der Sortieralgorithmen, wobei allerdings, wenn ich nochmal Zeit habe, Quicksort und Mergesort noch ein Tuning vertragen. Ein B-Sort, dass auf B-Trees basiert (dieses Verfahren wird z.B. auch von MySQL zur Indexverwaltung eingesetzt), ist noch angedacht. Toppt in der Laufzeit selbst Spitzenreiter Quicksort.
Verwendung im Programm z.B.: $this->bbcode_second_pass_code('', 'HeapSort<int> hs; hs.sort(meinArray, 0, SIZE);')
Start und Ende sind als Indexposititionen anzugeben. Dieser Bereich wird dann sortiert. Übrigens GNU-kompatibel, lässt sich in UNIX-C++-Projekte genauso einbauen.
|