Sorting in Data Structures

Sorting data involves putting it in a certain order. It is a basic data manipulation technique that is applied to a wide range of data analysis and visualization jobs.
Depending on the type of data and the desired outcome, there are several ways for sorting data.

Typical sorting techniques include:
● Ascending order: This is the most common sorting method, and it arranges data from
smallest to largest.
● Descending order: This method arranges data from largest to smallest.
● Custom order: This method allows you to specify the order in which data is sorted.

Data sorting in programming is the process of arranging data in a specific order. This can be done in ascending or descending order and can be based on any criteria, such as the value of a variable, the date an event occurred, or the alphabetical order of a word.
There are several sorting algorithms, each with unique advantages and disadvantages. Some of the most common sorting algorithms include:
● Bubble sort
● Selection sort
● Insertion sort

Depending on the particular requirements of the application, a sorting algorithm should be chosen. For example, if the data is relatively small, then a simple algorithm like bubble sort may be sufficient. However, if the data is large or if speed is critical, then a more efficient algorithm like merge sort or quicksort should be used.

Benefits of data sorting:
● Improved data organization: Sorting data can help to improve its organization and make
it easier to find and use.
● Increased efficiency: Sorting data can help to improve the efficiency of data processing
and analysis.
● Improved accuracy: Sorting data can help to improve the accuracy of data analysis and
reporting.
● Enhanced data visualization: Sorting data can help to enhance the visualization of data,
making it easier to understand and interpret.

---

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly compares adjacent elements in an array and swaps them if they are in the wrong order.When the first two entries in the array are compared repeatedly, the algorithm swaps them if they are in the wrong order. It then compares the next two elements, and so on. This process continues until the end of the array is reached. Bubble sort is a very simple algorithm to understand and implement, but it is not very efficient. The worst-case time complexity of the technique is O(n2) means, where n is the number of items in the array and means the amount of time it takes to finish the operation. This indicates that the algorithm's execution time is inversely related to the square of the array's element count.

Bubble sort is not a good choice for sorting large arrays.However, it can be a good choice for sorting small arrays or arrays that are already partially sorted.

public class BubbleSort {
   public static void bubbleSort(int[] array) {
       int n = array.length;
          for (int i = 0; i < n - 1; i++) {
             for (int j = 0; j < n - i - 1; j++) {
                 if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                 }
             }
          }
     }

   public static void main(String[] args) {
      int[] array = {5, 3, 1, 2, 4};
      bubbleSort(array);
      for (int i = 0; i < array.length; i++) {
         System.out.print(array[i] + " ");
      }
   }
}

Advantages and disadvantages of bubble sort

Advantages:
● Bubble sort is a very simple algorithm to understand and implement.
● Bubble sort is stable, meaning that it does not change the relative order of elements
that are equal.

Disadvantages:
● Bubble sort is not very efficient, especially for large arrays.
● Bubble sort is not a good choice for sorting arrays that are already partially sorted.

---

Selection Sort

Selection sort is a simple in-place comparison sorting algorithm in computer science. It worksby dividing the input list into two parts:

1. sorted sublist
2. unsorted sublist.

The algorithm repeatedly selects the smallest (or largest) element from the unsorted sublist and swaps it with the leftmost unsorted element, thereby expanding the sorted sublist. This process continues until the entire list is sorted. Selection sort has a time complexity of O(n^2), which makes it inefficient for large lists compared to more advanced algorithms like merge sort or quicksort.

The algorithm can be summarized in the following steps:

1. Divide the input list into two sublists: the sorted sublist and the unsorted sublist.
2. Initially, the sorted sublist is empty, and the unsorted sublist contains all the elements.
3. Find the minimum (or maximum) element in the unsorted sublist.
4. Swap the minimum (or maximum) element with the leftmost element in the unsorted sublist, putting it in its correct sorted position.
5. Move the sublist boundaries one element to the right, expanding the sorted sublist and reducing the unsorted sublist.
6. Repeat steps 3 to 5 until the entire list is sorted.

public class SelectionSort {
   public static void selectionSort(int[] array) {
      int n = array.length;
      for (int i = 0; i < n - 1; i++) {
         int minIndex = i;
         for (int j = i + 1; j < n; j++) {
            if (array[j] < array[minIndex]) {
               minIndex = j;
            }
         }
         int temp = array[minIndex];
         array[minIndex] = array[i];
         array[i] = temp;
      }
   }  
   public static void main(String[] args) {
      int[] array = {10, 8, 7, 6, 5, 4, 3, 2, 1};
      selectionSort(array);
      for (int i = 0; i < array.length; i++) {
         System.out.print(array[i] + " ");
      }
   }
}

Selection sort is renowned for its simplicity and offers certain benefits when auxiliary memory is constrained. Due to its quadratic time complexity, it typically performs worse than more
sophisticated sorting algorithms on big lists. In reality, the comparable algorithm insertion sort frequently performs better than selection sort.

Here are the advantages and disadvantages of selection sort:

Advantages:
● Simple to implement - Selection sort is a straightforward algorithm that can be implemented easily in any programming language. This makes it a good choice for beginners who are learning about sorting algorithms.
● In-place sorting algorithm: Selection sort does not require any additional memory to sort the data. This makes it a good choice for applications where memory is limited.
● Can be used for small data sets: Selection sort is a relatively efficient algorithm for small data sets. However, its performance degrades significantly for large data sets.

Disadvantages:
● Slow for large data sets
● Not stable: Selection sort is not a stable sorting algorithm. This means that it can change the relative order of elements with equal values. For example, if the array [1, 2, 2, 3] is sorted using selection sort, the output could be [1, 2, 3, 2].
● Not adaptive: Selection sort is not an adaptive sorting algorithm. This means that its performance does not improve as the data becomes more sorted. For example, if the array [1, 2, 3, 4] is sorted using selection sort, the algorithm will still need to perform the same number of comparisons as if the array was [1, 100, 1000, 10000].

---

Insertion sort

The basic sorting method known as "insertion sort" involves continuously adding elements into a subarray that has already been sorted. The way the method operates is by first presuming that
the array's first element has already undergone sorting. The method then compares each succeeding element to the items in the sorted subarray. The element is placed into the appropriate location if it is smaller than any of the other items in the sorted subarray. If not, the algorithm moves on to the following element.

public class InsertionSort {
   public static void sort(int[] array) {
      int n = array.length;
      for (int i = 1; i < n; i++) {
         int key = array[i];
         int j = i - 1;
         while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
         }
         array[j + 1] = key;
      }
   }
   public static void main(String[] args) {
      int[] array = {10, 8, 7, 6, 5, 4, 3, 2, 1};
      sort(array);
      for (int i = 0; i < array.length; i++) {
         System.out.print(array[i] + " ");
      }
   }
}

Advantages and disadvantages of insertion sort:

Advantages:
● Simple to implement
● In-place sorting algorithm
● Stable sorting algorithm (elements with equal keys retain their original order)
● Efficient for small lists

Disadvantages:
● Not as efficient for large lists
● Slow for already sorted or reverse-sorted lists
● Requires O(n^2) time in the worst case

Here are some examples of when insertion sort might be a good choice:

● Sorting a small list of numbers
● Sorting a list of strings that are already in alphabetical order
● Sorting a list of records that have a primary key field

Here are some examples of when insertion sort might not be a good choice:

● Sorting a large list of numbers
● Sorting a list of strings that are not in alphabetical order
● Sorting a list of records that do not have a primary key field