Selection sort:
using System;
namespace Whittle.Sorting.Selection {
class Selection<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Selection"; }
}
override public void Sort(T[] items) {
int n = items.Length;
int iMin;
for (int i = 0; i < n; i++) {
iMin = i;
for (int j = i+1; j < n; j++) {
if (items[j].CompareTo(items[iMin]) < 0) {
iMin = j;
}
}
if (iMin != i) {
Swap(items, iMin, i);
}
}
}
}
}
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
Insertion sort
using System;
namespace Whittle.Sorting.Insertion {
class Insertion<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Insertion"; }
}
override public void Sort(T[] items) {
int n = items.Length;
for (int i = 1; i < n; i++) {
T value = items[i];
int j = i - 1;
Boolean done = false;
do {
if (items[j].CompareTo(value) > 0) {
items[j + 1] = items[j];
j--;
if (j < 0) {
done = true;
}
} else {
done = true;
}
} while (done == false);
items[j + 1] = value;
}
}
}
}
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
Quick sort
using System;
namespace Whittle.Sorting.Exchange {
class Quick<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Quick"; }
}
override public void Sort(T[] items) {
Quicksort(items, 0, items.Length - 1);
}
private void Quicksort(T[] array, int left, int right) {
if (right > left) {
int pivotIndex = left + (right - left) / 2;
pivotIndex = Partition(array, left, right, pivotIndex);
Quicksort(array, left, pivotIndex - 1);
Quicksort(array, pivotIndex + 1, right);
}
}
private int Partition(T[] array, int left, int right, int pivotIndex) {
T pivotValue = array[pivotIndex];
int storeIndex = left;
Swap(array, pivotIndex, right);
for (int i = left; i < right; i++) {
if (array[i].CompareTo(pivotValue) <= 0) {
Swap(array, i, storeIndex);
storeIndex++;
}
}
Swap(array, storeIndex, right);
return storeIndex;
}
}
}
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
OddEven sort
using System;
namespace Whittle.Sorting.Exchange {
class OddEven<T>: Sorts<T> where T : IComparable {
override public string Name {
get { return "Odd-Even"; }
}
override public void Sort(T[] items) {
int n = items.Length;
Boolean sorted = false;
while (sorted == false) {
sorted = true;
for (int i = 1; i < n - 1; i += 2) {
if (items[i].CompareTo(items[i + 1]) > 0) {
Swap(items, i, i + 1);
sorted = false;
}
}
for (int i = 0; i < n - 1; i += 2) {
if (items[i].CompareTo(items[i + 1]) > 0) {
Swap(items, i, i + 1);
sorted = false;
}
}
}
}
}
}
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
Gnome sort
using System;
namespace Whittle.Sorting.Exchange {
class Gnome<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Gnome"; }
}
override public void Sort(T[] items) {
int n = items.Length;
int pos = 1;
while (pos < n) {
if (items[pos].CompareTo(items[pos - 1]) > 0) {
pos++;
} else {
Swap(items, pos, pos - 1);
if (pos > 1) {
pos--;
} else {
pos++;
}
}
}
}
}
}
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
Comb sort
using System;
namespace Whittle.Sorting.Exchange {
class Comb<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Comb"; }
}
override public void Sort(T[] items) {
double shrink_factor = 1.247330950103979;
int gap = items.Length;
bool swapped = true;
int i;
while ((gap > 1) || swapped) {
if (gap > 1) gap = (int)(gap/ shrink_factor);
swapped = false;
i = 0;
while (gap + i < items.Length) {
if (items[i].CompareTo(items[i+gap]) > 0) {
Swap(items, i, i + gap);
swapped = true;
}
i++;
}
}
}
}
}
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
Cocktail sort
using System;
namespace Whittle.Sorting.Exchange {
class Cocktail<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Cocktail"; }
}
override public void Sort(T[] items) {
int begin = -1;
int end = items.Length - 2;
Boolean swapped;
do {
swapped = false;
begin++;
for (int i = begin; i <= end; i++) {
if (items[i].CompareTo(items[i + 1]) > 0) {
Swap(items, i, i + 1);
swapped = true;
}
}
if (swapped == false) {
break;
}
swapped = false;
end--;
for (int i = end; i >= begin; i--) {
if (items[i].CompareTo(items[i + 1]) > 0) {
Swap(items, i, i + 1);
swapped = true;
}
}
} while (swapped);
}
}
}
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
Bubble sort
using System;
namespace Whittle.Sorting.Exchange {
class Bubble<T> :Sorts<T> where T : IComparable {
override public string Name {
get { return "Bubble"; }
}
override public void Sort(T[] items) {
int n = items.Length;
do {
int newn = 0;
for (int i = 0; i < n - 1; i++) {
if (items[i].CompareTo(items[i + 1]) > 0) {
Swap(items, i, i + 1);
newn = i + 1;
}
}
n = newn;
} while (n > 1);
}
}
}
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
Heap Sort
using System;
namespace Whittle.Sorting.Selection {
class Heap<T> : Sorts<T> where T : IComparable {
public override string Name {
get { return "Heap"; }
}
public override void Sort(T[] array) {
Heapify(array, array.Length);
int end = array.Length - 1;
while (end > 0) {
Swap(array, end, 0);
SiftDown(array, 0, end - 1);
end--;
}
}
public void Heapify(T[] array, int count) {
int start = count / 2 - 1;
while (start >= 0) {
SiftDown(array, start, count - 1);
start--;
}
}
public void SiftDown(T[] array, int start, int end) {
int root = start;
while (root * 2 + 1 <= end) {
int child = root * 2 + 1;
int swap = root;
if (array[swap].CompareTo(array[child]) < 0) {
swap = child;
}
if (child < end && array[swap].CompareTo(array[child + 1]) < 0) {
swap = child + 1;
}
if (swap != root) {
Swap(array, root, swap);
root = swap;
} else {
break;
}
}
}
}
}
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
Shell sort
using System;
namespace Whittle.Sorting.Insertion {
class Shell<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Shell"; }
}
override public void Sort(T[] items) {
int n = items.Length;
int inc = n / 2;
while (inc > 0) {
for (int i = inc; i < n; i++) {
T temp = items[i];
int j = i;
while (j >= inc && items[j - inc].CompareTo(temp) > 0) {
items[j] = items[j - inc];
j -= inc;
}
items[j] = temp;
}
inc = (int)(inc / 2.2);
}
}
}
}
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
Great! It teaches me a lot to see your class design.
This is my own humble contribution from a time ago http://www.daniweb.com/code/snippet217212.html
My BubbleSort is a bit different and I have a sort called straight insertion sort.
Maybe you could add them to your collection.
I found it always fun to know how these things work, but as your testdata show, if you really want to sort .NET is way ahead. :)
ddanbe
Senior Poster
3,829 posts since Oct 2008
Reputation Points: 2,070
Solved Threads: 661
Your bubble sort is an unoptimized bubble sort, so it's not much different.
The two insertions sorts are basically the same. The difference being that yours starts from the beginning of the array to find where to place the item (then pushes all the items down) while mine starts at the end (effectively) and moves each item until it finds the spot where the new item should go.
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
