Sorting in Data Structure
What is a Data Structure?
A Data Structure is a way of collecting and organising data in such a way that we can perform various operations on it.
Why Data Structure is important?
Data Structures are important because they make it easier for computers to process large, complex sets of information. By logically organising data elements, data structure increases the efficiency of computer code .
What is Sorting ?
Sorting is the process of arranging elements in ascending or descending order.
Types Of Sorting:
1. Internal Sorting:- Internal sorting takes place in the main memory of the computer. Internal sorting can takes advantages of random access of the main memory.
2. External Sorting:- External sorting is carried out on secondary storage. External sorting becomes necessity if the number of elements to be sorted is too large to fit in main memory.
Sorting Techniques / Methods:
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Quick Sort
5. Merge Sort
1.Bubble Sort :-
Bubble Sort compares each pair of adjacent elements and swaps them if they are in the wrong order.
This process repeats until the whole array is sorted.
Algorithm For Bubble Sort :-
Step 1: Set i = 1
Step 2: Repeat step 3 to step 6 while i <= n - 1
Step 3: Set j = 1
Step 4: Repeat step 5 while j <= n - i
Step 5: If a[j] > a[j + 1]
Swap a[j] and a[j + 1]
[end of if]
Set j = j + 1
[end of inner loop]
Step 6: Set i = i + 1
[end of outer loop]
Step 7: Print sorted array
Step 8: Exit
Example For Bubble Sort :-
- Simple and easy to understand
- Very easy to implement
- Requires very little memory (in-place sorting)
- Good for small datasets
- Works well for already sorted or nearly sorted arrays (optimized version)
- Useful for teaching basic sorting concepts
Disadvantages of Bubble sort:
- Simple and easy to understand
- Very easy to implement
- Requires very little memory (in-place sorting)
- Good for small datasets
- Works well for already sorted or nearly sorted arrays (optimized version)
- Useful for teaching basic sorting concepts
Code for Bubble Sort:-
#include <stdio.h>
int main() {
int arr[100], n, i, j, temp;
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter %d elements: ", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
for(i = 0; i < n - 1; i++) {
for(j = 0; j < n - i - 1; j++) {
if(arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
printf("Sorted array in ascending order: ");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output :
2.Selection sort :-
Selection Sort repeatedly selects the smallest (or largest) element from the unsorted portion and places it at the beginning (or end) of the array.
Algorithm For Selection sort :-
Step 1: Set i = 0
Step 2: Repeat step 3 to step 6 while i <= n - 2
Step 3: Set min_index = i
Step 4: Set j = i + 1
Step 5: Repeat while j <= n - 1
If a[j] < a[min_index]
min_index = j
Set j = j + 1
Step 6: Swap a[i] and a[min_index]
Step 7: Set i = i + 1
Step 8: Print sorted array
Step 9: Exit
Example For Selection Sort :-
Advantages of Selection Sort:
Simple and easy to implement
-
Performs well on small lists
-
Requires no extra memory (in-place)
Disadvantages of Selection sort :
Inefficient for large lists (O(n²) comparisons)
-
Does not adapt to already sorted arrays
-
More swaps than bubble sort in some cases
Code for Selection Sort :-
#include <stdio.h>
int main() {
int arr[100], n, i, j, min_index, temp;
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter %d elements: ", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
for(i = 0; i < n - 1; i++) {
min_index = i;
for(j = i + 1; j < n; j++) {
if(arr[j] < arr[min_index]) {
min_index = j;
}
}
temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
printf("Sorted array in ascending order: ");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output :
3.Insertion sort :-
Insertion Sort builds the sorted array one element at a time by inserting each new element into its correct position.
Algorithm For Insertion sort :-
Step 1: Set i = 1
Step 2: Repeat while i <= n - 1
key = a[i]
j = i - 1
While j >= 0 and a[j] > key
a[j + 1] = a[j]
j = j - 1
a[j + 1] = key
Set i = i + 1
Step 3: Print sorted array
Step 4: Exit
Example For Insertion Sort :-
Advantages of Insertion Sort:
- Simple and easy to implement
-
Efficient for small or nearly sorted arrays
-
Stable sorting (does not change order of equal elements)
Disadvantages of Insertion sort :
- Inefficient for large arrays (O(n²))
-
More comparisons in worst-case scenarios
Code for Insertion Sort :-
#include <stdio.h>
int main() {
int arr[100], n, i, j, key;
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter %d elements: ", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
for(i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while(j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
printf("Sorted array in ascending order: ");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output :
4.Merge sort :-
Merge Sort is a divide and conquer algorithm that divides the array into two halves, sorts them recursively, and then merges the sorted halves.
Algorithm For Merge sort :-
MERGE-SORT(A, low, high)
1. IF low >= high THEN
RETURN
2. mid = (low + high) / 2
3. MERGE-SORT(A, low, mid)
4. MERGE-SORT(A, mid + 1, high)
5. MERGE(A, low, mid, high)
6. RETURN
MERGE(A, low, mid, high)
1. n1 = mid - low + 1
2. n2 = high - mid
3. Create arrays L[1..n1] and R[1..n2]
4. FOR i = 0 to n1-1
L[i] = A[low + i]
5. FOR j = 0 to n2-1
R[j] = A[mid + 1 + j]
6. i = 0, j = 0, k = low
7. WHILE i < n1 AND j < n2
IF L[i] <= R[j] THEN
A[k] = L[i]
i = i + 1
ELSE
A[k] = R[j]
j = j + 1
k = k + 1
8. WHILE i < n1
A[k] = L[i]
i = i + 1
k = k + 1
9. WHILE j < n2
A[k] = R[j]
j = j + 1
k = k + 1
10. RETURN
Example For Merge Sort :-
Advantages of Merge Sort:
Very efficient for large datasets
-
Time complexity is O(n log n) in all cases
-
Stable sorting
-
Works well for linked lists
Disadvantages of Merge sort :
Requires extra memory for merging
-
Slightly more complex to implement than simple sorts
Code for Merge Sort :-
#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
int i, j, k;
for(i = 0; i < n1; i++)
L[i] = arr[l + i];
for(j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0; j = 0; k = l;
while(i < n1 && j < n2) {
if(L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while(i < n1) {
arr[k] = L[i];
i++; k++;
}
while(j < n2) {
arr[k] = R[j];
j++; k++;
}
}
void mergeSort(int arr[], int l, int r) {
if(l < r) {
int m = l + (r - l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[100], n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter %d elements: ", n);
for(i = 0; i < n; i++)
scanf("%d", &arr[i]);
mergeSort(arr, 0, n - 1);
printf("Sorted array in ascending order: ");
for(i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Output :
5.Quick sort :-
Quick Sort is a divide and conquer algorithm that selects a “pivot” element, partitions the array around the pivot, and recursively sorts the partitions.
Algorithm For Quick sort :-
QUICK-SORT(A, low, high)
1. IF low >= high THEN
RETURN
2. pivot = A[high]
3. pi = PARTITION(A, low, high, pivot)
4. QUICK-SORT(A, low, pi - 1)
5. QUICK-SORT(A, pi + 1, high)
6. RETURN
PARTITION(A, low, high, pivot)
1. i = low - 1
2. FOR j = low TO high - 1
IF A[j] < pivot THEN
i = i + 1
SWAP(A[i], A[j])
3. SWAP(A[i + 1], A[high])
4. RETURN i + 1
Example For Quick Sort :-
Advantages of Quick Sort:
Very efficient for large datasets
-
Average time complexity is O(n log n)
-
In-place sorting (no extra array needed)
Disadvantages of Quick sort :
Worst-case time complexity is O(n²)
-
Performance depends on pivot selection
-
Not stable
Code for Quick Sort :-
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1, j;
for(j = low; j <= high - 1; j++) {
if(arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if(low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[100], n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter %d elements: ", n);
for(i = 0; i < n; i++)
scanf("%d", &arr[i]);
quickSort(arr, 0, n - 1);
printf("Sorted array in ascending order: ");
for(i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Output :
0 Comments