In this section of the tutorial, we will discuss Sorting in Data Structures and the different sorting techniques used in performing operations in detail. We will also discuss the advantages of using Sorting algorithms in Data Structure with examples.
What is Sorting in Data Structure?
Sorting is one of the most commonly used applications in the data structure. The concept of sorting originated way back in the 1890s when a person named Herman Hollerith built an electric tabulating machine that was used in the U.S. Census in the year 1890.
Similarly, sorting techniques were first used in general-purpose computers. Sorting is one of the most important concepts in the computer world today.
- In sorting, the data values are arranged according to their values.
- There is an emphasized need of arranging data in a particular order known as sorting, in the data structure.
- It is important because it provides easy access to locate a single piece of data or information in a pool of data values.
- It saves a lot of time and memory.
Sorting Concept in Data Structure
The concept behind sorting is quite simple and mostly directed towards implementation on data-processing applications. Sorting concepts are generally categorized into two parts, i.e. internal sorts and external sorts.
- The main difference between internal and external sorts is the storage of data values in memory.
- In the internal sort, all of the data values are initially stored in primary memory during the sorting process.
- While in the external sort, the data values are initially stored in primary memory and the data that does not fit in primary memory is stored in secondary memory during the sorting process.
For example, a file containing 100 records can be sorted using an array that can hold upto 50 records. During the sorting process, only 50 data values are present in the primary memory and the rest 50 is stored in the secondary memory.
Different Sorting Techniques
As we know that Sorting is classified into two types, i.e. internal sorting and external sorting. These two categories are further divided into subcategories which include different purpose-specific sorting algorithms that are used in sorting data values in the data structure.
Bubble Sort |
Insertion Sort |
Selection Sort |
Merge Sort |
Quick Sort |
Heap Sort |
Counting Sort |
Radix Sort |
Bucket Sort |
Comb Sort |
Shell Sort |
Bitonic Sort |
Cocktail Sort |
Cycle Sort |
Tim Sort |
An example of Sorting:
Bubble Sort
In Bubble Sort, the algorithm starts by selecting the smallest unsorted item and then swapping the values in the next position to be filled.
Suppose we have a set of numbers: 13, 25, 07, 11, 02, 97
- We will find the smallest unsorted item in the list.
Step 1: 13, 25, 07, 11, 02, 97
- Here, 02 is the smallest unsorted item in the list is selected first.
Step 2: 02, 25, 07, 11, 13, 97
- Here, 02 is swapped with the first element.
- And now excluding the first element, the next smallest unsorted item 07 is selected from the remaining array.
Step 3: 02, 07, 25, 11, 13, 97
- Here, 07 is swapped with the second element.
- And now excluding upto the second element, the next smallest unsorted item 11 is selected from the remaining array.
Step 4: 02, 07, 11, 25, 13, 97
- Here, 11 is swapped with the third element.
- And now excluding upto the third element, the next smallest unsorted item 13 is selected from the remaining array.
Step 5: 02, 07, 11, 13, 25, 97
- Here, 13 is swapped with the fourth element.
Now the array is sorted by the Bubble Sort algorithm.
Order of Sorting and Sorting Stability
The order of sorting specifies that data may be stored in either ascending or descending order depending on our requirement. By default, the order of sorting is assumed to be ascending. For example, Data records sorted in ascending order in a dictionary and the telephone directory.
Sorting stability is an attribute of a sorting algorithm that specifies the data with equal keys are maintained by their relative input order in the output.
We can understand sorting stability with the help of an example given below.
Suppose we have a list of data values with their keys:
- Here, the unsorted data contains three entries with a common key, i.e. 212.
Stable Sort
- Here, the data are sorted with a stable sort.
- 212 green is the first of three outputs.
- 212 yellow is the second of three outputs.
- 212 blue is the third of three outputs.
- The output is sorted in the same order as the input order, hence it is a stable sort.
Unstable Sort
- Here, the data are not sorted with a stable sort, hence it is an unstable sort.
- 212 blue comes first of three outputs.
- 212 green comes second of three outputs.
- 212 yellow comes third of three outputs.
- The outputs are not sorted in the same order as the input order, hence it is an unstable sort.
Advantages of Sorting in Data Structure
- The sorting algorithms like bubble sort are easy to implement in solving a problem.
- The elements are swapped in place without allocating a temporary storage in sorting algorithms like bubble sort, hence saving memory space.
- Sorting algorithms like insertion sort can be used easily when handling a small list of data values.
- Sorting algorithms like quick sort can handle a large list of data items without alloating any additional storage space.
- In sorting algorithms like heap sort, the in-memory part operation of the merge can overlap with I/O operations.
Applications of Sorting in Data Structure
- Testing whether an element is unique or not in a list.
- Locating and deallocating space occupied by elements that are repeated in a list.
- Prioritizing the elements in a desired order.
- Evaluating the number of repetitions of an element in a list.
- Changing the order of elements back to its original form.
- Create intersection or union between elements in the list.
- Searching for a pair of elements to compute mathematical operations.
- Searching an element in a pool of data items of different size and class.
Examples of Sorting in Data Structure
Bubble Sort
Code:
#include<stdio.h> void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void bubble_sort(int nums[], int size) { for (int i = 0; i < size - 1; i++) { for (int j = 0; j < size - i - 1; j++) { if (nums[j] > nums[j + 1]) { swap(&nums[j],&nums[j+1]); } } } } int main() { int arr[] = {9,8,7,6,5,4,3,2,1}; int n = sizeof(arr)/sizeof(arr[0]); bubble_sort(arr,n); printf("Sorted Array \n"); for(int i = 0; i < n; i++) { printf("%d ",arr[i]); } return 0 ; }
Output:
Sorted Array 1 2 3 4 5 6 7 8 9
Insertion Sort
Code:
#include<stdio.h> void InsertionSort(int [] , int); int main() { int arr[]={8,5,10,54,-1,67,9}; int n=sizeof(arr)/sizeof(arr[0]); InsertionSort(arr, n); for(int i=0;i<n;i++) { printf("%d ",arr[i]); } return 0; } void InsertionSort(int arr[], int n) { for(int pos=1; pos<n; pos++) { int tobesort=arr[pos]; int j=pos-1; while(j>=0 && arr[j]>tobesort) { arr[j+1]=arr[j]; j--; } arr[j+1]=tobesort; } }
Output:
-1 5 8 9 10 54 67
Quick Sort
Code:
#include <stdio.h> void quick_sort(int [], int, int); int split(int [], int, int); int main() { int arr[8] = {21, 82, 73, 17, 35, 58, 64, 49}; quick_sort(arr, 0, 7); for (int i = 0; i < 8; i++) { printf("%d ",arr[i]); } printf("\n"); return 0; } void quick_sort(int a[], int start, int end) { if (start < end) { int mid = split(a, start, end); quick_sort(a, start, mid - 1); quick_sort(a, mid + 1, end); } } int split(int a[], int start, int end) { int temp; int x = a[end]; int i = start - 1; for (int j = start; j < end; j++) { if (a[j] <= x) { i++; temp = a[i]; a[i] = a[j]; a[j] = temp; } } temp = a[i+1]; a[i+1] = a[end]; a[end] = temp; return i+1; }
Output:
17 21 35 49 58 64 73 82
In the next section of the tutorial, we will discuss the Bubble Sort in Data Structure which sorts an unsorted list by comparing each item in the list with the item next to it, and swapping them if required.