DSAA Week7-9-Sorting(Different Sorting Schemes).pptx

SORTING ALGORITHM SORTING refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical and lexicographical order The important soring lies in the fact that data searching can be optimized to a very h...

SORTING ALGORITHM SORTING refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical and lexicographical order The important soring lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to present data in more readable formats. FOLLOWING ARE SOME OF THE EXAMPLES OF SORTING IN REAL-LIFE SCENARIOS Telephone Directory – The telephone directory stores the telephone number of people sorted by their names, so that the names can be searched easily. Dictionary – The dictionary stores words in an alphabetical order so that searching of any word becomes easy. IN-PLACING SORTING AND NOT-IN-PLACE SORTING Sorting algorithms may require some extra space for comparison and temporary storage of few data elements. These algorithms do not require any extra space and sorting is said to happen in- place, or for example, with the array itself. This is called in-place sorting. Bubble sort is an example of in-place sorting. STABLE AND NOT STABLE SORTING If a sorting algorithm, after sorting the contents, does not charge the sequence of similar content in which they appear, it is called stable sorting. 0 1 2 3 4 5 6 7 8 359 33 42 10 14 19 26 44 26 31 10 14 19 26 26 31 33 35 42 44 0 1 2 3 4 5 6 7 8 9 If a sorting algorithm, after sorting the contents, changes the sequence of similar content in which they appear, it is called unstable sorting. 0 1 2 3 4 5 6 7 8 359 33 42 10 14 19 26 44 26 31 35 33 42 10 14 19 26 44 26 31 0 1 2 3 4 5 6 7 8 9 ADAPTIVE AND NON- ADAPTIVE SORTING ALGORITHM A sorting algorithm is said to be adaptive. If it takes advantage of already ‘sorted’ elements in the list that is to be sorted. This is, while sorting if the source list has some element already sorted, adaptive algorithms will take this into account and will try not to A non-adaptive re-order them. algorithm is one which does not take into account the elements which are already sorted. They try to force every single element to be re-ordered to confirm their sortedness. INCREASING ORDER A sequence of values is said to be in increasing order, if the successive element is greater than the previous one For example 1, 3, 4, 6, 8, 9 are in increasing order, as every next element is greater than the previous element. DECREASING ORDER A sequence of value is said to be in decreasing order, if the successive element is less than the current one. For example, 9, 8, 6, 4, 3, 1 are in decreasing order, as every next element is less than the previous element. NON-INCREASING ORDER A sequence of values is said to be in non-increasing order, if the successive element is less than or equal to its previous element in the sequence. This order occurs when the sequence contains duplicate values. For example, 9, 8, 6, 3, 3, 1 are in non-increasing order, as every next element is less than or equal to(in case of 3) but not greater than any previous element. Non-Decreasing Order A sequence of values is said to be in non-decreasing order, if the successive element is greater than or equal to its previous element in the sequence. This order occurs when the sequence contains duplicate values. For example 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next element is greater than or equal to (in case of 3) but not less than the previous one. BUBBLE SORT Bubble sort may be defined as the sorting algorithm that follows the approach of replacing the value in the first index with the smallest value in the array and keep it repeating until the list is sorted. It is a very simple way of performing sorting. In this way to sort the array, the value has to be assigned to the array in the beginning before starting the sorting. The first smallest value found in the array has been moved to the first index of the array and then the search begins again to find the other smallest number. Once the next smallest number is found, it replaces the value in the second index and the process keeps on repeating until the array consists of a sorted list of values. INSERTION SORT Insertion sort picks elements one by one and places it to the right position where it belongs in the sorted list of elements. A simple sorting algorithm that works the way we sort playing cards in our hands. SELECTION SORT Selection sort may be defined as another algorithm for sorting the list in which the array is bifurcated into two arrays where the first array is supposed to be empty while the second array consists of the unsorted list of values. The program searches for the smallest values in the second array and when the value is found, it has been moved to the beginning of the first array that was empty. The approach is repeated again and the next smallest values will be shifted to the second index of the first array. The processes will keep on repeating until the second array became empty. The processes will be repeated until the first list is full of the sorted list. Meanwhile, the programs keep its primary focus to check if the second array is having value and if it is found positive, the program runs the sorting algorithm again. Though it sorts the list in an easy manner, it may take a bit more time as compared to the other algorithms. But by the end, the result it will generate will be the same as the other sorting algorithms. MERGE SORT Merge sort may be defined as another sorting algorithm that performs the sorting by segregating the array till last when it turns into an individual value and then aggregating them in a manner so that it could turn into a sorted array. The process consumes a bit much time as compared to the other rival algorithms but it is considered pretty efficient as compared to others. When it comes to sorting a large list, this algorithm works very fine and hence preferred in developing the application that has to process the large list. QUICK SORT Quick sort can be defined as the other algorithm for sorting the list in which the approach is to divide the array in terms of greater than and less than values until the entire values if divided into individuals forms. In this algorithm, the value of the last index of the array has been selected as a pivot and all the values smaller than pivot has been shifted to the array that is expected to occur in the left of the value and the elements having a higher value than the pivot are shifted to the right array. Again one pivot is selected from the newly formed array that had the values less than the last pivot value. Similarly, the values smaller than the new pivot will be shifted to the array that will be left and the values more than the new pivot will be shifted in the right array. Quicksort is the only algorithm that leads to dividing the array until all the values are separated into the individual arrays. They will be then added or aggregated in a single array which is considered as the sorted list. HEAP SORT Heap sort can be defined as the sorting algorithm that works by searching the maximum element in the list and place it to the last. The algorithm performs the action recursively until the array gets sorted into the ascending way. It is very time taking the process to choose the maximum value and move it to the last and hence it is considered as a less efficient sorting approach when it comes to sorting the large list. However, it works fine with the list that has a limited number of values.  Source: https://www.cs.cmu.edu https://www.tutorialspoint.com