Sorting Algorithms to arrange data in particular format

Algorithms

1. Sorting Prepared by Muhammad Kamran

2. Sorting Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is presented in a sorted manner. Sorting is also used to represent data in more readable formats.

3. In-place vs Not-In-place The sorting algorithms which do not require any extra space and sorting is said to happen in-place, or for example, within the array itself. This is called  in-place sorting . Bubble sort is an example of in-place sorting. However in some sorting algorithms, the program requires space which is more than or equal to the elements being sorted . Sorting which uses equal or more space is called  not-in-place sorting . Merge-sort is an example of not-in-place sorting.

4. Adaptive and Non-Adaptive A sorting algorithm is said to be adaptive, if it takes advantage of already 'sorted' elements in the list that is to be sorted. A non-adaptive 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 .

5. Important Terms Increasing Order 1, 3, 6, 12 . . . Decreasing Order 44, 33, 21, 9, 1.

6. Selection Sort Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

7. Selection Sort Step 1 − Set MIN to location 0 Step 2 − Search the minimum element in the list Step 3 − Swap with value at location MIN Step 4 − Increment MIN to point to next element Step 5 − Repeat until list is sorted

8. Selection Sort

9. Bubble Sort Bubble sort is another simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n 2 ) where  n  is the number of items.

10. Bubble Sort Start

11. Bubble Sort Algo begin BubbleSort (list) for all elements of list if list[ i ] > list[i+1] swap(list[ i ], list[i+1]) end if end for return list end BubbleSort

12. Insertion Sort An in-place comparison-based sorting algorithm. An element which is to be inserted in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name,  insertion sort . This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n 2 ), where  n  is the number of items.

13. Insertion Sort Step 1 − If it is the first element, it is already sorted. return 1; Step 2 − Pick next element Step 3 − Compare with all elements in the sorted sub-list Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted Step 5 − Insert the value Step 6 − Repeat until list is sorted

14. Insertion Sort 12, 11, 13, 5, 6 Let us loop for i = 1 (second element of the array) to 4 (last element of the array) i = 1 . Since 11 is smaller than 12, move 12 and insert 11 before 12 11, 12, 13, 5, 6 i = 2 . 13 will remain at its position as all elements in A[0..I-1] are smaller than 13 11, 12, 13, 5, 6 i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position. 5, 11, 12, 13 , 6 i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position. 5, 6, 11, 12, 13

15. Merge Sort Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being Ο(n log n), it is one of the most respected algorithms. Merge sort first divides the array into equal halves and then combines them in a sorted manner.

16. Merge Sort

17. Merge Sort Algorithm Step 1 − if it is only one element in the list it is already sorted, return. Step 2 − divide the list recursively into two halves until it can no more be divided. Step 3 − merge the smaller lists into new list in sorted order.

18. Merge Sort

19. Quick Sort Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value. Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are O( n 2 ), respectively.

20. Quick Sort Pivot Step 1 − Choose the highest index value has pivot Step 2 − Take two variables to point left and right of the list excluding pivot Step 3 − left points to the low index Step 4 − right points to the high Step 5 − while value at left is less than pivot move right Step 6 − while value at right is greater than pivot move left Step 7 − if both step 5 and step 6 does not match swap left and right Step 8 − if left ≥ right, the point where they met is new pivot

21. Quick Sort Algorithm Step 1 − Make the right-most index value pivot Step 2 − partition the array using pivot value Step 3 − quicksort left partition recursively Step 4 − quicksort right partition recursively

22. Quick Sort

23. Quick Sort lo hi Pivot lo hi Pivot 26 27 19 10 14 31 33 44 35 42 lo hi lo hi 10 27 19 26 14 31 33 44 35 42 lo & hi lo & hi 10 27 19 26 14 31 33 35 44 42 10 14 19 26 27 31 33 35 42 44

24. Quick Sort

25. Tasks Implement source code for any two of the following: Bubble Sort Merge Sort Quick Sort

26. Thank You