Bubble Sort
Basic
void BubbleSort(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
for (int j = 0; j < arr.Length - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}Optimized
Stops early if no swaps were made in a full pass — the array is already sorted.
void BubbleSortOptimized(int[] arr)
{
int n = arr.Length;
bool swapped;
do
{
swapped = false;
for (int i = 0; i < n - 1; i++)
{
if (arr[i] > arr[i + 1])
{
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
n--; // ignore the already-sorted last element
} while (swapped);
}Bidirectional (Cocktail Sort)
Passes left-to-right and right-to-left alternately, shrinking the unsorted region from both ends.
void BubbleSortBiDirectional(int[] arr)
{
bool swapped = true;
int start = 0;
int end = arr.Length - 1;
while (swapped)
{
swapped = false;
// Left to right pass
for (int i = start; i < end; i++)
{
if (arr[i] > arr[i + 1])
{
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
swapped = false;
end--;
// Right to left pass
for (int i = end - 1; i >= start; i--)
{
if (arr[i] > arr[i + 1])
{
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
start++;
}
}Recursive
Each recursive call bubbles the largest element to the end, then recurses on the remaining subarray.
void BubbleSortRecursive(int[] arr, int n)
{
if (n == 1) return; // base case
for (int i = 0; i < n - 1; i++)
{
if (arr[i] > arr[i + 1])
{
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
BubbleSortRecursive(arr, n - 1);
}Comb Sort
Improves on bubble sort by using a gap larger than 1, shrinking it by a factor of 1.3 each pass. Eliminates “turtles” (small values near the end).
void CombSort(int[] arr)
{
int n = arr.Length;
int gap = n;
float shrink = 1.3f;
bool swapped = true;
while (gap > 1 || swapped)
{
gap = (int)(gap / shrink);
swapped = false;
for (int i = 0; i + gap < n; i++)
{
if (arr[i] > arr[i + gap])
{
int temp = arr[i];
arr[i] = arr[i + gap];
arr[i + gap] = temp;
swapped = true;
}
}
}
}Odd-Even Sort
Alternates between comparing odd-indexed pairs and even-indexed pairs until no swaps occur. Useful for parallel processing.
void OddEvenSort(int[] arr)
{
bool sorted = false;
int n = arr.Length;
while (!sorted)
{
sorted = true;
// Odd pass
for (int i = 1; i < n - 1; i += 2)
{
if (arr[i] > arr[i + 1])
{
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
sorted = false;
}
}
// Even pass
for (int i = 0; i < n - 1; i += 2)
{
if (arr[i] > arr[i + 1])
{
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
sorted = false;
}
}
}
}Gnome Sort
Moves forward if elements are in order; swaps and steps back if not. Simple but slow — similar to insertion sort.
void GnomeSort(int[] arr)
{
int i = 1;
int n = arr.Length;
while (i < n)
{
if (i == 0 || arr[i - 1] <= arr[i])
{
i++;
}
else
{
int temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
i--;
}
}
}Selection Sort
Ascending
void SelectionSortAscending(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[minIndex])
minIndex = j;
}
if (minIndex != i)
{
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}Descending
void SelectionSortDescending(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
int maxIndex = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] > arr[maxIndex])
maxIndex = j;
}
if (maxIndex != i)
{
int temp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = temp;
}
}
}Bidirectional (Cocktail Selection Sort)
Finds both min and max in each pass, placing them at both ends simultaneously.
void SelectionSortBiDirectional(int[] arr)
{
int left = 0;
int right = arr.Length - 1;
while (left < right)
{
int minIndex = left;
int maxIndex = right;
for (int i = left; i <= right; i++)
{
if (arr[i] < arr[minIndex]) minIndex = i;
if (arr[i] > arr[maxIndex]) maxIndex = i;
}
// Place minimum at left
int tempMin = arr[minIndex];
arr[minIndex] = arr[left];
arr[left] = tempMin;
// If max was at left, it has now moved to minIndex
if (maxIndex == left) maxIndex = minIndex;
// Place maximum at right
int tempMax = arr[maxIndex];
arr[maxIndex] = arr[right];
arr[right] = tempMax;
left++;
right--;
}
}Stable
Standard selection sort is unstable (e.g. {2,3,2,1} swaps non-adjacent equal elements). This version shifts elements instead of swapping, preserving relative order.
void SelectionSortStable(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[minIndex])
minIndex = j;
}
int minValue = arr[minIndex];
// Shift elements right instead of swapping
for (int k = minIndex; k > i; k--)
{
arr[k] = arr[k - 1];
}
arr[i] = minValue;
}
}Recursive
void SelectionSortRecursive(int[] arr, int startIndex)
{
if (startIndex >= arr.Length - 1) return;
int minIndex = startIndex;
for (int i = startIndex + 1; i < arr.Length; i++)
{
if (arr[i] < arr[minIndex])
minIndex = i;
}
if (minIndex != startIndex)
{
int temp = arr[minIndex];
arr[minIndex] = arr[startIndex];
arr[startIndex] = temp;
}
SelectionSortRecursive(arr, startIndex + 1);
}Insertion Sort
Ascending
Builds a sorted region one element at a time by inserting each new element into its correct position.
void InsertionSortAscending(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int current = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > current)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
}Descending
void InsertionSortDescending(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int current = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] < current)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
}Recursive
void InsertionSortRecursive(int[] arr, int startIndex)
{
if (startIndex >= arr.Length) return;
int current = arr[startIndex];
int j = startIndex - 1;
while (j >= 0 && arr[j] > current)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
InsertionSortRecursive(arr, startIndex + 1);
}Shell Sort
A generalization of insertion sort that sorts elements far apart first, reducing the amount of shifting needed. Gap starts at n/2 and halves each pass.
void ShellSort(int[] arr)
{
int n = arr.Length;
int gap = n / 2;
while (gap > 0)
{
for (int i = gap; i < n; i++)
{
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
{
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
gap /= 2;
}
}