Basics of algorithms in computer science
Sorting Algorithms
A sorting algorithm is an algorithm that puts elements of a list in a certain order. Most frequently used orders are numerical order and alphabetical order (often referred to as “lexicographical” order).
There are numerous sorting algorithms such as:
Insertion Sort — Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. An insertion sort is less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. A simple example of insertion sort is when people manually sort cards in their hand to they have a clearer picture of how to play their cards. Insertion sorts provide several advantages:
- Simple implementation
- Efficient for very small data sets, can sort a list as it receives it
- Memory efficient
Selection Sort — The Selection sort algorithm is based on the idea of finding the minimum or maximum element in an unsorted array and then putting it in its correct position in a sorted array.
Bubble Sort — Compare and swapping two elements like small soap bubbles and hence the name given as bubble sort.
Merge Sort — Merge Sort divides an input array (numeric or alpha numeric) into two halves and then merges the two sorted halves. A merge() function is used for merging the two halves.
Quick Sort- Quick Sort is a type of “divide and conquer algorithm”. It picks an element (numeric or alphanumeric) as a pivot and then partitions the array around the pivot. There are many different methods for a quick sort to pick a pivot
o Pick the first element as pivot.
o Pick the last element as pivot
o Pick a random element as pivot.
o Pick the median as pivot.
Timsort — TimSort is a sorting algorithm that is a sort based on Insertion Sort and Merge Sort. Timsort first analyses a list that it is trying to sort and then chooses the best sorting approach based on the analysis of the list. Timsort makes use of Insertion sort and Mergesort
