Comparison of Search and Sort Techniques in ProgrammingA look at some search and sort techniques commonly used in programming, comparing their uses and performance on increasing data lengths.
There are many best methods depending on what is to be sorted, on what machine, and for what purpose.Donald Knuth
Since there are many different search and sort techniques (algorithms), software engineers must know their basic operation, relevant efficiencies, etc, to select the best one for a particular application. One efficiency criterion that gives an idea of the relationship between processing time and the array size is the simple big-O (O - Order of magnitude) calculation.
The three basic types of sorting (insertion, exchange and selection) will be compared regarding the basic differences in their operation, their relative efficiencies and how they are affected by small and large array sizes and the initially ordered state.
The different search and sort techniques (linear and binary) will be compared, and the basic operation will be outlined. This includes how the absence of the required item can be found and under what condition each would be used.
big-O Notation
The big-O Notation is also sometimes called Landau's Symbol. It is a technique used to describe the asymptotical behaviour of functions mathematically. It guides how fast the output of the function grows with the input increase. The results are relative times.
Some common big-O functions are shown below.
O(1)- ConstantO(log(n))- LogarithmicO((log(n))c)- PolylogarithmicO(n)- LinearO(n2)- QuadraticO(nc)- PolynomialO(cn)- Exponential
Sorting Techniques
Insertion Sort
The insertion sort extracts the second data element from the data. It then compares the extracted element with the next; if the next is larger, the next element is moved up an index. The extracted element then takes its place. The process is repeated until no passes are made.
If the data is almost sorted, for example, the numbers (8, 1, 2, 3, 4, 5, 6, 7, 9), then the 8 is extracted, 1 is moved to the first index, 2 into the second and so on until a number greater than 8 is encountered (or end of data). The 8 is then inserted into the data.
Generally, the maximum number of passes is given by the formula N - 1, where N is the number of data elements.
The relative time of the algorithm is O(N2) for unsorted data. As the array size increases, the algorithm's execution time increases.
using System;
public class InsertionSortExample
{
public static void Main(string[] args)
{
int[] array = { 12, 11, 13, 5, 6 };
Console.WriteLine("Original Array: " + string.Join(", ", array));
InsertionSort(array);
Console.WriteLine("Sorted Array: " + string.Join(", ", array));
}
public static void InsertionSort(int[] array)
{
int n = array.Length;
for (int i = 1; i < n; ++i)
{
int key = array[i];
int j = i - 1;
// Move elements of array[0..i-1], that are greater than key,
// to one position ahead of their current position
while (j >= 0 && array[j] > key)
{
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
} Exchange Sort
The Exchange Sort, or bubble sort, is the simplest sorting algorithm. The algorithm takes an item and compares it with the next adjacent item. If the first item exceeds the next item, they are swapped. No change is made if the first item is less than or equal to the next. There are several passes through the data.
Generally, the maximum number of passes is given by the formula N - 1, where N is the number of data elements.
The relatively short time of the algorithm is O(N2) for unsorted data.
There is also a bi-directional exchange sort that repeatedly makes a pass downwards and then upwards, sorting the data.
using System;
public class ExchangeSortExample
{
public static void Main(string[] args)
{
int[] array = { 12, 11, 13, 5, 6 };
Console.WriteLine("Original Array: " + string.Join(", ", array));
ExchangeSort(array);
Console.WriteLine("Sorted Array: " + string.Join(", ", array));
}
public static void ExchangeSort(int[] array)
{
int n = array.Length;
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (array[i] > array[j])
{
// Swap array[i] and array[j]
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
} Selection Sort
Sort data by repeatedly comparing remaining items to find the smallest and moving it to the end of the data. The effective size (area of data unsorted) is then reduced, and the process is repeated on the sub-array until the effective size is one (an array of one is sorted).
Generally, the maximum number of passes is given by the formula N - 1, where N is the number of data elements.
The relatively short time of the algorithm is O(N2) for unsorted data.
using System;
class Program
{
static void Main()
{
int[] array = { 64, 25, 12, 22, 11 };
Console.WriteLine("Sorted Array: " + string.Join(", ", array));
SelectionSort(array);
Console.WriteLine("Sorted Array: " + string.Join(", ", array));
}
static void SelectionSort(int[] array)
{
int n = array.Length;
for (int i = 0; i < n - 1; i++)
{
// Find the minimum element in the remaining unsorted array
int minIndex = i;
for (int j = i + 1; j < n; j++)
{
if (array[j] < array[minIndex])
{
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
}
} Shell Sort
The shell sort is the optimised version of the insertion sort. It takes the smallest value and moves all values above it down an index. The smallest value is then inserted at the start of the array. The process is repeated, with the next smallest value inserted below the last smallest value.
The shell sort has an average sort time of O(N1.25).
using System;
class Program
{
static void Main()
{
int[] array = { 12, 34, 54, 2, 3 };
Console.WriteLine("Original Array: " + string.Join(", ", array));
ShellSort(array);
Console.WriteLine("Sorted Array: " + string.Join(", ", array));
}
static void ShellSort(int[] array)
{
int n = array.Length;
// Start with a large gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2)
{
// Perform a gapped insertion sort for this gap size.
// The first gap elements array[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is gap sorted
for (int i = gap; i < n; i++)
{
// add array[i] to the elements that have been gap sorted
// save array[i] in temp and make a hole at position i
int temp = array[i];
// shift earlier gap-sorted elements up until the correct location for array[i] is found
int j;
for (j = i; j >= gap && array[j - gap] > temp; j -= gap)
{
array[j] = array[j - gap];
}
// put temp (the original array[i]) in its correct location
array[j] = temp;
}
}
}
} Quick sort
The Quick Sort uses the divide and conquer paradigm to sort the data. The first element is the central one. The data on the left is sorted similarly to the data on the right. The algorithm is recursive, so the data is recursively broken down into halves until it cannot be broken down further.
The quick sort has a sort time of O(n log n).
As the initial ordered state becomes sorted, the time increases.
using System;
class Program
{
static void Main()
{
int[] array = { 10, 7, 8, 9, 1, 5 };
Console.WriteLine("Original Array: " + string.Join(", ", array));
QuickSort(array, 0, array.Length - 1);
Console.WriteLine("Sorted Array: " + string.Join(", ", array));
}
static void QuickSort(int[] array, int low, int high)
{
if (low < high)
{
// Partitioning index, array[p] is now at right place
int pi = Partition(array, low, high);
// Recursively sort elements before partition and after partition
QuickSort(array, low, pi - 1);
QuickSort(array, pi + 1, high);
}
}
static int Partition(int[] array, int low, int high)
{
int pivot = array[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j < high; j++)
{
// If current element is smaller than or equal to pivot
if (array[j] <= pivot)
{
i++;
// Swap array[i] and array[j]
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// Swap array[i + 1] and array[high] (or pivot)
int temp1 = array[i + 1];
array[i + 1] = array[high];
array[high] = temp1;
return i + 1;
}
} Heap Sort
The heap sort builds a heap of the data and repeatedly extracts the maximum item.
To build the heap, the algorithm loops through all items in the array and places the value on the heap. The item is pushed into its position on the tree (highest at the top and lowest at the bottom).
When all the items have been placed in the tree, the values are extracted back into their indexes in the array.
The heap sort has an time of O(n log n)
using System;
class Program
{
static void Main()
{
int[] array = { 12, 11, 13, 5, 6, 7 };
Console.WriteLine("Original Array: " + string.Join(", ", array));
HeapSort(array);
Console.WriteLine("Sorted Array: " + string.Join(", ", array));
}
static void HeapSort(int[] array)
{
int n = array.Length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
{
Heapify(array, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--)
{
// Move current root to end
int temp = array[0];
array[0] = array[i];
array[i] = temp;
// Call max heapify on the reduced heap
Heapify(array, i, 0);
}
}
static void Heapify(int[] array, int n, int i)
{
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left = 2*i + 1
int right = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (left < n && array > array[largest])
{
largest = left;
}
// If right child is larger than largest so far
if (right < n && array > array[largest])
{
largest = right;
}
// If largest is not root
if (largest != i)
{
int swap = array[i];
array[i] = array[largest];
array[largest] = swap;
// Recursively heapify the affected sub-tree
Heapify(array, n, largest);
}
}
} Visual Analysis
The graph below shows a comparison between the O(N2) un-optimised sorts and the optimised O(n log n) and O(N1.25) sorts. The graph shows the time taken to sort the data.
The un-optimised sorts are nearly infinitely long to execute as the data size approaches 100. This would cause the algorithm to take a long time to sort the data. The time increases quadratically. (The value is about 500 seconds or 8 minutes).
On the other hand, the optimised sort algorithms still perform well with over 500 data items.
Summary of Sort Algorithms
- For small amounts of unsorted data, the basic sort types can be used.
- For Large amounts of unsorted data, the optimised types should be used
- As the Array size increases, the time taken increases
- Time increases as the data becomes more sorted
Searching Techniques
Linear Search
A linear search starts at the first data item and moves towards the last item, trying to find an item. Linear searches can be done on unsorted or sorted data; there is no difference in performance.
The absence of the item can only be found once all of the items have been looked at.
The time taken to perform the search is O(N/2).
using System;
class Program
{
static void Main()
{
int[] array = { 2, 3, 4, 10, 40 };
int target = 10;
int result = LinearSearch(array, target);
if (result != -1)
{
Console.WriteLine($"Element {target} is present at index {result}.");
}
else
{
Console.WriteLine($"Element {target} is not present in array.");
}
}
static int LinearSearch(int[] array, int target)
{
int n = array.Length;
for (int i = 0; i < n; i++)
{
if (array[i] == target)
{
return i;
}
}
return -1; // Element is not present in array
}
} Binary Search
Binary search will only work on sorted data. The technique is similar to the quick sort in that it partitions the array into progressive halves until the item is found. The array is narrowed to the lower half if the search item is less than the middle item. If the search item exceeds the middle value, the array is narrowed to the upper half.
The absence of a data item can be found easily, as the data is partitioned. The number of partitions to find the data depends on the number of data items.
The time taken to perform the search is O(Log N).
using System;
class Program
{
static void Main()
{
int[] array = { 2, 3, 4, 10, 40 };
int target = 10;
int result = BinarySearch(array, target);
if (result != -1)
{
Console.WriteLine($"Element {target} is present at index {result}.");
}
else
{
Console.WriteLine($"Element {target} is not present in array.");
}
}
static int BinarySearch(int[] array, int target)
{
int left = 0, right = array.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
// Check if target is present at mid
if (array[mid] == target)
{
return mid;
}
// If target greater, ignore left half
if (array[mid] < target)
{
left = mid + 1;
}
// If target is smaller, ignore right half
else
{
right = mid - 1;
}
}
// Target is not present in array
return -1;
}
} Visual Analysis of Search Techniques
The graph below compares the search times of the two search techniques described above. The binary search is much faster than the linear search.
Binary search should be used to sort data and many items. Linear search can be used for small amounts of unsorted data.
- Binary Search data must be sorted.
- Linear Search data can be sorted or unsorted.
