Scribd
Upload
17 views21 pages

C Sorting Algorithms: Selection, Bubble, Quick, Merge, Insertion

The document contains multiple C implementations of sorting algorithms including Selection Sort, Bubble Sort, Quick Sort, Insertion Sort, and Merge Sort. Each algorithm is explained with its respective code and time complexity analysis. Additionally, the document highlights the characteristics and efficiency of each sorting method.

Uploaded by

Gayu Ks
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views21 pages

C Sorting Algorithms: Selection, Bubble, Quick, Merge, Insertion

The document contains multiple C implementations of sorting algorithms including Selection Sort, Bubble Sort, Quick Sort, Insertion Sort, and Merge Sort. Each algorithm is explained with its respective code and time complexity analysis. Additionally, the document highlights the characteristics and efficiency of each sorting method.

Uploaded by

Gayu Ks
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Code:1 Selection_SORT.

#include<stdio.h>
#define SIZE 5

void swap(int *x, int *y)


{
int temp = *x;
*x = *y;
*y = temp;
}
void selectionSort(int arr[],int size)
{
int i,j;

for(i = 0; i < size-1; i++)


{
for(j = i+1; j < size; j++)
{
if(arr[i] > arr[j])
swap(&arr[i],&arr[j]);
}
}

int main()
{
int arr[SIZE] = {180,165,150,170,145},i;

selectionSort(arr,SIZE);

printf("After selection sort\n");


for(i = 0; i < SIZE; i++)
printf("%d ",arr[i]);

return 0;

}
After STEP-2 to n-1
/* Program : Bubble sort * Language : C */
#include<stdio.h>
#define size 5

void swap(int *x, int *y)


{
int temp = *x;
*x = *y;
*y = temp;
}

void bubbleSort(int arr[])


{
int i,j;
for(i = 0; i < size-1; i++)
{
for(j = 0; j < size-1-i; j++)
{
if(arr[j] > arr[j+1])
swap(&arr[j],&arr[j+1]);
}
}
}

int main()
{
int arr[size] = {50, 25, 5, 20, 10}, i;
bubbleSort(arr);
printf("After the bubble sort\n");
for(i = 0; i < size; i++)
printf("%d ",arr[i]);
return 0;
}
#include<stdio.h>
int partition(int arr[], int low, int high)
{
int temp;
int pivot = arr[high]; // assuming last element of the array as the pivot element
int i = (low - 1); // assuming the index of i pointer as one position less than the first element
for (int j = low; j <= high - 1; j++) // assuming the index of j pointer as the first position
{
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of i pointer and swap the elemets at index i and j
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swapping the pivot (last) element and element at i + 1 index
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// returning the index of pivot element having lesser elements to the left and greater elements to the right
return (i + 1);
}
void quick_sort(int arr[], int low, int high)
{
if (low < high) {
// partitioning the single array into two sub-arrays
int pi = partition(arr, low, high);
// sorting the sub-arrays
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{ printf("%d ", arr[i]); }
}

int main()
{
int n, i;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{ scanf("%d", &arr[i]); }
quick_sort(arr, 0, n - 1);
print(arr, n);
}
/* Program : QuickSort Language : C /

#include<stdio.h>

void quickSort(int[], int, int);


int partition(int[], int, int);
void swap(int*, int*);

int main()
{
int n,i;
printf("Enter Array Size\n");
scanf("%d",&n);
int arr[n];
printf("Enter Array Elements\n");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
quickSort(arr,0,n-1);
printf("After the QuickSort\n");
for(i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");
return 0;
}

void quickSort(int arr[], int start, int end)


{
if(start < end)
{
int pIndex = partition(arr, start, end);
quickSort(arr, start, pIndex-1);
quickSort(arr, pIndex+1, end);
}
}

int partition(int arr[], int start, int end)


{
int pIndex = start;
int pivot = arr[end];
int i;
for(i = start; i < end; i++)
{
if(arr[i] < pivot)
{
// swap(&arr[i], &arr[pIndex]);
pIndex++;
}
}
swap(&arr[end], &arr[pIndex]);
return pIndex;
}

void swap(int *x, int *y)


{
int t = *x;
*x = *y;
*y = t;
}
Time Complexity of Quick Sort
Since similar to Merge sort, Quick sort follows divide and conquer algorithm, its complexity in average and best case is same as that
of Merge sort which is O(nlogn).

Whereas in the worst case, its complexity is O(n2). This occurs when the given array is nearly or completely sorted.

Important Note: Time complexity of the quick sort algorithm is dependent on the pivot chosen. If the pivot is close to the median or
the array, then the number of comparisons required to sort the array are less in number.
Insertion Sort Algorithm
Insertion sort is slightly different from the other sorting algorithms. It is based on the idea that each element in the array
arra
is consumed in each iteration to find its right position in the sorted array such that the entire array is sorted at the end
of all the iterations.
#include<stdio.h>
int main()
{
int i, n, j, temp, min, key;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{ scanf("%d", &arr[i]); }
for (i = 1; i < n; i++)
{ key = arr[i];
j = i - 1;
// comparing whether the first element is greater than the second element
// if yes, then store the largest element to the next position
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
// storing the smallest element in the correct position
arr[j + 1] = key;
}
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}

Insertion Sort Time Complexity


Similar to Bubble sort and Selection sort, the time complexity of Insertion sort is also O(n). This is because, in the worst case, i.e
when the given array is in the exact reverse order as that of the output, each element has to be compared with all the n elements in the
sorted array. So this makes it n*n.

 Best case time-complexity:O(n). This occurs when the given array is already sorted.
 Worst case time complexity:O(n)
 Space Complexity:O(1)
Merge Sort Algorithm
In Merge sort, the given array is sorted using Divide and Conquer algorithm. This algorithm divides the input array into sub- sub
arrays (until each sub array contains one element
lement only) and then recursively sorts the sub
sub-arrays.
arrays. The sorted sub-arrays
sub are then
merged back together to form a single sorted array. This is where Merge sort differs from all other sorting algorithms.

A simple visualization of this is shown below.

Let us consider an array A={4, 8, 13, 2, 23, 16}.


The working of Merge sort for this array of elements is shown below
below.
#include <stdio.h>
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
int main()
{
int a[30],n,i;
printf("Enter no of elements:");
scanf("%d",&n);
printf("Enter array elements:");
for(i=0;i<n;i++) scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("\nSorted array is :");
for(i=0;i<n;i++) printf("%d ",a[i]);
return 0;
}

void mergesort(int a[],int i,int j)


{
int mid;
if(i<j)
{ mid=(i+j)/2;
mergesort(a,i,mid); //left recursion
mergesort(a,mid+1,j); //right recursion
merge(a,i,mid,mid+1,j); } //merging of two sorted sub-arrays
}

void merge(int a[],int i1,int j1,int i2,int j2)


{
int temp[50]; //array used for merging
int i,j,k;
i=i1; //beginning of the first list
j=i2; //beginning of the second list
k=0;
while(i<=j1 && j<=j2) //while elements in both lists
{
if(a[i]<a[j]) temp[k++]=a[i++];
else temp[k++]=a[j++];
}
while(i<=j1) //copy remaining elements of the first list
temp[k++]=a[i++];
while(j<=j2) //copy remaining elements of the second list
temp[k++]=a[j++];
//Transfer elements from temp[] back to a[]
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
}

Merge Sort Time Complexity


Here the array consists of 6 elements. So, the number of sub-arrays formed with a single element in it is 6. Then those 6 sub-arrays are
merged to 4 sub-arrays. To do this we need 6 append (adding of elements) operations.

Append operation: Comparing the elements and inserting them in sorted order.

Then those 4 sub-arrays are merged to 2 sub-arrays. Again here comes another 6 append operations.

Then those 2 sub-arrays to 1 single sorted array. Another 6 append operations required to do this.

Total 6 + 6+ 6 = 18 append operations. This is the total complexity of the entire merge sort. If the number of array elements keeps
increasing, then append operations will also increase. So, in general, total complexity can be (n * log n)
Insertion sort

#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
This implementation takes an integer array arr and its length n as arguments. It then iterates over
the array from index 1 to n-1 and inserts each element into its correct position in the sorted subarray
to the left of it. The algorithm uses a key variable to temporarily store the current element being
sorted and shifts the elements in the sorted subarray to the right until it finds the correct position to
insert the key element.

Note that insertion sort is not the most efficient sorting algorithm and may not be suitable for large
arrays. Other sorting algorithms such as quicksort or merge sort may be more efficient for larger
arrays.

MERGE SORTING
This implementation takes an integer array arr and its length n as arguments. It then recursively
divides the array into halves until each subarray contains only one element. It then merges the
subarrays by comparing the elements in each subarray and putting them in order into a new array.

Note that merge sort is an efficient sorting algorithm but may require additional memory to store the
subarrays during the merging process.

Common questions

Powered by AI

QuickSort and Merge Sort both utilize the divide and conquer strategy but implement it differently. QuickSort first partitions the array around a pivot such that elements less than the pivot are on one side and those greater are on the other, then recursively applies this partitioning to the subarrays . This often results in non-uniform partitions based on the pivot's position, affecting the balance of recursion. Merge Sort, in contrast, divides the array into two equal halves, sorts each half, and merges them back together, ensuring balanced partitions . While both achieve O(n log n) average time complexities, QuickSort is typically faster in practice due to in-place partitioning without additional space requirements, whereas Merge Sort needs extra space for merging .

Merge Sort uses a divide and conquer approach, recursively dividing the array into halves until subarrays of one element are achieved, then merges these subarrays in a sorted manner to produce the final sorted array . This is different from algorithms like Selection Sort and Bubble Sort, which make in-place comparisons and swaps within a single pass through the list . Merge Sort's approach also contrasts with QuickSort, which also divides the array but does so based on a pivot element, leading to potentially less balanced partitions . Merge Sort consistently achieves O(n log n) time complexity due to its balanced division and merging strategy, unlike QuickSort and Insertion Sort which can degrade to O(n^2) in the worst case .

Bubble Sort's iterative nature results in a simplistic, but less efficient sorting process compared to recursive algorithms like QuickSort and Merge Sort. Bubble Sort repeatedly steps through the array, comparing adjacent elements and swapping them if needed, leading to a time complexity of O(n^2) in the average and worst case as each element potentially traverses the array multiple times . Recursive algorithms like QuickSort and Merge Sort efficiently divide and conquer the array, reducing the number of necessary comparisons by exploiting array partitioning and sorting at multiple levels simultaneously . This allows them to achieve O(n log n) time complexity on average, making them more suitable for larger datasets where Bubble Sort's performance would degrade significantly.

QuickSort often outperforms Merge Sort in practice due to its in-place partitioning that minimizes overhead. While both have an average time complexity of O(n log n), QuickSort generally requires fewer data movements due to its use of a well-chosen pivot to partition the array without the need for additional storage . This lack of need for auxiliary space during partitioning translates to lower memory usage and cache efficiency advantages, making QuickSort faster for systems with memory constraints. Conversely, Merge Sort's merging process requires additional memory allocation for temporary subarrays, which can become a bottleneck for large datasets or memory-limited environments . QuickSort's adaptability to different partition strategies allows it to outperform Merge Sort on average.

Insertion Sort is considered inefficient for large datasets because its average and worst-case time complexity is O(n^2). This quadratic time complexity makes it significantly slower on larger inputs compared to QuickSort and Merge Sort, both of which have an average time complexity of O(n log n). While Insertion Sort is efficient on small or partially sorted datasets due to its O(n) best-case scenario, its performance degrades markedly with input size, making it unsuitable for large datasets where more efficient algorithms like QuickSort and Merge Sort are preferable .

In Merge Sort, the merging process is crucial for achieving a sorted array. After recursively dividing the array into single-element subarrays, the merge step involves comparing elements from two subarrays and combining them into a single sorted subarray . This is done by iterating over both subarrays and inserting the smaller element into a temporary array, which is eventually copied back into the original array. This merging operation ensures that the left and right halves of the array are combined in sorted order, producing a fully sorted array by the end of the algorithm . The merging process is what differentiates Merge Sort from other sorting algorithms that sort subarrays separately without a merging step.

Merge Sort has a space complexity of O(n) because it requires additional memory for the temporary arrays used during the merge process . In contrast, Insertion Sort has a space complexity of O(1), as it sorts the array in place without requiring additional storage . The difference arises because Merge Sort needs to maintain subarrays for merging, thus requiring extra space, whereas Insertion Sort reorganizes elements within the existing array.

The choice of pivot in QuickSort significantly affects its time complexity. When the pivot is close to the median of the array, QuickSort performs efficiently with an average time complexity of O(n log n). However, if the pivot is poorly chosen, such as the smallest or largest element in a nearly sorted array, the performance degrades to O(n^2) since it leads to unbalanced partitions . This makes the efficiency of QuickSort heavily reliant on the pivot selection strategy, which determines the number of comparisons required to sort the array.

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order, with the largest unsorted element bubbling to the end after each pass . Selection Sort, on the other hand, divides the list into a sorted and unsorted part, repeatedly finding the minimum element from the unsorted section and placing it at the end of the sorted section . Both algorithms have a worst-case and average time complexity of O(n^2), but Bubble Sort makes more swaps than Selection Sort, making Selection Sort generally more efficient in practice despite their theoretically similar complexities .

Using a fixed small array size in Selection Sort and Bubble Sort examples simplifies the code and demonstration of algorithm mechanics but limits practical applicability. Small, fixed arrays make the code easy to understand and the algorithms' operations easy to follow visually . However, this approach restricts the test cases to a narrow set of data, which may not showcase the algorithms' inefficiencies such as high time complexity in worst-case scenarios or scalability issues on larger datasets. This could lead to an underestimation of time complexities in a real-world application where datasets vary widely in size.

You might also like