Sorting-Algorithms - All information about sorting algorithm you need and you can visualize the code tracer

Overview

Sorting-Algorithms

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

Requirements

For Linux Users only

open your terminal

sudo apt install python3
sudo apt install python3-tk

How to run

Linux

git clone https://github.com/7oSkaaa/Sorting-Algorithms.git
cd Sorting-Algorithms
python3 main.py

Windows

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

Video:

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

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Time Complexity

Best Case is O(n)

Worst Case is O(n2)

Pseudocode

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

Code

C++

void Bubble_Sort(vector < int >& nums){
    int n = nums.size();
    for(int i = 0; i < n; i++){
        bool is_sorted = true;
        for(int j = i; j < n; j++){
            if(nums[j] < nums[i])
                swap(nums[i], nums[j]), is_sorted = false;
        }
        if(is_sorted) return;
    }
}

Python

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]

Java

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;
            }
}

Selection Sort

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.

  1. The subarray which is already sorted.
  2. 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.

Time Complexity

Best Case is O(n2)

Worst Case is O(n2)

Pseudocode

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

Code

C++

void Selection_Sort(vector < int >& nums){
    int n = nums.size();
    for(int i = 0; i < n; i++){
        int min = i;
        for(int j = i + 1; j < n; j++){
            if(nums[j] < nums[min])
                min = j;
        }
        swap(nums[i], nums[min]);
    }
}

Python

def selection_sort(data, drawData, timeTick):
    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 = k

Java

void 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;
    }
}

Insertion Sort

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:

  1. Iterate from arr[1] to arr[n] over the array.
  2. Compare the current element (key) to its predecessor.
  3. 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.

Time Complexity

Best Case is O(n2)

Worst Case is O(n2)

Pseudocode

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

Code

C++

void Insertion_Sort(vector < int >& nums){
    int n = nums.size();
    for(int i = 0; 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;
    }
}

Python

def insertion_sort(data, drawData, timeTick):
    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] = temp

Java

void 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;
    }
}

Merge Sort

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.

Time Complexity

Best Case is O(n x log(n))

Worst Case is O(n x log(n))

Pseudocode

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

Code

C++

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);
}

Python

def merge(data, start, mid, end, drawData, timeTick):
    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)

Java

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);
    }
}

Quick Sort

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.

  1. Always pick first element as pivot.
  2. Always pick last element as pivot (implemented below)
  3. Pick a random element as pivot.
  4. Pick median as pivot.

Time Complexity

Best Case is O(n x log(n))

Worst Case is O(n2)

Pseudocode

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

Code

C++

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);
}

Python

def partition(data, start, end, drawData, timeTick):
    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, drawData, timeTick):
    if start < end:
        pivot_position = partition(data, start, end, drawData, timeTick)
        quick_sort(data, start, pivot_position - 1, drawData, timeTick)
        quick_sort(data, pivot_position + 1, end, drawData, timeTick)

Java

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(a, start, p - 1);  
        quick(a, p + 1, end);  
    }
}  

Counting Sort

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.

Time Complexity

Best Case is O(n + k)

Worst Case is O(n + k)

Pseudocode

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

Code

C++

void countSort(vector < int >& nums){
    int max = *max_element(nums.begin(), nums.end());
    int min = *min_element(nums.begin(), nums.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];
}

Python

def counting_sort(data, drawData, timeTick):
    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 += 1

Java

static 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];
}

Heap Sort

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:

  1. Build a max heap from the input data.
  2. 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.
  3. Repeat step 2 while the size of the heap is greater than 1.

Time Complexity

Best Case is O(n x log(n))

Worst Case is O(n x log(n))

Pseudocode

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

Code

C++

void heapify(vector < int >& nums, int i){
    int largest = i, l = 2 * i + 1, r = 2 * i + 2, n = nums.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, n, largest);
    }
}

void heapSort(vector < int >& nums){
    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);
    }
}

Python

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)

Java

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);
   }
}

FingerPy is a algorithm to measure, analyse and monitor heart-beat using only a video of the user's finger on a mobile cellphone camera.

FingerPy is a algorithm using python, scipy and fft to measure, analyse and monitor heart-beat using only a video of the user's finger on a m

Thiago S. Brasil 37 Oct 21, 2022
How on earth can I ever think of a solution like that in an interview?!

fuck-coding-interviews This repository is created by an awkward programmer who always struggles with coding problems on LeetCode, even with some Easy

Vinta Chen 613 Jan 08, 2023
Algorithmic Trading with Python

Source code for Algorithmic Trading with Python (2020) by Chris Conlan

Chris Conlan 1.3k Jan 03, 2023
A tictactoe where you never win, implemented using minimax algorithm

Unbeatable_TicTacToe A tictactoe where you never win, implemented using minimax algorithm Requirements Make sure you have the pygame module along with

Jessica Jolly 3 Jul 28, 2022
Visualisation for sorting algorithms. Version 2.0

Visualisation for sorting algorithms v2. Upped a notch from version 1. This program provides animates simple, common and popular sorting algorithms, t

Ben Woo 7 Nov 08, 2022
A genetic algorithm written in Python for educational purposes.

Genea: A Genetic Algorithm in Python Genea is a Genetic Algorithm written in Python, for educational purposes. I started writing it for fun, while lea

Dom De Felice 20 Jul 06, 2022
Implementation for Evolution of Strategies for Cooperation

Moraliser Implementation for Evolution of Strategies for Cooperation Dependencies You will need a python3 (= 3.8) environment to run the code. Before

1 Dec 21, 2021
Leveraging Unique CPS Properties to Design Better Privacy-Enhancing Algorithms

Differential_Privacy_CPS Python implementation of the research paper Leveraging Unique CPS Properties to Design Better Privacy-Enhancing Algorithms Re

Shubhesh Anand 2 Dec 14, 2022
This is an Airport Scheduling Time table implemented using Genetic Algorithm

This is an Airport Scheduling Time table implemented using Genetic Algorithm In this The scheduling is performed on the basisi of that no two Air planes are arriving or departing at the same runway a

1 Jan 06, 2022
This repository explores an implementation of Grover's Algorithm for knights on a chessboard.

Grover Knights Welcome to my Knights project! Project Description: I explore an implementation of a quantum oracle for knights on a chessboard.

Will Sun 8 Feb 22, 2022
Tic-tac-toe with minmax algorithm.

Tic-tac-toe Tic-tac-toe game with minmax algorithm which is a research algorithm his objective is to find the best move to play by going through all t

5 Jan 27, 2022
Primedice like provably fair algorithm

Primedice like provably fair algorithm

Ryu juheon 3 Dec 02, 2022
Sorting-Algorithms - All information about sorting algorithm you need and you can visualize the code tracer

Sorting-Algorithms - All information about sorting algorithm you need and you can visualize the code tracer

Ahmed Hossam 15 Oct 16, 2022
Benchmark for Robustness Tests of Control Alrogithms

A gym-like classical control benchmark for evaluating the robustnesses of control and reinforcement learning algorithms.

Kim Taekyung 4 Jan 18, 2022
N Queen Problem using Genetic Algorithm

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

Mahdi Hassanzadeh 2 Nov 11, 2022
This repository provides some codes to demonstrate several variants of Markov-Chain-Monte-Carlo (MCMC) Algorithms.

Demo-of-MCMC These files are based on the class materials of AEROSP 567 taught by Prof. Alex Gorodetsky at University of Michigan. Author: Hung-Hsiang

Sean 1 Feb 05, 2022
Algorithmic virtual trading using the neostox platform

Documentation Neostox doesnt have an API Support, so this is a little selenium code to automate strategies How to use Clone this repository and then m

Abhishek Mittal 3 Jul 20, 2022
Implementation of Apriori Algorithm for Association Analysis

Implementation of Apriori Algorithm for Association Analysis

3 Nov 14, 2021
Ralebel is an interpreted, Haitian Creole programming language that aims to help Haitians by starting with the fundamental algorithm

Ralebel is an interpreted, Haitian Creole programming language that aims to help Haitians by starting with the fundamental algorithm

Lub Lorry Lamysère 5 Dec 01, 2022
CLI Eight Puzzle mini-game featuring BFS, DFS, Greedy and A* searches as solver algorithms.

🕹 Eight Puzzle CLI Jogo do quebra-cabeças de 8 peças em linha de comando desenvolvido para a disciplina de Inteligência Artificial. Escrito em python

Lucas Nakahara 1 Jun 30, 2021