SORTING AND ALGORITHM
What is a Sorting Algorithm?
So why is sorting important? Well we use it daily:
1. The way your clothes are organized
2. Where your dishes are in the kitchen
3. Your books on your bookshelf
They may not be in perfect order, but during a way that creates it easier for you to look for things.
There are many sorting algorithms for several sorts of data
1. You arrange or sort your dishes by several orders which might be the size and shape, but not alphabetically
2. You sort my books alphabetically, not by color
3. You sort post-its notes in reverse chronological order
There are many differing types of knowledge computers got to sort, a bit like within the world .
An example of a Sorting Algorithm:
Number=[6,5,4,3,2,1]
Number sort #=> [1,2,3,4,5,6]
Types of Sorting Algorithm:
They all are different in performance, which further depends on data characteristics.
- Bubble sort
- Selection sort
- Insertion sort
- Heap sort
Bubble sort
Bubble sort is a simple sorting algorithm, which is commonly used in computer science. It is through the thought of continuous repeated comparing pairs of adjacent elements then interchanging their positions if they exist in the incorrect order.
Bubble sort algorithm: on how it works:
1. In an unsorted array of 5 elements, start with the first two elements then sort them in ascending order.
2. Then compare the second and third element to check which one is greater, and then sort them in ascending order.
3. Then compare the third and fourth element to check which one is greater, and then sort them in ascending order.
4. Then compare the fourth and fifth element to check which one is greater, and then sort them in ascending order.
5. Keep repeating steps until no more swaps are required.
Bubble sort: example:
The following is an example of Bubble Sort algorithm which returns sorted array :
const array = [2, 5, 4, 3, 1];
function bubbleSort(array) {
let swapped;
do {
swapped = false;
for(let i = 0; i < array.length; i++) {
if(array[i] && array[i + 1] && array[i] > array[i + 1]) {
[array[i], array[i + 1]] = [array[i + 1], array[i]];
swapped = true;
}
}
} while(swapped);
return array;
}
Selection Sort
Selection sort is a simple sorting algorithm. It is an in-place comparison- based algorithm during which the list is split into two parts, the sorted part which is at the left end and therefore the unsorted part at the right end. Firstly, the sorted section is empty and therefore the unsorted section consists of the entire list.
The lowest element is picked from the unsorted array then replaced with the leftmost element, then that element becomes a neighbor of the sorted array. This process continues moving unsorted array boundaries by one element to the proper .
Selection sort algorithm: on how it works:
1. Iterate over the unsorted array, keeping track of the minimum value as you go.
2. Then when you get to the end of the array, you know which element is the minimum.
3. Then swap the minimum element and the first element in the unsorted array.
4. Now the first element is now considered sorted.
5. Keep repeating this until the array is sorted
Selection sort: example:
The following is an example of Selection Sort algorithm which returns sorted array :
function selectionSort(array) {
for (let i = 0; i < array. Length — 1; i++) {
// i holds the initial min number
let min = i;
// Note that j = i + 1 as we only need to go through unsorted array
for (let j = i + 1; j < length; j++) {
// Compare the numbers
if (array[j] < array[min]) {
// Change the current min number position if a smaller number
// is found
min = j;
}
}
if (min !== i) {
// exchange the position.
// Swap the numbers
let temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
return array;
}
Insertion sort
Insertion sort may be an algorithm, which sorts the array by shifting the weather one at a time. It repeats the input elements by growing the sorted array at each repetition. It compares the present element with the most important value within the sorted array. If the present element is bigger, then it leaves the element in its place and moves on to the subsequent element else it finds its correct position within the sorted array and moves it to that position. This is done by shifting all the elements, which are larger than the current element, within the sorted array to next position.
Insertion sort algorithm: on how it works:
1. If it is the first element, then it is already sorted.
2. Then pick the next element.
3. Then compare with all the elements in the sorted sub-list.
4. Then shift all the elements in the sorted sub-list that are greater than the value to be sorted.
5. Then insert the value.
6. Keep repeating this until the list is sorted.
Insertion sort: example:
The following is an example of Insertion Sort algorithm which returns sorted array :
function insertionSort(array) {
// Loop through array
for (var i = 0; i < array. length — 1; i++) {
// Create temp variable for the current element and set it equal to the
// previous element’s index.
var temp = array[i];
// Loop backwards while the index is greater than or equal to zero and
// the current element is greater than the temp variable.
for (var j = i — 1; j > -1_&& array[i] > temp; j — ) {
// Set next element equal to the current element
array(j + 1] = array[j];
}
// Set next element equal to the temp variable
array(j + 1] = temp;
}
return array;
}
Heap Sort
Heap sort is a technique based on comparison of Binary Heap data structure. It is quite the same as the selection sort in which we first find the max element and place the max element at the end. Do the same process for all of the elements.
What is Binary Heap?
Basically a Binary Heap is a Complete Binary Tree where items are stored in a particular order so that value in a parent node is greater (or smaller) than the values in its two children nodes. The first is called max-heap and the latter is called min-heap. The heap can be shown as a binary tree or array.
Why array based representation for Binary Heap?
Binary Heap is a Complete Binary Tree, it can be easily expressed as an array and the array-based expression is space-efficient. If the parent node is placed at index X, the left child can be found by 2 * X + 1 and right child by 2 * X + 2.
Heap Sort Algorithm for sorting in increasing order:
1. Make a maximum heap from the input data.
2. At this point, the highest item is stored at the top of the heap. Replace it with the bottom item of the heap and then reduce the size of the heap by 1. Then, heapify the top of the tree.
3. Keep repeating the step 2 while the size of the heap is greater than 1.
Input: 4, 10, 3, 5, 1
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
The values inside the brackets represent the respective index value in the array.
Apply heapify to index 1:
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
Apply heapify to index 0:
10(0)
/ \
5(1) 3(2)
/ \
4(3) 1(4)
The heapify process calls itself recursively to make heap
in top down manner.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
