“An algorithm must be seen to be believed.” – Maestro Knuth
Recommended Books (click for Amazon link)
Introduction
An algorithm is a systematic method for deterministically producing a specified result. Algorithms solve computational problems. These problems have an input which define an instance of the problem. An algorithm is an object which maps inputs/instances of the problem to solutions or outputs for this problem. Good algorithms are correct and efficient. It takes creativity to design good algorithms, and like all creative forms, mastery in algorithms comes with practice.
There are five important characteristics of algorithms:
1 – Algorithms are well-ordered.
2 – Algorithms have unambiguous operations.
3 – Algorithms have effectively computable operations.
4 – Algorithms produce a result.
5 – Algorithms halt in a finite amount of time.
Details
1 – Algorithms are well-ordered
Since an algorithm is a collection of operations or instructions, we must know the correct order in which to execute the instructions. If the order is unclear, we may perform the wrong instruction or we may be uncertain which instruction should be performed next. This characteristic is especially important for computers. A computer can only execute an algorithm if it knows the exact order of steps to perform.
2 – Algorithms have unambiguous operations
Each operation in an algorithm must be sufficiently clear so that it does not need to be simplified. Given a list of numbers, you can easily order them from largest to smallest with the simple instruction “Sort these numbers.” A computer, however, needs more detail to sort numbers. It must be told to search for the smallest number, how to find the smallest number, how to compare numbers together, etc. The operation “Sort these numbers” is ambiguous to a computer because the computer has no basic operations for sorting. Basic operations used for writing algorithms are known as primitive operations or primitives. When an algorithm is written in computer primitives, then the algorithm is unambiguous and the computer can execute it.
3 – Algorithms have effectively computable operations
Each operation in an algorithm must be doable, that is, the operation must be something that is possible to do. Suppose you were given an algorithm for planting a garden where the first step instructed you to remove all large stones from the soil. This instruction may not be doable if there is a four ton rock buried just below ground level. For computers, many mathematical operations such as division by zero or finding the square root of a negative number are also impossible. These operations are not effectively computable so they cannot be used in writing algorithms.
4 – Algorithms produce a result
In our simple definition of an algorithm, we stated that an algorithm is a set of instructions for solving a problem. Unless an algorithm produces some result, we can never be certain whether our solution is correct. Have you ever given a command to a computer and discovered that nothing changed? What was your response? You probably thought that the computer was malfunctioning because your command did not produce any type of result. Without some visible change, you have no way of determining the effect of your command. The same is true with algorithms. Only algorithms which produce results can be verified as either right or wrong.
5 – Algorithms halt in a finite amount of time
Algorithms should be composed of a finite number of operations and they should complete their execution in a finite amount of time. Suppose we wanted to write an algorithm to print all the integers greater than 1. Our steps might look something like this:
Print the number 2.
Print the number 3.
Print the number 4.
.
.
.
While our algorithm seems to be pretty clear, we have two problems. First, the algorithm must have an infinite number of steps because there are an infinite number of integers greater than one. Second, the algorithm will run forever trying to count to infinity. These problems violate our definition that an algorithm must halt in a finite amount of time. Every algorithm must reach some operation that tells it to stop.
Resources
Algorithms Fundamentals (Sedgewick and Wayne ) (website) [free]
Algorithms on reddit (website) [free]
Algorithms on stackoverflow (website) [free]
Algorithms on twitter (website) [free]
Algorithm Notes for Professionals (PDF) (257 pages) [free]
C# Algorithm Exercises with Solutions (w3resource) (website) [free] [excellent]
Understand the Concept of an Algorithm (NTU) (PPT) [free]
Analysis of Algorithms Study Guide (Princeton) (website) [free]
Data Structure and Algorithms Tutorial (TutorialsPoint) (website) [free]
Algorithms and Data Structures (Princeton) (lectures) (PDF) [free]
Study Guide for Algorithms (University of Virginia’s College at Wise) (PDF) [free]
Algorithms (University of Illinois) (PDF) [free]
Skiena’s Algorithms Lectures (video) (audio) (PDF) [free]
Quizlet Algorithms (website) [free]
Introduction to Algorithms (MIT) (course) [free]
Sort Algorithms
All code was tested in Visual Studio Community 2017…
Quick sort
using System;
namespace Quicksort
{
class Program
{
static void Main(string[] args)
{
// Create an unsorted array of string elements
string[] unsorted = { "z", "e", "x", "c", "m", "q", "a" };
// Print the unsorted array
for (int i = 0; i < unsorted.Length; i++)
{
Console.Write(unsorted[i] + " ");
}
Console.WriteLine();
// Sort the array
Quicksort(unsorted, 0, unsorted.Length - 1);
// Print the sorted array
for (int i = 0; i < unsorted.Length; i++)
{
Console.Write(unsorted[i] + " ");
}
Console.WriteLine();
Console.ReadLine();
}
public static void Quicksort(IComparable[] elements, int left, int right)
{
int i = left, j = right;
IComparable pivot = elements[(left + right) / 2];
while (i <= j)
{
while (elements[i].CompareTo(pivot) < 0) { i++; } while (elements[j].CompareTo(pivot) > 0)
{
j--;
}
if (i <= j)
{
// Swap
IComparable tmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;
i++;
j--;
}
}
// Recursive calls
if (left < j)
{
Quicksort(elements, left, j);
}
if (i < right)
{
Quicksort(elements, i, right);
}
}
}
}
Merge sort
using System;
namespace CommonInsertion_Sort
{
class Program
{
static void Main(string[] args)
{
int[] numbers = new int[12] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6, 19, 13 };
Console.WriteLine("\nOriginal Array Elements: ");
PrintIntegerArray(numbers);
Console.WriteLine("\n\nSorted Array Elements: ");
PrintIntegerArray(InsertionSort(numbers));
Console.WriteLine("\n");
Console.ReadLine();
}
static int[] InsertionSort(int[] inputArray)
{
for (int i = 0; i < inputArray.Length - 1; i++) { for (int j = i + 1; j > 0; j--)
{
if (inputArray[j - 1] > inputArray[j])
{
int temp = inputArray[j - 1];
inputArray[j - 1] = inputArray[j];
inputArray[j] = temp;
}
}
}
return inputArray;
}
public static void PrintIntegerArray(int[] array)
{
foreach (int i in array)
{
Console.Write(i.ToString() + " ");
}
}
public static int[] InsertionSortByShift(int[] inputArray)
{
for (int i = 0; i < inputArray.Length - 1; i++) { int j; var insertionValue = inputArray[i]; for (j = i; j > 0; j--)
{
if (inputArray[j - 1] > insertionValue)
{
inputArray[j] = inputArray[j - 1];
}
}
inputArray[j] = insertionValue;
}
return inputArray;
}
}
}
Heap sort
using System;
namespace Heap_sort
{
public class MainClass
{
public static void Main(string[] args)
{
int[] mykeys = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };
//double[] mykeys = new double[] {2.22, 0.5, 2.7, -1.0, 11.2};
//string[] mykeys = new string[] {"Red", "White", "Black", "Green", "Orange"};
Console.WriteLine("\nOriginal Array Elements:");
printArray(mykeys);
heapSort(mykeys);
Console.WriteLine("\n\nSorted Array Elements:");
printArray(mykeys);
Console.WriteLine("\n");
Console.ReadLine();
}
private static void heapSort<T>(T[] array) where T : IComparable<T>
{
int heapSize = array.Length;
buildMaxHeap(array);
for (int i = heapSize - 1; i >= 1; i--)
{
swap(array, i, 0);
heapSize--;
sink(array, heapSize, 0);
}
}
private static void buildMaxHeap<T>(T[] array) where T : IComparable<T>
{
int heapSize = array.Length;
for (int i = (heapSize / 2) - 1; i >= 0; i--)
{
sink(array, heapSize, i);
}
}
private static void sink<T>(T[] array, int heapSize, int toSinkPos) where T : IComparable<T>
{
if (getLeftKidPos(toSinkPos) >= heapSize)
{
// No left kid => no kid at all
return;
}
int largestKidPos;
bool leftIsLargest;
if (getRightKidPos(toSinkPos) >= heapSize || array[getRightKidPos(toSinkPos)].CompareTo(array[getLeftKidPos(toSinkPos)]) < 0) { largestKidPos = getLeftKidPos(toSinkPos); leftIsLargest = true; } else { largestKidPos = getRightKidPos(toSinkPos); leftIsLargest = false; } if (array[largestKidPos].CompareTo(array[toSinkPos]) > 0)
{
swap(array, toSinkPos, largestKidPos);
if (leftIsLargest)
{
sink(array, heapSize, getLeftKidPos(toSinkPos));
}
else
{
sink(array, heapSize, getRightKidPos(toSinkPos));
}
}
}
private static void swap<T>(T[] array, int pos0, int pos1)
{
T tmpVal = array[pos0];
array[pos0] = array[pos1];
array[pos1] = tmpVal;
}
private static int getLeftKidPos(int parentPos)
{
return (2 * (parentPos + 1)) - 1;
}
private static int getRightKidPos(int parentPos)
{
return 2 * (parentPos + 1);
}
private static void printArray<T>(T[] array)
{
foreach (T t in array)
{
Console.Write(' ' + t.ToString() + ' ');
}
}
}
}
Insertion sort
using System;
namespace CommonInsertion_Sort
{
class Program
{
static void Main(string[] args)
{
int[] numbers = new int[10] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };
Console.WriteLine("\nOriginal Array Elements:");
PrintIntegerArray(numbers);
Console.WriteLine("\n\nSorted Array Elements:");
PrintIntegerArray(InsertionSort(numbers));
Console.WriteLine("\n");
Console.ReadLine();
}
static int[] InsertionSort(int[] inputArray)
{
for (int i = 0; i < inputArray.Length - 1; i++) { for (int j = i + 1; j > 0; j--)
{
if (inputArray[j - 1] > inputArray[j])
{
int temp = inputArray[j - 1];
inputArray[j - 1] = inputArray[j];
inputArray[j] = temp;
}
}
}
return inputArray;
}
public static void PrintIntegerArray(int[] array)
{
foreach (int i in array)
{
Console.Write(i.ToString() + " ");
}
}
public static int[] InsertionSortByShift(int[] inputArray)
{
for (int i = 0; i < inputArray.Length - 1; i++) { int j; var insertionValue = inputArray[i]; for (j = i; j > 0; j--)
{
if (inputArray[j - 1] > insertionValue)
{
inputArray[j] = inputArray[j - 1];
}
}
inputArray[j] = insertionValue;
}
return inputArray;
}
}
}
Bubble sort
using System;
public class Bubble_Sort
{
public static void Main(string[] args)
{
int[] a = { 3, 0, 2, 5, -1, 4, 1 };
int t;
Console.WriteLine("\nOriginal array: ");
foreach (int aa in a)
Console.Write(aa + " ");
for (int p = 0; p <= a.Length - 2; p++)
{
for (int i = 0; i <= a.Length - 2; i++) { if (a[i] > a[i + 1])
{
t = a[i + 1];
a[i + 1] = a[i];
a[i] = t;
}
}
}
Console.WriteLine("\n\nSorted array: ");
foreach (int aa in a)
Console.Write(aa + " ");
Console.Write("\n");
Console.Read();
}
}
Counting sort
using System;
public class Counting_sort
{
public static void Main()
{
int[] array = new int[10] { 2, 5, -4, 11, 0, 8, 22, 67, 51, 6 };
Console.WriteLine("\n" + "Original array: ");
foreach (int aa in array)
Console.Write(aa + " ");
int[] sortedArray = new int[array.Length];
// find smallest and largest value
int minVal = array[0];
int maxVal = array[0];
for (int i = 1; i < array.Length; i++)
{
if (array[i] < minVal) minVal = array[i]; else if (array[i] > maxVal) maxVal = array[i];
}
// init array of frequencies
int[] counts = new int[maxVal - minVal + 1];
// init the frequencies
for (int i = 0; i < array.Length; i++)
{
counts[array[i] - minVal]++;
}
// recalculate
counts[0]--;
for (int i = 1; i < counts.Length; i++) { counts[i] = counts[i] + counts[i - 1]; } // Sort the array for (int i = array.Length - 1; i >= 0; i--)
{
sortedArray[counts[array[i] - minVal]--] = array[i];
}
Console.WriteLine("\n\n" + "Sorted array: ");
foreach (int aa in sortedArray)
Console.Write(aa + " ");
Console.Write("\n");
Console.ReadLine();
}
}
Selection sort
using System;
namespace Selection_Sort
{
class Program
{
static void Main(string[] args)
{
Selection_Sort selection = new Selection_Sort(10);
selection.Sort();
Console.Write("\n\nDone!");
Console.ReadLine();
}
}
class Selection_Sort
{
private int[] data;
private static Random generator = new Random();
//Create an array of 10 random numbers
public Selection_Sort(int size)
{
data = new int[size];
for (int i = 0; i < size; i++)
{
data[i] = generator.Next(20, 90);
}
}
public void Sort()
{
Console.Write("\nSorted Array Elements: (Step by Step)\n\n");
display_array_elements();
int smallest;
for (int i = 0; i < data.Length - 1; i++)
{
smallest = i;
for (int index = i + 1; index < data.Length; index++)
{
if (data[index] < data[smallest])
{
smallest = index;
}
}
Swap(i, smallest);
display_array_elements();
}
}
public void Swap(int first, int second)
{
int temporary = data[first];
data[first] = data[second];
data[second] = temporary;
}
public void display_array_elements()
{
foreach (var element in data)
{
Console.Write(element + " ");
}
Console.Write("\n");
Console.ReadLine();
}
}
}
Radix sort
using System;
namespace Radix_Sort
{
class Program
{
static void Sort(int[] arr)
{
int i, j;
int[] tmp = new int[arr.Length];
for (int shift = 31; shift > -1; --shift)
{
j = 0;
for (i = 0; i < arr.Length; ++i)
{
bool move = (arr[i] << shift) >= 0;
if (shift == 0 ? !move : move)
arr[i - j] = arr[i];
else
tmp[j++] = arr[i];
}
Array.Copy(tmp, 0, arr, arr.Length - j, j);
}
}
static void Main(string[] args)
{
int[] arr = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };
Console.WriteLine("\nOriginal array: ");
foreach (var item in arr)
{
Console.Write(" " + item);
}
Sort(arr);
Console.WriteLine("\n\nSorted array: ");
foreach (var item in arr)
{
Console.Write(" " + item);
}
Console.WriteLine("\n");
Console.ReadLine();
}
}
}
Bucket sort
using System;
using System.Collections.Generic;
namespace BucketSort
{
public class BucketSort
{
static void Main(string[] args)
{
// our list
int[] x = new int[] { 99, 95, 90, 85, 80, 75, 70, 65, 60, 55, 50, 45, 40, 35, 30, 25, 20, 15, 10, 5, 1 };
// sort list
List<int> sorted = Run_Sort(x);
// build list
foreach (int i in sorted)
// show list
Console.WriteLine(i);
Console.Read();
}
public static List<int> Run_Sort(params int[] x)
{
List<int> result = new List<int>();
int numOfBuckets = 10;
List<int>[] buckets = new List<int>[numOfBuckets];
for (int i = 0; i < numOfBuckets; i++)
buckets[i] = new List<int>();
for (int i = 0; i < x.Length; i++)
{
int buckitChoice = (x[i] / numOfBuckets);
buckets[buckitChoice].Add(x[i]);
}
for (int i = 0; i < numOfBuckets; i++)
{
int[] temp = BubbleSortList(buckets[i]);
result.AddRange(temp);
}
return result;
}
public static int[] BubbleSortList(List<int> input)
{
for (int i = 0; i < input.Count; i++)
{
for (int j = 0; j < input.Count; j++)
{
if (input[i] < input[j])
{
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
}
return input.ToArray();
}
}
}
Permutation sort
using System;
class Program
{
static void Main()
{
string str = "ABC";
char[] arr = str.ToCharArray();
GetPer(arr);
Console.Read();
}
private static void Swap(ref char a, ref char b)
{
if (a == b) return;
a ^= b;
b ^= a;
a ^= b;
}
public static void GetPer(char[] list)
{
int x = list.Length - 1;
GetPer(list, 0, x);
}
private static void GetPer(char[] list, int k, int m)
{
if (k == m)
{
{
Console.WriteLine(list);
}
}
else
for (int i = k; i <= m; i++)
{
Swap(ref list[k], ref list[i]);
GetPer(list, k + 1, m);
Swap(ref list[k], ref list[i]);
}
}
}
Notes
An Invitation to Computer Science textbook
tags: Algorithms, MrNetTek