Sorting Algorithm Concepts

Sorting Algorithms

A Sorting Algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists. Sorting is also useful for sorting data and for producing human readable output.

Algorithms differ in various ways, such as their speed (in O(n)), their stability (such as cards of a certain type sorted in the right positions), stacks and heap sizes.

We will take a look at the popular Sorting Algorithms, separated into categories, These are:

Simple Sorts
Efficient Sorts
Bubble Sorts
Distribution Sorts

Simple Sorts

Most sorting algorithms that people know are the Insertion Sort and the Selection Sort. Both of these are best used in sorting small lists and are both used as components of larger, more sophisticated algorithms. The Insertion sort builds the final sorted array one item at a time, and whilst the algorithm runs, an element is selected in the array and is then compared with the first element in the array and if the first element is bigger then the selected element is put towards the front of the array.

An Example of how Insertion Sort works in JavaScript - Here is the given code:


							function insertionSort(items){
	
	for(var i=0; i<items.length; i++){

		let value = items[i];
		//stores current item value

		for(var j=(i-1); j>-1 && items[j] > value; j--){
			//loop through items in sorted array (from current to the beginning)
			//copy each item to the next one

			items[j+1] = items[j];

		}

		//the last item we've reached should now hold the value of the currently sorted item

		items[j+1] = value;

	}

	return items;

}

const array = [5,9,13,4,1,6];
console.log(insertionSort(array));

// result is [1,4,5,6,9,13]

This is what is going on with the array:


							Start: [5,9,13,4,1,6]

At array[0] (= 5)
No Change.

At array[1] (= 9)
No Swap: [5,9,13,4,1,6] // 9 > 5

At array[2] (= 13)
No Swap: [5,9,13,4,1,6] // 13 > 9

At array[3] (= 4)
Swap: [4,5,9,13,1,6] // compare all to 4, 4 moves up to front

At array[4] (= 1)
Swap: [1,4,5,9,13,6] // compare all to 1, 1 moves up to front

At array[5] (= 6)
Swap: [1,4,5,6,9,13] // first smaller item is 5, place 6 after it

End: [1,4,5,6,9,13]

If the first smaller item in the array is found then both elements are swapped, else there is no swap.

Selection sorts are similar to insertion sorts but they find the smallest element first and swap it with the first element, and then finding the second smallest element and swapping it with the second element, etc

Efficient Sorts

Practical sorting algorithms are almost always based on a algorithm with average time complexity, of which most common are, heap sort, merge sort and quicksort. Each one has advantages and disadvantages, with the most significant being that simple implementatio of merge sort uses O(n) additional space, and simple implementation of quicksort has O(n^2) worst-case complexity. These problems can be solved or sortedd at the cost of a more complex algorithm. These algorithms are usually used in real world data, and modifications of these are usually used to produce the best reslts.

An Example of how merge sort works in Java - Here is the given code:


							class mergeSort{
	
	void merge(int arr[], int l, int m, int r){

		int n1 = m - l + 1;
		int n2 = r - m;

		// Create Temp Arrays
		int L[] = new int[n1];
		int R[] = new int[n2];

		// Copy data to temp arrays
		for(int i=0; i<n1; ++i){
			L[i] = arr[l + i];
		}
		for(int j=0; j<n2; ++j){
			R[j] = arr[m + 1 + j];
		}

		// Merge the temp arrays

		// Initial index of merged subarray array
		int k = l;
		while(i &l; n1 && j < n2){

			if(L[i] <= R[j]){

				arr[k] = L[i];
				i++;

			} else {

				arr[k] = R[j];
				j++;

			}
			k++;

		}

		// Copy remaining elements of L[] if any
		while(i < n1){

			arr[k] = L[i];
			i++;
			k++;

		}

		// Copy remaining elements of R[] if any
		while(j < n2){

			arr[k] = R[j];
			j++;
			k++;

		}

	}



//Main function that sorts arr[l..r] using merge()
void sort(int arr[], int l, int r){
	
	if(l < r){

		//Find the middle point
		int m = (l+r)/2;

		//Sort first and second halves
		sort(arr,l,m);
		sort(arr,m+1,r);

		//Merge the sorted halves
		merge(arr,l,m,r);

	}

}

//Print array of size n
static void printArray(int arr[]){
	
	int n = arr.length;
	for(int i=0; i<n; ++i){

		System.out.print(arr[i] + " ");

	}
	System.out.println();

}

//Driver method
public static void main(String args[]){
	
	int arr[] = {12,11,13,5,6,7};

	System.out.println("Given Array");
	printArray(arr);

	MergeSort ob = new MergeSort();
	ob.sort(arr,0,arr.length-1);

	System.out.println("\nSorted Array");
	printArray(arr);

}

}

This is how the array is being reconstructed here:


							Start: [12,11,13,5,6,7]

Split array as evenly as possible

- [12,11,13] || [5,6,7]

Split both arrays as evenly as possible again

- [12,11] | [13] || [5,6] | [7]

Split both arrays as evenly as possible again until you reach just elements

- [12] [11] | [13] || [5] [6] | [7]

Now all elements are ready to be merged, you compare both of them in the way way you broke them up
Find the minimum of 12 and 11 for example and then merge them in ascending order

- [11,12] | [13] || [5,6] | [7]

- [11,12,13] || [5,6,7]

Now to merge both back together, select the minimum of both subarrays and the minimum of both is to be the first element
Do this for each element to get a fully merged and sorted array.

minL = 11, minR = 5 min of both = 5

- [5]

minL = 11, minR = 6, min of both = 6

- [5,6]

etc, until

- [5,6,7,11,12,13]

End: [5,6,7,11,12,13]

Merge Sort is quite a complex algorithm but makes sense once you get used to it and it is rather fun in the end. The other efficient algorithms such as Quicksort and Shellsort use slightly different methods but are also used in everyday applications.

Bubble Sorts

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This method is extremely slow compared to the other algorithms.

An Example of how Bubble Sort works in Java - Here is the given code:


							public class BubbleSort{
	
	void bubbleSort(int arr[]){

		int n = arr.length;
		for(int i=0; i<n-1; i++){

			for(int j=0; j<n-i-1; j++){

				if(arr[j] > arr[j+1]){

					// swap arr[j+1] and arr[i]
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;

				}

			}	

		}

	}

	void printArray(int arr[]){

		int n = arr.length;
		for(int i=0; i<n; ++i){

			System.out.print(arr[i] + " ");

		}
		System.out.println();

	}

	//Driver method of test above
	public static void main(String args[]){

		BubbleSort ob = new BubbleSort();
		int arr[] = {19,3,2,56,34,5,10};
		ob.bubbleSort(arr);
		System.out.println("Sorted array");
		ob.printArray(arr);

	}

}

This is how the array is being sorted in steps:


							Start: [19,3,2,56,34,5,10]

Starting at position 0, we compare positions 0 and 1, if the 0th number is bigger than the 1st number then both are swapped

19 and 3 compared

Swap: [3,19,2,56,34,5,10]

The next 2 positions are compared (1 and 2) etc...

19 and 2 compared

Swap: [3,2,19,56,34,5,10]

19 and 56 compared

No Swap: [3,2,19,56,34,5,10]

56 and 34 compared

Swap: [3,2,19,34,56,5,10]

56 and 5 compared

Swap: [3,2,19,34,5,56,10]

56 and 10 compared

Swap: [3,2,19,34,5,10,56]

We now know that 56 is the last element as its the biggest, the limit of the array is now position arr.length-2

Limit: [3,2,19,34,5,10|56]; "|" denotes the limit line in the array, elements to the right of this line do not get compared

We now start the process again from 0th position comparing 0 and 1 positions until position 5.

3 and 2 compared etc

Swap: [2,3,19,34,5,10|56];
No Swap: [2,3,19,34,5,10|56];
No Swap: [2,3,19,34,5,10|56];
Swap: [2,3,19,5,34,10|56];
Swap: [2,3,19,5,10,34|56];

34 is now the 2nd biggest and the limit is now position arr.length-3.

Limit: [2,3,19,5,10|34,56];

Repeat until array is sorted...

No Swap: [2,3,19,5,10|34,56];
No Swap: [2,3,19,5,10|34,56];
Swap: [2,3,5,19,10|34,56];
Swap: [2,3,5,10,19|34,56];

Limit: [2,3,5,19|19,34,56];

No Swap: [2,3,5,10|19,34,56];
No Swap: [2,3,5,10|19,34,56];
No Swap: [2,3,5,10|19,34,56];

Limit: [2,3,5|10,19,34,56];

No Swap: [2,3,5|10,19,34,56];
No Swap: [2,3,5|10,19,34,56];

Limit: [2,3|5,10,19,34,56];

No Swap: [2,3|5,10,19,34,56];

Limit: [2|3,5,10,19,34,56];

End: [2,3,5,10,19,34,56]

As you can see, the Bubble Sort algorithm has sorted the array, through a long, but simple process in comparing and swapping elements depending on the conditions set. There are lots of differently modified Bubble Sort methods that you should look up.

Distribution Sort

Distribution Sorting algorithms refer to any sorting algorithm where data is distributed from their input to multiple intermediate structures which are then gathered and placed on the output. For example, both bucket sort and flash sort are distribution based sorting algorithms. Distribution sorting algorithms can be used on a single processor, or they can be a distributed algorithm, where individual subsets are separately sorted on different processors, then combined. This allows external sorting of data too large to fit into a single computer's memory.

An Example of how the Counting Sort Algorithm works in JavaScript - Here is the given code:


							let countingSort = (arr,min,max) =>{
	
	let i = min,
		j = 0,
		len = arr.length,
		count = [];

	for(i; i&let;=max; i++){

		count[i] = 0;

	}

	for(i=0; i&let;len; i++){

		count[arr[i]] += 1;

	}

	for(i=min; i<=max; i++){

		while(count[i] > 0){

			arr[j] = i;
			j++;
			count[i]--;

		}

	}

	return arr;
};

var array = [8,4,2,1,0,7,3,4];

console.log(countingSort(array,0,8));

Counting Sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence. Radix Sort, another distribution sorting algorithm can be visually shown if you would like to know how these types of algorithms work.

These are the main sorting algorithm concepts.