Sorts-Archived

⚠️ Deprecated Notice

This repository is deprecated and is no longer actively maintained. For the latest version, please refer to the updated repository here.

📌 Introduction

This repository contains various sorting algorithms discussed in the ADP (Algorithmen, Datenstrukturen und Programmierung) lecture.

The primary goal of this repository is to:

• Visualize and analyze inefficient coding practices in sorting algorithms.
• Understand algorithmic evolution and how sorting efficiency can be improved.
• Provide implementations of various classic sorting algorithms for educational purposes.

Supported Algorithms

• BubbleSort
• SelectionSort
• InsertionSort
• MergeSort (multiple versions)
• QuickSort
• HeapSort

💡 The main branch contains the fixed and corrected versions of the algorithms, while the feature branches include insufficient or inefficient versions, often with commented explanations.

Key Points to Note

MergeSort Implementation

• The MergeSort.java implementation should use a global auxiliary array that is instantiated only once, improving memory usage by avoiding unnecessary allocations during recursive calls.

  private int[] aux; // Global auxiliary array, instantiated once
  

• The NaturalMergeSortGlobal.java implementation merges elements using three distinct cases: (x = last written element ).

  1. If both elements >= x, then choose the smaller of the two.
  2. If both elements < x, then there is a jump, i.e. a new run. Start the new run with the smaller element.
  3. If one element >= x, the other <= x, then select the element >= x to extend the current run.

  🚨 Important: The first condition must use >= (greater than or equal to) instead of > (strictly greater). Otherwise, the algorithm suffers from performance degradation when dealing with duplicate values, as frequent collisions slow down sorting.