DS PPT - ( 1 )SORTING lgoritham techniques with bast example

sorting

1. DATA STRUCTUR :- -:SORTONG _METHODS:- BY_Vivek Makwana

2. - Sorting is the Process Of arranging data in some logical order. - This Logical order may be ascending or descending in case of numeric values or dictionary in case of alphanumeric values. - Two types of sorting : - Internal sorting - External sorting Sorting :- SORTONG _METHODS

3. Types of Sorting :- Bubble sort Selection sort Quick sort Insertion sort Merge sort Radix sort SORTONG _METHODS

4. (1) Bubble sort The bubble sort is the easiest and frequently used sorting algorithm among all other algorithms. In the process of bubble sort , it makes multiple passes through a list . Bubble sort focuses on successive adjacent pairs of element in the array , compares them , and either swaps them or not. The main disadvantage of this method is that , it works efficiently for smaller list . Not working well when there is large number of items in the list . SORTONG _METHODS

5. The first element is compared with the second, if first element is grater than second, it will be swapped and further compared with third element and again if is greater than third, then again swapped. If first element is not greater than third element , then now third element is comparison and swapping is made up to the end of the list. Finally at the end of the first pass, the largest element is placed at its proper position ( last position ). Maximum number of passes required is n – 1 . ( where n is the total number of elements ) . SORTONG _METHODS

6. SORTONG _METHODS Example:-

7. (2) Selection sort As the name suggests, selection sort selecting the smallest element in each iteration and pot it into its proper position. In each iteration, the key value is compared with the entire list until the smallest element is found. Then the smallest element is swapped with the key value.( initially, the key value is the first element of item. ) Then, tack second element as key value and find the second smallest element in the entire list. Do the same procedure up to the last element. At the and of the interation , the smallest element is placed at its proper position. SORTONG _METHODS

8. Example:- SORTONG _METHODS

9. (3) Quick sort This is the one of the best technique for a large set of data. This technique works on the method of partitioning, so it is also called partition exchange sort. In each iteration (pass), one element is selected, which is called pivot point. And at the end of each iteration, pivot point is placed in its final position. At that time two sub lists are created ( one on the side of the left side of the pivot having less value then the value of pivot point and second list on the right side of the pivot point having value then the value of the pivot point. SORTONG _METHODS

10. It is based on the rule of ‘divide and conquer’ technique. So, at the end of each iteration, this method divides the list into three main parts. Element less than pivot element Pivot element Element greater than pivot point element Then again same procedure (as above) is applied in both sub lists by taking an element as pivot element. This is why quick sort methode is called recursive given data in sorted form. SORTONG _METHODS

11. Example:- SORTONG _METHODS

12. (4) Insertion sort Insertion sort is a simple sorting algoritham; a comparison sort in which the sorted list (array) is built one at a time. However insertion sort provedes several advantages like: Simple to implicationt. Efficient for small data set. It is adaptive, as more efficient when givin data are sorted. It is stable, as it dose not change the relative order of elements with equal keys. It is a online, besause it can sort a list as it receives list. . SORTONG _METHODS

13. Example :- SORTONG _METHODS

14. (5) Merge sort:- Merge sort is used to merge (combine) two ordered list. So that we need to have two sorted array and combine them into third array in sorted manner. Suppose we have two sorted tables table 1 and table 2. In this method, we have to compare the element of both tables one by one and which element has the smallest value, it will be placed in a third table This process is repeated until all the element of both the tables are placed into third table. SORTONG _METHODS

15. Example :- SORTONG _METHODS

16. This sorting method used in digital computer.it is also used when we have to sort large number of element. In this method 10 buckets (pocket) of digit 0 to 9 are used to store each digit. So this method is also called ‘bucket sort’. During the first pass, we separate the unit digit of the number and place the number in to appropriate pocket to its unit digit. After the first pass, rearrange the elements in FIFO(QUEUE) order. During the second pass, we separate the unit digit of the number and place the number in to appropriate pocket to its unit digit. After this, again repeats until all the elements as above. The sum procedure repeats until all the elements are sorted. (6) Radix sort:- SORTONG _METHODS

17. Example :-

18. Thank You…