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

This is the code repository for 40 Algorithms Every Programmer Should Know , published by Packt.

40 Algorithms Every Programmer Should Know, published by Packt

Packt 721 Jan 02, 2023
A litle algorithm that i made for transform a picture in a spreadsheet.

PicsToSheets How it works? It is an algorithm designed to transform an image into a spreadsheet file. this converts image pixels to color cells of she

Guilherme de Oliveira 1 Nov 12, 2021
Implementation of Apriori Algorithm for Association Analysis

Implementation of Apriori Algorithm for Association Analysis

3 Nov 14, 2021
A library for benchmarking, developing and deploying deep learning anomaly detection algorithms

A library for benchmarking, developing and deploying deep learning anomaly detection algorithms Key Features • Getting Started • Docs • License Introd

OpenVINO Toolkit 1.5k Jan 04, 2023
Repository for Comparison based sorting algorithms in python

Repository for Comparison based sorting algorithms in python. This was implemented for project one submission for ITCS 6114 Data Structures and Algorithms under the guidance of Dr. Dewan at the Unive

Devashri Khagesh Gadgil 1 Dec 20, 2021
FPE - Format Preserving Encryption with FF3 in Python

ff3 - Format Preserving Encryption in Python An implementation of the NIST approved FF3 and FF3-1 Format Preserving Encryption (FPE) algorithms in Pyt

Privacy Logistics 42 Dec 16, 2022
Using A * search algorithm and GBFS search algorithm to solve the Romanian problem

Romanian-problem-using-Astar-and-GBFS Using A * search algorithm and GBFS search algorithm to solve the Romanian problem Romanian problem: The agent i

Mahdi Hassanzadeh 6 Nov 22, 2022
A Python program to easily solve the n-queens problem using min-conflicts algorithm

QueensProblem A program to easily solve the n-queens problem using min-conflicts algorithm Performances estimated with a sample of 1000 different rand

0 Oct 21, 2022
frePPLe - open source supply chain planning

frePPLe Open source supply chain planning FrePPLe is an easy-to-use and easy-to-implement open source advanced planning and scheduling tool for manufa

frePPLe 385 Jan 06, 2023
Solving a card game with three search algorithms: BFS, IDS, and A*

Search Algorithms Overview In this project, we want to solve a card game with three search algorithms. In this card game, we have to sort our cards by

Korosh 5 Aug 04, 2022
Path finding algorithm visualizer with python

path-finding-algorithm-visualizer ~ click on the grid to place the starting block and then click elsewhere to add the end block ~ click again to place

izumi 1 Oct 31, 2021
A fast python implementation of the SimHash algorithm.

This Python package provides hashing algorithms for computing cohort ids of users based on their browsing history. As such, it may be used to compute cohort ids of users following Google's Federated

Hybrid Theory 19 Dec 15, 2022
A minimal implementation of the IQRM interference flagging algorithm for radio pulsar and transient searches

A minimal implementation of the IQRM interference flagging algorithm for radio pulsar and transient searches. This module only provides the algorithm that infers a channel mask from some spectral sta

Vincent Morello 6 Nov 29, 2022
Python Package for Reflection Ultrasound Computed Tomography (RUCT) Delay And Sum (DAS) Algorithm

pyruct Python Package for Reflection Ultrasound Computed Tomography (RUCT) Delay And Sum (DAS) Algorithm The imaging setup is explained in these paper

Berkan Lafci 21 Dec 12, 2022
Python algorithm to determine the optimal elevation threshold of a GNSS receiver, by using a statistical test known as the Brown-Forsynthe test.

Levene and Brown-Forsynthe: Test for variances Application to Global Navigation Satellite Systems (GNSS) Python algorithm to determine the optimal ele

Nicolas Gachancipa 2 Aug 09, 2022
8 Puzzle with A* , Greedy & BFS Search in Python

8_Puzzle 8 Puzzle with A* , Greedy & BFS Search in Python Python Install Python from here. Pip Install pip from here. How to run? 🚀 Install 8_Puzzle

I3L4CK H4CK3l2 1 Jan 30, 2022
Zipline, a Pythonic Algorithmic Trading Library

Zipline, a Pythonic Algorithmic Trading Library

Stefan Jansen 463 Jan 08, 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
Distributed algorithms, reimplemented for fun and practice

Distributed Algorithms Playground for reimplementing and experimenting with algorithms for distributed computing. Usage Running the code for Ring-AllR

Mahan Tourkaman 1 Oct 16, 2022
Code for generating alloy / disordered structures through the special quasirandom structure (SQS) algorithm

Code for generating alloy / disordered structures through the special quasirandom structure (SQS) algorithm

Bruno Focassio 1 Nov 10, 2021