Bubble Sort using C
Bubble Sort is an elementary sorting algorithm, which works by repeatedly
exchanging adjacent elements, if necessary. When no exchanges are required, the
file is sorted.
Bubble sort is a sorting algorithm that compares two adjacent elements and swaps
them until they are in the intended order.Just like the movement of air bubbles in the
water that rise up to the surface, each element of the array move to the end in each
iteration. Therefore, it is called a bubble sort.
Working of Bubble Sort
Suppose we are trying to sort the elements in ascending order.
1. First Iteration (Compare and Swap)
a. Starting from the first index, compare the first and the second elements.
b. If the first element is greater than the second element, they are swapped.
c. Now, compare the second and the third elements. Swap them if they are not in
order.
d. The above process goes on until the last element.
The same process goes on for the remaining iterations.
After each iteration, the largest element among the unsorted elements is placed
at the end.
C Program
#include<stdio.h>
main(){
int d[ ] = {12, 4, 23, 3, 11};
int size = sizeof(d)/sizeof(int);
int i, step, temp;
clrscr();
// Print Elements before Sorting Process
printf("Array before Sorting Process\n", step+1);
for(i=0; i<size; i++)
printf("%d\t", d[i]);
printf("\n\n");
// Sorting Process
for(step=0; step<size-1; step++){
for(i=0; i<size-step-1; i++){
if(d[i] > d[i+1]){
temp = d[i];
d[i] = d[i+1];
d[i+1] = temp;
}
}
// Print Elements after each Iteration
printf("Array after %d Iteration\n", step+1);
for(i=0; i<size; i++)
printf("%d\t", d[i]);
printf("\n");
}
// Print Elements after Sorting
printf("\n\nArray after Sorting\n");
for(i=0; i<size; i++)
printf("%d\t", d[i]);
getch();
}
Insertion Sort using C
Insertion sort is a very simple method to sort numbers in an ascending or descending
order. This method follows the incremental method. It can be compared with the
technique how cards are sorted at the time of playing a game.
Insertion sort is a sorting algorithm that places an unsorted element at its suitable
place in each iteration.
Insertion sort works similarly as we sort cards in our hand in a card game.
We assume that the first card is already sorted then, we select an unsorted card. If
the unsorted card is greater than the card in hand, it is placed on the right otherwise,
to the left. In the same way, other unsorted cards are taken and put in their right
place.
Working of Insertion Sort
1. The first element in the array is assumed to be sorted. Take the second element
and store it separately in key.
Compare key with the first element. If the first element is greater than key, then
key is placed in front of the first element.
2. Now, the first two elements are sorted.
Take the third element and compare it with the elements on the left of it. Placed it
just behind the element smaller than it. If there is no element smaller than it, then
place it at the beginning of the array.
3. Similarly, place every unsorted element at its correct position.
C Program
#include<stdio.h>
main(){
int d[ ] = {12, 4, 23, 3, 11};
int size = sizeof(d)/sizeof(int);
int step, key, i;
clrscr();
// Print Elements before Sorting Process
printf("Array before Sorting Process\n");
for(i=0; i<size; i++)
printf("%d\t", d[i]);
printf("\n\n");
// Insertion Sort Process
for(step=1; step<size; step++){
key = d[step];
i = step-1;
while(i>=0 && key<d[i]){
d[i+1] = d[i];
i--;
}
d[i+1] = key;
// Print after each Iteration
printf("Array after %d Iteration\n", step+1);
for(i=0; i<size; i++)
printf("%d\t", d[i]);
printf("\n");
}
// Print Elements after Sorting Process
printf("\n\nArray after Sorting\n");
for(i=0; i<size; i++)
printf("%d\t", d[i]);
getch();
}
Insertion Sort Complexity
Time Complexity
Best O(n)
Worst O(n2)
Average O(n2)
Space Complexity O(1)
Time Complexities
Worst Case Complexity: O(n2)
Suppose, an array is in ascending order, and you want to sort it in descending
order. In this case, worst case complexity occurs.
Each element has to be compared with each of the other elements so, for every
nth element, (n-1) number of comparisons are made.
Thus, the total number of comparisons = n*(n-1) ~ n2
Best Case Complexity: O(n)
When the array is already sorted, the outer loop runs for n number of times
whereas the inner loop does not run at all. So, there are only n number of
comparisons. Thus, complexity is linear.
Average Case Complexity: O(n2)
It occurs when the elements of an array are in jumbled order (neither ascending
nor descending).
Space Complexity
Space complexity is O(1) because an extra variable key is used.
Selection Sort Algorithm
Selection sort is a sorting algorithm that selects the smallest element from an
unsorted list in each iteration and places that element at the beginning of the
unsorted list.
Working of Selection Sort
1. Set the first element as minimum.
2. Compare minimum with the second element. If the second element is smaller than
minimum, assign the second element as minimum.
Compare minimum with the third element. Again, if the third element is smaller,
then assign minimum to the third element otherwise do nothing. The process goes
on until the last element.
3. After each iteration, minimum is placed in the front of the unsorted list.
4. For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are
repeated until all the elements are placed at their correct positions.
C Program
// Selection sort in C
#include <stdio.h>
void main() {
int data[ ] = {12, 4, 23, 3, 11};
int size = sizeof(data) / sizeof(data[0]);
int i, min_idx, temp, step;
clrscr();
// Print Elements before Sorting Process
printf("Array before Sorting Process\n");
for(i=0; i<size; i++)
printf("%d\t", data[i]);
printf("\n\n");
for (step=0; step<size-1; step++) {
int min_idx = step;
for (i=step+1; i<size; i++) {
// Select the minimum element in each loop.
if(data[i] < data[min_idx])
min_idx = i;
}
// Put min at the correct position
temp = data[min_idx];
data[min_idx] = data[step];
data[step] = temp;
// Print Elements after each Iteration
printf("Array after %d Iteration\n", step+1);
for(i=0; i<size; i++)
printf("%d\t", data[i]);
printf("\n");
}
// Print Elements after Sorting Process
printf("\n\nArray after Sorting\n");
for(i=0; i<size; i++)
printf("%d\t", data[i]);
}
Selection Sort Complexity
Time Complexity
Best O(n2)
Worst O(n2)
Average O(n2)
Space Complexity O(1)
