This Repo have all information needed to study Sorting Algorithm and there is a tracer to see how the algorithm work
You can see how to algorithm run with two way you can use the button of Generate Nums to generate array and see how the algorithm work or you can enter your numbers that you want to check them by write them in the text box seperated by spaces and use button Use my Numbers to use them to see how the algorithms work
For Linux Users only
open your terminal
sudo apt install python3
sudo apt install python3-tk
git clone https://github.com/7oSkaaa/Sorting-Algorithms.git
cd Sorting-Algorithms
python3 main.py
you can download the repo as zip and extract it
OR
you can use cmd
git clone https://github.com/7oSkaaa/Sorting-Algorithms.git
go to the folder of the repo and just double click on main.exe
Sorting.Algorithms.mp4
You can read the information about each algorithm from the algorithms and go to the tracer and run it to see how the algorithm work
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Best Case is O(n)
Worst Case is O(n2)
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap list[i] and list[i + 1]
return list
end BubbleSort
void Bubble_Sort(vector < int >& nums){
int n = nums.size();
for(int i = 0; i < n - 1; i++){
bool is_sorted = true;
for(int j = 0; j < n - i - 1; j++){
if(nums[j] > nums[j + 1])
swap(nums[j], nums[j + 1]), is_sorted = false;
}
if(is_sorted) return;
}
}void swap(int *x, int *y){
int temp = *x;
*x = *y, *y = temp;
}
void bubbleSort(int* arr, int n){
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(&arr[j], &arr[j + 1]);
}def bubble_sort(data):
size = len(data)
for i in range(size - 1):
for j in range(size - i - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]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]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}const bubbleSort = (arr) => {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
}The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
- The subarray which is already sorted.
- Remaining subarray which is unsorted. In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Best Case is O(n2)
Worst Case is O(n2)
begin SelectionSort(list)
for i from 0 to n - 2 do:
min = i
for j from i + 1 to n - 1 do:
if list[j] < list[min]: Min = j
swap list[j] and list[min]
end SelectionSort
void Selection_Sort(vector < int >& nums){
int n = nums.size();
for(int i = 0; i < n - 1; i++){
int min = i;
for(int j = i + 1; j < n; j++){
if(nums[j] < nums[min])
min = j;
}
swap(nums[i], nums[min]);
}
}void swap(int *x, int *y){
int temp = *x;
*x = *y, *y = temp;
}
void selectionSort(int* arr, int n){
int i, j, min_idx;
for (i = 0; i < n - 1; i++){
min_idx = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]);
}
}```
#### Python
```Python
def selection_sort(data):
for i in range(len(data) - 1):
Min_Idx = i
for k in range(i + 1, len(data)):
if data[k] < data[Min_Idx]:
Min_Idx = kvoid selection_sort(int arr[]){
int n = arr.length;
for (int i = 0; i < n - 1; i++){
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}const selectionSort = (arr) => {
const n = arr.length;
for (let i = 0; i < n - 1; i++){
let min_idx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) min_idx = j;
}
[arr[min_idx], arr[i]] = [arr[i], arr[min_idx]];
}
}Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part. Algorithm To sort an array of size n in ascending order:
- Iterate from arr[1] to arr[n] over the array.
- Compare the current element (key) to its predecessor.
- If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
Best Case is O(n)
Worst Case is O(n2)
begin InsertionSort(list)
for i from 1 to n - 1 do:
v = list[i]
j = i - 1
while j >= 0 and list[j] > v do:
list[j + 1] = list[j]
j = j - 1
list[j + 1] = v
end SelectionSort
void Insertion_Sort(vector < int >& nums){
int n = nums.size();
for(int i = 1; i < n; i++){
int value = nums[i], j = i - 1;
while(j >= 0 && nums[j] > value)
nums[j + 1] = nums[j], j--;
nums[j + 1] = value;
}
}void insertionSort(int* arr, int n){
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}def insertion_sort(data):
for i in range(len(data)):
temp = data[i]
k = i
while k > 0 and temp < data[k - 1]:
data[k] = data[k - 1]; k -= 1
data[k] = tempvoid insertion_sort(int arr[]){
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j -= 1;
}
arr[j + 1] = key;
}
}const insertionSort = (arr) => {
const n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j -= 1;
}
arr[j + 1] = key;
}
}Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m + 1..r] are sorted and merges the two sorted sub-arrays into one. See the following C implementation for details.
Best Case is O(n x log(n))
Worst Case is O(n x log(n))
begin MergeSort(list, left, right):
if left > right
return
mid = (left+right)/2
mergeSort(list, left, mid)
mergeSort(list, mid+1, right)
merge(arr, list, mid, right)
end MergeSort
begin merge(list, left, right)
mid = (left + right) / 2
L[left ... mid]
R[mid + 1 ... right]
i = 0, j = 0, k = left
while i < len(L) and j < len(R)
if L[i] <= R[j]
list[k] = L[i]
k++, i++
else
list[k] = R[j]
k++, j++
while i < len(L) do
list[k] = L[i]
k++, i++
while(j < len(R) do
list[k] = R[j]
k++, j++
end merge
void Merge(int l, int m, int r, vector < int >& nums){
int sz_1 = m - l + 1, sz_2 = r - m;
vector < int > left(sz_1), right(sz_2);
for(int i = 0; i < sz_1; i++) left[i] = nums[l + i];
for(int i = 0; i < sz_2; i++) right[i] = nums[m + 1 + i];
int i = 0, j = 0, k = l;
while(i < sz_1 && j < sz_2)
nums[k++] = (left[i] <= right[j] ? left[i++] : right[j++]);
while(i < sz_1) nums[k++] = left[i++];
while(j < sz_2) nums[k++] = right[j++];
}
void Merge_Sort(vector < int >& nums, int l, int r){
if(l >= r) return;
int m = l + (r - l) / 2;
Merge_Sort(nums, l, m);
Merge_Sort(nums, m + 1, r);
Merge(l, m, r, nums);
}void merge(int* arr, int l, int m, int r){
int i, j, k;
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0, j = 0, k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}
void mergeSort(int* arr, int l, int r){
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}```
#### Python
```Python
def merge(data, start, mid, end):
L = data[start : mid + 1]
R = data[mid + 1: end + 1]
L_idx, R_idx, S_idx = 0, 0, start
while L_idx < len(L) and R_idx < len(R):
if L[L_idx] <= R[R_idx]:
data[S_idx] = L[L_idx]
L_idx += 1
else:
data[S_idx] = R[R_idx]
R_idx += 1
S_idx += 1
while L_idx < len(L):
data[S_idx] = L[L_idx]
L_idx += 1; S_idx += 1
while R_idx < len(R):
data[S_idx] = R[R_idx]
R_idx += 1; S_idx += 1
def merge_sort(data, start, end):
if start < end:
mid = int((start + end) / 2)
merge_sort(data, start, mid)
merge_sort(data, mid + 1, end)
merge(data, start, mid, end)void merge(int arr[], int l, int m, int r){
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int[n1];
int R[] = new int[n2];
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];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void sort(int arr[], int l, int r){
if (l < r) {
int m =l+ (r-l)/2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}const merge = (arr, l, m, r) => {
let n1 = m - l + 1;
let n2 = r - m;
let L = new Array(n1);
let R = new Array(n2);
// Copy left half to L array
for(let i = 0; i < n1; i++)
L[i] = arr[l + i];
// Copy right half to R array
for(let j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
let i = 0, j = 0;
let k = l;
// Overwrite elements in original array in the right order
while(i < n1 && j < n2) {
if(L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements in L, if exist
while(i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements in R, if exist
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
const mergeSort = (arr, l, r) => {
if (l < r) {
let m = l + Math.floor((r-l) / 2);
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
- Always pick first element as pivot.
- Always pick last element as pivot (implemented below)
- Pick a random element as pivot.
- Pick median as pivot.
Best Case is O(n x log(n))
Worst Case is O(n2)
begin quickSort(arr[], low, high)
if low < high do
pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
end quickSort
begin partition (arr[], low, high)
pivot = arr[high]
i = low - 1
for j from low to high- 1
if arr[j] < pivot
i++;
swap arr[i] and arr[j]
swap arr[i + 1] and arr[high])
return (i + 1)
}
end partition
int Partition(vector < int >& nums, int l, int r){
int pivot = nums[r], i = l;
for(int j = l; j < r; j++){
if(nums[j] <= pivot)
swap(nums[i++], nums[j]);
}
swap(nums[i], nums[r]);
return i;
}
void Quick_Sort(vector < int >& nums, int l, int r){
if(l >= r) return;
int pivot = Partition(nums, l, r);
Quick_Sort(nums, l, pivot - 1);
Quick_Sort(nums, pivot + 1, r);
}void swap(int* a, int* b){
int t = *a;
*a = *b, *b = t;
}
int partition (int* arr, int low, int high){
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++){
if (arr[j] < pivot){
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int* arr, int low, int high){
if (low < high){
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}def partition(data, start, end):
i = start + 1
pivot = data[start]
for j in range(start + 1, end + 1):
if data[j] < pivot:
data[i], data[j] = data[j], data[i]
i += 1
data[start], data[i - 1] = data[i - 1], data[start]
return i - 1
def quick_sort(data, start, end):
if start < end:
pivot_position = partition(data, start, end)
quick_sort(data, start, pivot_position - 1)
quick_sort(data, pivot_position + 1, end)int partition (int a[], int start, int end) {
int pivot = a[end];
int i = (start - 1);
for (int j = start; j <= end - 1; j++) {
if (a[j] < pivot){
i++;
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int t = a[i + 1];
a[i + 1] = a[end];
a[end] = t;
return (i + 1);
}
void quick_sort(int a[], int start, int end){
if (start < end) {
int p = partition(a, start, end);
quick_sort(a, start, p - 1);
quick_sort(a, p + 1, end);
}
} const partition = (a, start, end) => {
let pivot = a[end];
let i = (start - 1);
for(let j = start; j < end; j++) {
if (a[j] < pivot){
i++;
[a[i], a[j]] = [a[j], a[i]];
}
}
[a[i + 1], a[end]] = [a[end], a[i + 1]];
return (i + 1);
}
const quickSort = (a, start, end) => {
if(start < end) {
let partitionIndex = partition(a, start, end);
quickSort(a, start, partitionIndex - 1);
quickSort(a, partitionIndex + 1, end);
}
} 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.
Best Case is O(n + k)
Worst Case is O(n + k)
begin CountingSort(A)
for i = 0 to k do
c[i] = 0
for j = 0 to n do
c[A[j]] = c[A[j]] + 1
for i = 1 to k do
c[i] = c[i] + c[i-1]
for j = n - 1 downto 0 do
B[ c[A[j]]-1 ] = A[j]
c[A[j]] = c[A[j]] - 1
end CountingSort
void countSort(vector < int >& arr){
int max = *max_element(arr.begin(), arr.end());
int min = *min_element(arr.begin(), arr.end());
int range = max - min + 1;
vector < int > count(range), output(arr.size());
for (int i = 0; i < arr.size(); i++)
count[arr[i] - min]++;
for (int i = 1; i < count.size(); i++)
count[i] += count[i - 1];
for (int i = arr.size() - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < arr.size(); i++)
arr[i] = output[i];
}
void countSort(int* arr, int n){
int max = INT_MIN, min = INT_MAX;
int range = max - min + 1;
int count[range], output[n];
for (int i = 0; i < n; i++)
count[arr[i] - min]++;
for (int i = 1; i < range; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}def counting_sort(data):
n = max(data) + 1
count = [0] * n
for item in data:
count[item] += 1
k = 0
for i in range(n):
for j in range(count[i]):
data[k] = i
k += 1static void countSort(int[] arr){
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1;
int count[] = new int[range];
int output[] = new int[arr.length];
for (int i = 0; i < arr.length; i++)
count[arr[i] - min]++;
for (int i = 1; i < count.length; i++)
count[i] += count[i - 1];
for (int i = arr.length - 1; i >= 0; i--){
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < arr.length; i++)
arr[i] = output[i];
}const countSort = (arr) => {
const max = Math.max(...arr);
const min = Math.min(...arr);
const range = max - min + 1;
const count = new Array(range);
const output = new Array(arr.length);
for (let i = min; i <= max; i++)
count[i] = 0;
for (let i = 0; i < arr.length; i++)
count[arr[i]] += 1;
let j = 0;
for (let i = min; i <= max; i++) {
while (count[i] > 0) {
arr[j] = i;
j++;
count[i]--;
}
}
}Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements. Heap Sort Algorithm for sorting in increasing order:
- Build a max heap from the input data.
- At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of the tree.
- Repeat step 2 while the size of the heap is greater than 1.
Best Case is O(n x log(n))
Worst Case is O(n x log(n))
begin Heapify(A as array, n as int, i as int)
max = i
leftchild = 2i + 1
rightchild = 2i + 2
if (leftchild <= n) and (A[i] < A[leftchild])
max = leftchild
else
max = i
if (rightchild <= n) and (A[max] > A[rightchild])
max = rightchild
if (max != i)
swap(A[i], A[max])
Heapify(A, n, max)
end Heapify
Heapsort(A as array)
n = length(A)
for i = n/2 downto 1
Heapify(A, n ,i)
for i = n downto 2
exchange A[1] with A[i]
A.heapsize = A.heapsize - 1
Heapify(A, i, 0)
end Heapsort
void heapify(vector < int >& arr, int i){
int largest = i, l = 2 * i + 1, r = 2 * i + 2, n = arr.size();
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, largest);
}
}
void heapSort(vector < int >& arr){
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, 0);
}
}
void heapify(int* arr, int n, int i){
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int* arr, int n){
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}def heapify(data, n, i):
largest, left, right = i, 2 * i + 1, 2 * i + 2
if left < n and data[i] < data[left]:
largest = left
if right < n and data[largest] < data[right]:
largest = right
if largest != i:
data[i], data[largest] = data[largest], data[i]
heapify(data, n, largest)
def heap_sort(data):
n = len(data)
for i in range(n - 1, -1, -1):
heapify(data, n, i)
for i in range(n - 1, 0, -1):
data[i], data[0] = data[0], data[i]
heapify(data, i, 0)public void heap_sort(int arr[]){
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public void heapify(int arr[], int n, int i){
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}const heapSort = (arr) => {
const n = arr.length;
// Convert array to a heap
for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
heapify(arr, n, i);
// Iteratively pick the root of the heap and add it to the end of the array
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]
heapify(arr, i, 0);
}
}
const heapify = (arr, n, i) => {
let largest = i;
let l = 2 * i + 1;
let r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}