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
- 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 10Algorithm
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