Introduction to Sorting in DAA

DAA: What is Sorting?

The technique in which a data structure is rearranged in decreasing order, increasing order, or in a specified order is called sorting.

We apply to sort in our day-to-day lives in various ways. In real life, sorting is seen in:

1.  Ranking based on scores
2.  People standing in a queue according to their heights
3.  A dictionary or telephone directory in which words are sorted alphabetically.

In technical terms, the concept of sorting is applied to linear data structures such as Arrays, LinkedList, Stack, Queues, and many more.

Applications of Sorting

Some important applications of sorting are as follows:

1. Efficiently search an item: When all the items will be arranged in an order, it is easy to search for an item.
2. Commercial computing: Industrial and governmental organizations use enhanced sorting-based techniques to manage their databases. It becomes easier to sort the data according to time, place, date, identity number, etc.
3. String processing: String algorithms are mostly based on sorting. We can arrange a string in order of their ASCII values.
4.  Numerical computations: Numerical computations focus on approximate close answers to a given problem statement. The priority queue uses various sorting algorithms to get accurate results.

Sorting Algorithms

When we write a sorting algorithm, efficiency and time complexity are the two major points to be kept in mind. The algorithm should work correctly and should have less execution time. A programmer uses the correct algorithm to escape from the TLE( time limit exceeded) issue. On this note, the various sorting algorithms are listed below -

1. Selection sort
2. Bubble sort
3. Insertion sort
4. Merge sort
5. Heapsort
6. Quicksort
7. Radix sort
8. Shell sort
9. Counting sort
10. Comb sort

Now let us discuss each sorting algorithm in detail -

DAA SELECTION SORT

The algorithm is a comparison-based in-place algorithm in which the array is divided into two parts as:

1. The sorted part at the left end.
2. The unsorted part at the right end.

Initially, the unsorted part is the entire array, and the sorted part is zero as we had not sorted our array.

Algorithm:

Select the smallest element from the unsorted part and swap with the leftmost element, and that element becomes a part of the sorted array. This process repeats for n iterations till the whole array is sorted.

Time complexity

O(n^2)  as there are two nested loops.

Space complexity

 O(1). 

C++ Code:

 #include <bits/stdc++.h>
 using namespace std;
 void swap(int *xp, int *yp)
 {
          int temp = *xp;
          *xp = *yp;
          *yp = temp;
 }
 void selectionSort(int arr[], int n)
 {
          int i, j, min_idx;
           for (i = 0; i < n-1; i++)  // Iterate through the entire array
          {
                       min_idx = i;
                    for (j = i+1; j < n; j++)     /* From the unsorted part
                     minimal element is found*/
                    if (arr[j] < arr[min_idx])
                             min_idx = j;
          // Swap minimum element from unsorted part and first element
                    swap(&arr[min_idx], &arr[i]);
          }
 }
 // This function prints the array
 void printArray(int arr[], int size)
 {
          int i;
          for (i=0; i < size; i++)
                    cout << arr[i] << " ";
          cout << endl;
 }
 int main()
 {
          int arr[] = {64, 25, 12, 22, 11};
          int n = 5;
          selectionSort(arr, n);
          cout << "Sorted array: \n";
          printArray(arr, n);
          return 0;
 } 

C code:

 #include <stdio.h>
 void swap(int *xp, int *yp)
 {
          int temp = *xp;
          *xp = *yp;
          *yp = temp;
 }
 void selectionSort(int arr[], int n)
 {
          int i, j, min_idx;
          for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
          {
                    // From the unsorted section find minimum element
                    min_idx = i;
                    for (j = i+1; j < n; j++) //Iterate through inner loop to compare
                    if (arr[j] < arr[min_idx])
                             min_idx = j;
                                       swap(&arr[min_idx], &arr[i]);
          }
 }
 void printArray(int arr[], int size)
 {
          int i;
          for (i=0; i < size; i++)
                    printf("%d ", arr[i]);
          printf("\n");
 }
 int main()
 {
          int arr[] = {64, 25, 12, 22, 11};
          int n = 5;
          selectionSort(arr, n);
          printf("Sorted array: \n");
          printArray(arr, n);
          return 0;
 } 

Java code:

 class SelectionSort
 {
          void 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;
          // Swap minimum element from unsorted part and first element
                             int temp = arr[min_idx];
                             arr[min_idx] = arr[i];
                             arr[i] = temp;
                    }
          }
           void printArray(int arr[])
          {
                    int n = arr.length;
                    for (int i=0; i<n; ++i)
                             System.out.print(arr[i]+" ");
                    System.out.println();
          }
                    public static void main(String args[])
          {
                    SelectionSort ob = new SelectionSort();
                    int arr[] = {64,25,12,22,11};
                    ob.sort(arr);
                    System.out.println("Sorted array");
                    ob.printArray(arr);
          }
 }