Sorting Techniques in C programming

Sorting is one of the important category of algorithms in computer science. And a lot of research has gone into this category. Sorting can significantly reduce the complexity of problem and is often used for database algorithms and searches
Indian Institute of Embedded Systems ( www.iies.in)

1. Topic: Sorting in c programming

2. Why Sorting : Sorting is one of the important category of algorithms in computer science. And a lot of research has gone into this category. Sorting can significantly reduce the complexity of problem and is often used for database algorithms and searches. What is Sorting : Sorting is an algorithm that arranges the data elements in a specified order, here the order refers to ascending or descending.

3. C provides the following categories of sorting techniques: Bubble Sort. Insertion Sort. Selection Sort. Quick Sort. Merge Sort.

4. Bubble sort: bubble sort is a simple algorithm. It works by iterating the input array from the first element to the last, comparing each pair of elements and swapping them if needed. Bubble sort continues its iteration until no swaps are needed. The algorithm gets it name from the way smaller elements bubble up to the top of the list. Now let us take an example : Suppose we have an array which is to be sorted like this , a[ ] ={7,9,5,18,2} Before sorting: 7 9 5 18 2 1 2 3 4

5. After sorting the array it should look like this now this is our unsorted array 2 5 7 9 18 1 2 3 4 7 9 5 18 2 1 2 3 4

6. now in the 1ST PASS we compare the adjacent elements and do swapping if they are not in sorted form to get them in sorted form and traverse to the next adjacent elements now for traversing what I can see is we compare the adjacent elements and if it is already in sorted form then we move ahead with next adjacent elements without swapping. What if they are not in sorted order we just simply swap the elements to place them in there right place. To sort an n-size array we perform n-1 passes. Now let us see how actually we perform bubble sort and what actually a pass means and what will happen at the end of each pass. PASS:1 first we compare with index 0 and index 1. 7 9 5 18 2 1 2 3 4

7. since the elements are already in the sorted form we move ahead without swapping. Now we compare with the index 1 and 2 since 5<9 we swap them and go ahead with next adjacent elements. 7 9 5 18 2 1 2 3 4 7 5 9 18 2 1 2 3 4

8. Now we are comparing the index 2 and 3 since 18 > 9 we are not swapping them and moving ahead with next adjacent elements. Now we are comparing with index 3 and index 4 since 2< 18 we are swapping their positions. 7 5 9 18 2 1 2 3 4 7 5 9 2 18 1 2 3 4

9. So now we completed PASS:1 and the complete array comparison and and sorted the highest element in the array to its correct position after PASS:1 array looks like. 7 5 9 2 18 1 2 3 4 Unsorted array Sorted array

10. PASS:2 Now we are comparing with index 0 and index1 since 5<7 we swap the elements and move ahead with the next adjacent comparing. Now we are comparing with index 1 and index 2 since they are in there right positions we are moving ahead without swapping . 7 5 9 2 18 1 2 3 4 5 7 9 2 18 1 2 3 4

11. Now we are comparing with the index 2 and 3 since 2<9 we swap them and move ahead. We can see that we have completed PASS:2 and the result is that 9 has reached its correct position in the array. We have seen below that we have sorted two elements in two passes. The output of second pass is : 5 7 9 2 18 1 2 3 4

12. This the output of second pass we have sorted two elements in two passes: 5 7 2 9 18 1 2 3 4 Unsorted array Sorted array

13. PASS:3 now we are comparing the indices 0 and 1 since they are already in sorted positions we are not going to swap them and proceed with next adjacent comparisons. 5 7 2 9 18 1 2 3 4 5 7 2 9 18 1 2 3 4

14. Now we are comparing with indices 1 and 2 since 2 < 7 we are going to swap them and not going to proceed with next adjacent comparison because and 9 and 18 has already been sorted. we have also finished the pass:3, The output of pass-3 is: 5 2 7 9 18 1 2 3 4 5 2 7 9 18 1 2 3 4 Unsorted array Sorted array

15. PASS:4 In pass 4 we have only one comparison because rest of the elements are already sorted. We are comparing indices 0 and 1 since 2 < 5 we are swapping them and our array is fully sorted. 5 2 7 9 18 1 2 3 4 2 5 7 9 18 1 2 3 4

16. The output of PASS:4 is This is our final output of bubble sort technique. 2 5 7 9 18 1 2 3 4 Fully sorted array

17. In pass:1 we did n-1 comparisons. N=5 n-1= 5-1 = 4 comparisons In pass:2 we did n-2comparisons. N=5 n-1= 5-2 = 3 comparisons In pass:3 we did n-3 comparisons. N=5 n-1= 5-3 = 2 comparisons In pass:4 we did n-4 comparisons. N=5 n-1= 5-4 = 1 comparison.

18. PROGRAM FOR BUBBLE SORT ALGORITHM USING C PROGRAMMING LANGUAGE. #include<stdio.h> // for displaying the output void DisPlay(int A[], int SIZE) { for (int i = 0; i < SIZE; i++) { printf("%d ", A[i]); } printf("\n"); }

19. // for bubblesort void bubble_SorT(int A[], int SIZE){ int temp; int Sorted = 0; for (int i = 0; i < SIZE-1; i++) // For number of pass { // printf("Working on pass number %d\n", i+1); for (int j = 0; j <SIZE-1-i ; j++) // For comparison in each pass { if(A[j]>A[j+1]){ temp = A[j]; A[j] = A[j+1]; A[j+1] = temp; } } } }

20. int main(){ int A[] = {11, 2, 5, 78,8,75,56,65,100,722,7,1}; int SIZE = sizeof(A)/sizeof(int); DisPlay(A, SIZE); // array before sorting bubble_SorT(A, SIZE); // to sort the array DisPlay(A, SIZE); // array After sorting return 0; }