Learning Different Sorting Technique in DS & Algorithm

As you all Know from my Previous Story that my Internship is going on at Internity Foundation, And Today I have learned about the Different Sorting Technique in DSA Internship. Sorting Technique is very important to sort all the Arrays Efficiently in Increasing or Decreasing Order.

What is Sorting?

Sorting is arranging the elements in some logical order, logical order could
be increasing or decreasing. Sorting is nothing but systematic arrangement of the data based. The systematic arrangement

means based on some key the data should be arranged.

Types of sorting

Internal sorting and External sorting

1. Internal Sorting:

Sort can be done in main memory, so that the number of elements is relatively small (less

than a million).

2. External Sorting:

Sorts that cannot be performed in main memory and must be done on disk or tape are also

quite important. This type of sorting, known as external sorting

Topics covered:

1. Bubble sort

2. Insertion sort

3. Selection sort

4. Count Sort

5. Shell sort

6. Heap sort

7. Merge sort

8. Quick sort

9. Radix sort

10. Bucket sort

11. Dutch National Flag sort

Bubble sort:

Bubble is a simple and well-known sorting algorithm.

It is used in practice once in a blue moon and its main application is to make an introduction to

the sorting algorithm.

Algorithm:

1. Compare each pair of adjacent elements from the beginning of an array, if they are in

reversed order, swap them.

2. It at least one swap has been done, repeat step

Example. Sort {5, 1, 12, -5, 16} using bubble sort.

Pseudo Code:

bool isSorted(int *arr){
int i = 0;
for(i=0;i<n-1;i++)
{
if(arr[i]>arr[i+1])
return false;
}
return true;
}

void bubbleSort(int *arr){
int sizeOfArray = sizeof(arr)/sizeof(arr[0]); O(1) (Space)
int *temp = new int[sizeof(arr)/sizeof(arr[0])];[][][][][]
bool flag = false; → O(1)
for (int i=0; i<n-1;i++){ → O(1)
for(int j = 0; j<n-i-1; j++){ → O(1)
if(arr[j]<arr[j+1]){
flag = true;
swap(arr[j],arr[j+1]);
}
}
if(flag==false)
return;
}
}

Time Complexity :

In Worst case O(N²)

In best case O(N)

Space Complexity
O(1)

2. Selection Sort

The idea of algorithm is quite simple. Array is imaginary divided into two parts — sorted one and unsorted one. At the beginning, sorted part is empty, while unsorted one contains whole array. At every step, algorithm finds smallest element in the unsorted part and adds it to the end of the sorted one. When unsorted part becomes empty, algorithm stops.

When algorithm sorts an array, it swaps first element of unsorted part with minimal element and then it is included to the sorted part. This implementation of selection sort in not stable.

In case of linked list is sorted, and, instead of swaps, minimal element is linked to the unsorted part,

selection sort is stable.

The algorithm work as follows:

1. Set the first position as current position

2. Find the minimum value in the list

3. Swap it with the value in the current position

4. Set next position as current position

5. Repeat steps 2- 4 until you reach end of list.

Let us see an example of sorting an array to make the idea of selection sort clearer.

Example. Sort {5, 1, 12, -5, 16, 2, 12, 14} using selection sort.

0 1 2 3 4 5 6 7 8
[9,8,7,6,5,4,3,2,1] → original array

minimum is 1
minIndex = 8
swap(arr[i],arr[minIndex])
0 1 2 3 4 5 6 7 8
[1,8,7,6,5,4,3,2,9] → 1st Iteration

Now search space is from i = 1 to 8
minimum is 2
minIndex = 7
[1,2,7,6,5,4,3,8,9] → 2nd Iteration

Now search space is from i = 2 to 8
0 1 2 3 4 5 6 7 8
[1,2,7,6,5,4,3,8,9]
minimum is 3
minIndex = 6
[1,2,3,6,5,4,7,8,9] → 3rd Iteration

0 1 2 3 4 5 6 7 8
[1,2,3,6,5,4,7,8,9] i = 3 to 8
minimum is 4
minIndex = 5
0 1 2 3 4 5 6 7 8
[1,2,3,4,5,6,7,8,9]

0 1 2 3 4 5 6 7 8
[1,2,3,4,5,6,7,8,9] i = 4 to 8

…
…
… Same Index swapping

pseudo code :

void selectionSort(int *arr){
int n = sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<n-1;i++){
int minIndex = -1;
int minElement = INT_MAX;
for(int j = i;j<n;j++){
if(minElement>arr[j]){
minIndex = j;
minElement = arr[j];
}
}
swap(arr[i],arr[midIndex]);
}
}

Complexity :

Time Complexity → O(N²)

Space Complexity → O(1)

Current Code constraint is arr[n-1]<INT_MAX;

3. Counting Sort :

Counting sort is a stable sorting technique, which is used to sort objects according to the keys that are small numbers. It counts the number of keys whose key values are same. This sorting technique is effective when the difference between different keys are not so big, otherwise, it can increase the space complexity.

The complexity of counting Sort Technique

• Time Complexity: O(n+r)
• Space Complexity: O(n+r)

Input and Output

Input:
A list of unsorted data: 2 5 6 2 3 10 3 6 7 8
Output:
Array before Sorting: 2 5 6 2 3 10 3 6 7 8
Array after Sorting: 2 2 3 3 5 6 6 7 8 10

Algorithm

counting sort(array, size)

Input: An array of data, and the total number in the array

Output: The sorted Array

Begin
   max = get maximum element from array.
   define count array of size [max+1]
   for i := 0 to max do
      count[i] = 0 //set all elements in the count array to 0
   done
   for i := 1 to size do
      increase count of each number which have found in the array
   done
   for i := 1 to max do
      count[i] = count[i] + count[i+1] //find cumulative frequency
   done
   for i := size to 1 decrease by 1 do
      store the number in the output array
      decrease count[i]
   done
   return the output array
End

Example

#include<iostream>
#include<algorithm>
using namespace std;
void display(int *array, int size) {
   for(int i = 1; i<=size; i++)
      cout << array[i] << " ";
   cout << endl;
}
int getMax(int array[], int size) {
   int max = array[1];
   for(int i = 2; i<=size; i++) {
      if(array[i] > max)
         max = array[i];
   }
   return max; //the max element from the array
}
void countSort(int *array, int size) {
   int output[size+1];
   int max = getMax(array, size);
   int count[max+1]; //create count array (max+1 number of elements)
   for(int i = 0; i<=max; i++)
      count[i] = 0; //initialize count array to all zero
   for(int i = 1; i <=size; i++)
      count[array[i]]++; //increase number count in count array.
   for(int i = 1; i<=max; i++)
      count[i] += count[i-1]; //find cumulative frequency
   for(int i = size; i>=1; i--) {
      output[count[array[i]]] = array[i];
      count[array[i]] -= 1; //decrease count for same numbers
   }
   for(int i = 1; i<=size; i++) {
      array[i] = output[i]; //store output array to main array
   }
}
int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n+1]; //create an array with given number of elements
   cout << "Enter elements:" << endl;
   for(int i = 1; i<=n; i++) {
      cin >> arr[i];
   }
   cout << "Array before Sorting: ";
   display(arr, n);
   countSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

Output

Enter the number of elements: 10
Enter elements:
2 5 6 2 3 10 3 6 7 8
Array before Sorting: 2 5 6 2 3 10 3 6 7 8
Array after Sorting: 2 2 3 3 5 6 6 7 8 10